|
|
A122974
|
|
Triangle T(n,k), the number of permutations on n elements that have no cycles of length k.
|
|
3
|
|
|
0, 1, 1, 2, 3, 4, 9, 15, 16, 18, 44, 75, 80, 90, 96, 265, 435, 520, 540, 576, 600, 1854, 3045, 3640, 3780, 4032, 4200, 4320, 14833, 24465, 29120, 31500, 32256, 33600, 34560, 35280, 133496, 220185, 259840, 283500, 290304, 302400, 311040, 317520, 322560
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,4
|
|
COMMENTS
|
Read as sequence, a(n) is the number of permutations on j elements with no cycles of length i where j=round((2*n)^.5) and i=n-C(j,2).
T(n,k) generalizes several sequences already in the On-Line Encyclopedia, such as A000166, the number of permutations on n elements with no fixed points and A000266, the number of permutations on n elements with no transpositions (i.e., no 2-cycles). See the cross references for further examples.
|
|
LINKS
|
|
|
FORMULA
|
T(n,k)=n!*sum r=0..floor(n/k)((-1/k)^r/r!) E.G.F: exp(-x^k/k)/(1-x) a(n)=(round((2*n)^.5))!*sum((-1/(n-binomial(round((2*n)^.5),2)))^r/r!,r=0..floor(round((2*n)^.5)/(n-binomial(round((2*n)^.5),2)))).
|
|
EXAMPLE
|
T(3,2)=3 since there are exactly 3 permutations of 1,2,3 that have no cycles of length 2, namely, (1)(2)(3),(1 2 3) and (2 1 3).
Triangle T(n,k) begins:
0;
1, 1;
2, 3, 4;
9, 15, 16, 18;
44, 75, 80, 90, 96;
265, 435, 520, 540, 576, 600;
1854, 3045, 3640, 3780, 4032, 4200, 4320;
14833, 24465, 29120, 31500, 32256, 33600, 34560, 35280;
...
|
|
MAPLE
|
seq((round((2*n)^.5))!*sum((-1/(n-binomial(round((2*n)^.5), 2)))^r/r!, r=0..floor(round((2*n)^.5)/(n-binomial(round((2*n)^.5), 2)))), n=1..66);
# second Maple program:
T:= proc(n, k) option remember; `if`(n=0, 1, add(`if`(j=k, 0,
T(n-j, k)*binomial(n-1, j-1)*(j-1)!), j=1..n))
end:
|
|
MATHEMATICA
|
T[n_, k_] := T[n, k] = If[n==0, 1, Sum[If[j==k, 0, T[n - j, k] Binomial[n - 1, j - 1] (j - 1)!], {j, 1, n}]];
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|