[go: up one dir, main page]

login
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.
14
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,5
LINKS
EXAMPLE
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;
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 *)
CROSSREFS
Row sums give A000312.
T(A000217(n),n) gives A246292.
Cf. A003056, A060281, A218868 (the same for permutations).
Sequence in context: A229827 A295839 A243270 * A329891 A357810 A057402
KEYWORD
nonn,tabf
AUTHOR
Alois P. Heinz, Aug 11 2014
STATUS
approved