A242027 Number T(n,k) of endofunctions on [n] with cycles of k distinct lengths; triangle T(n,k), n>=0, 0<=k<=A003056(n), read by rows.

1, 0, 1, 0, 4, 0, 24, 3, 0, 206, 50, 0, 2300, 825, 0, 31742, 14794, 120, 0, 522466, 294987, 6090, 0, 9996478, 6547946, 232792, 0, 218088504, 160994565, 8337420, 0, 5344652492, 4355845868, 299350440, 151200, 0, 145386399554, 128831993037, 11074483860, 18794160

Offset: 0

Author

Alois P. Heinz, Aug 11 2014

Keywords

• nonn
• tabf

Examples

			T(3,2) = 3: (1,3,2), (3,2,1), (2,1,3).
Triangle T(n,k) begins:
00 :  1;
01 :  0,          1;
02 :  0,          4;
03 :  0,         24,          3;
04 :  0,        206,         50;
05 :  0,       2300,        825;
06 :  0,      31742,      14794,       120;
07 :  0,     522466,     294987,      6090;
08 :  0,    9996478,    6547946,    232792;
09 :  0,  218088504,  160994565,   8337420;
10 :  0, 5344652492, 4355845868, 299350440, 151200;
		

Links

• Alois P. Heinz, Rows n = 0..140, flattened

Crossrefs

Columns k=0-10 give: A000007, A241980 for n>0, A246283, A246284, A246285, A246286, A246287, A246288, A246289, A246290, A246291.

Row sums give A000312.

T(A000217(n),n) gives A246292.

Cf. A003056, A060281, A218868 (the same for permutations).

Programs

Maple

with(combinat):
b:= proc(n, i, k) option remember; `if`(n=0, `if`(k=0, 1, 0),
      `if`(i<1 or k<1, 0, add((i-1)!^j*multinomial(n, n-i*j, i$j)/j!*
      b(n-i*j, i-1, k-`if`(j=0, 0, 1)), j=0..n/i)))
    end:
T:= (n, k)-> add(binomial(n-1, j-1)*n^(n-j)*b(j$2, k), j=0..n):
seq(seq(T(n, k), k=0..floor((sqrt(1+8*n)-1)/2)), n=0..14);

Mathematica

multinomial[n_, k_] := n!/Times @@ (k!); b[n_, i_, k_] := b[n, i, k] = If[n == 0, If[k==0, 1, 0], If[i<1 || k<1, 0, Sum[(i-1)!^j*multinomial[n, Join[ {n-i*j}, Array[i&, j]]]/j!*b[n-i*j, i-1, k-If[j==0, 0, 1]], {j, 0, n/i}]] ]; T[0, 0] = 1; T[n_, k_] := Sum[Binomial[n-1, j-1]*n^(n-j)*b[j, j, k], {j, 0, n}]; Table[T[n, k], {n, 0, 14}, {k, 0, Floor[(Sqrt[1+8n]-1)/2]}] // Flatten (* Jean-François Alcover, Feb 18 2017, translated from Maple *)