login
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

%I #61 Jan 12 2023 06:32:16

%S 0,0,2,0,3,21,0,4,40,232,0,5,65,505,3005,0,6,96,936,7056,45936,0,7,

%T 133,1561,14287,112609,818503,0,8,176,2416,26048,241984,2056832,

%U 16736896,0,9,225,3537,43929,470961,4601529,42683841,387057609,0,10,280,4960,69760,848800

%N 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.

%C The formula for this sequence is Theorem 2.2(iv) of the author's paper, p. 131 (see the link).

%H Mohammad K. Azarian, <a href="https://doi.org/10.12988/imf.2022.912321">Remarks and Conjectures Regarding Combinatorics of Discrete Partial Functions</a>, Int'l Math. Forum (2022) Vol. 17, No. 3, 129-141.

%F T(n,k) = k^n - k!/(k - n)!, k>=n.

%F T(n,n) = A036679(n).

%e 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.

%e Triangle T(n,k) begins:

%e k=1 k=2 k=3 k=4 k=5 k=6

%e n=1: 0 0 0 0 0 0

%e n=2: 2 3 4 5 6

%e n=3: 21 40 65 96

%e n=4: 232 505 936

%e n=5: 3005 7056

%e n=6: 45936

%p A347034 := proc(n,k)

%p k^n-k!/(k-n)! ;

%p end proc:

%p seq(seq(A347034(n,k),n=1..k),k=1..12) ; # _R. J. Mathar_, Jan 12 2023

%t Table[k^n - k!/(k - n)!, {k, 12}, {n, k}] // Flatten

%o (PARI) T(n,k) = k^n - k!/(k - n)!;

%o row(k) = vector(k, i, T(i, k)); \\ _Michel Marcus_, Oct 01 2021

%Y Cf. A000312, A002416, A036679, A068424, A089072, A101030, A199656, A344110, A344112, A344113, A344114, A344115, A344116.

%K easy,nonn,tabl

%O 1,3

%A _Mohammad K. Azarian_, Aug 28 2021