login
A347034
Triangle read by columns: T(n,k) is the number of functions from an n-element set to a k-element set that are not one-to-one, k>=n>=1.
1
0, 0, 2, 0, 3, 21, 0, 4, 40, 232, 0, 5, 65, 505, 3005, 0, 6, 96, 936, 7056, 45936, 0, 7, 133, 1561, 14287, 112609, 818503, 0, 8, 176, 2416, 26048, 241984, 2056832, 16736896, 0, 9, 225, 3537, 43929, 470961, 4601529, 42683841, 387057609, 0, 10, 280, 4960, 69760, 848800
OFFSET
1,3
COMMENTS
The formula for this sequence is Theorem 2.2(iv) of the author's paper, p. 131 (see the link).
LINKS
Mohammad K. Azarian, Remarks and Conjectures Regarding Combinatorics of Discrete Partial Functions, Int'l Math. Forum (2022) Vol. 17, No. 3, 129-141.
FORMULA
T(n,k) = k^n - k!/(k - n)!, k>=n.
T(n,n) = A036679(n).
EXAMPLE
For T(2,3): the number of functions is 3^2 and the number of one-to-one functions is 6, so 3^2 - 6 = 3 and thus T(2,3) = 3.
Triangle T(n,k) begins:
k=1 k=2 k=3 k=4 k=5 k=6
n=1: 0 0 0 0 0 0
n=2: 2 3 4 5 6
n=3: 21 40 65 96
n=4: 232 505 936
n=5: 3005 7056
n=6: 45936
MAPLE
A347034 := proc(n, k)
k^n-k!/(k-n)! ;
end proc:
seq(seq(A347034(n, k), n=1..k), k=1..12) ; # R. J. Mathar, Jan 12 2023
MATHEMATICA
Table[k^n - k!/(k - n)!, {k, 12}, {n, k}] // Flatten
PROG
(PARI) T(n, k) = k^n - k!/(k - n)!;
row(k) = vector(k, i, T(i, k)); \\ Michel Marcus, Oct 01 2021
KEYWORD
easy,nonn,tabl
AUTHOR
Mohammad K. Azarian, Aug 28 2021
STATUS
approved