|
Search: id:A145877
|
|
|
| A145877 |
|
Triangle read by rows: T(n,k) is the number of permutations of [n] for which the shortest cycle length is k (1<=k<=n). |
|
+0
2
|
|
| 1, 1, 1, 4, 0, 2, 15, 3, 0, 6, 76, 20, 0, 0, 24, 455, 105, 40, 0, 0, 120, 3186, 714, 420, 0, 0, 0, 720, 25487, 5845, 2688, 1260, 0, 0, 0, 5040, 229384, 52632, 22400, 18144, 0, 0, 0, 0, 40320, 2293839, 525105, 223200, 151200, 72576, 0, 0, 0, 0, 362880, 25232230
(list; table; graph; listen)
|
|
|
OFFSET
|
1,4
|
|
|
COMMENT
|
Row sums are the factorials (A000142).
Sum(T(n,k),k=2..n)=A000166(n) (the derangement numbers).
T(n,1)=A002467(n).
T(n,n)=(n-1)! (A000142).
Sum(k*T(n,k),k=1..n)=A028417(n).
For the statistic "length of the longest cycle", see A126074.
|
|
FORMULA
|
E.g.f. for column k is [1-exp(-x^k/k)]*exp[ -sum(x^j/j,j=1..k-1)]/(1-x) (Vladeta Jovovic (vladeta(AT)eunet.rs).
|
|
EXAMPLE
|
T(4,2)=3 because we have 3412=(13)(24), 2143=(12)(34) and 4321=(14)(23).
Triangle starts:
1;
1,1;
4,0,2;
15,3,0,6;
76,20,0,0,24;
455,105,40,0,0,120;
|
|
MAPLE
|
F:=proc(k) options operator, arrow: (1-exp(-x^k/k))*exp(-(sum(x^j/j, j = 1 .. k-1)))/(1-x) end proc: for k to 16 do g[k]:= series(F(k), x=0, 16) end do: T:= proc(n, k) options operator, arrow: factorial(n)*coeff(g[k], x, n) end proc: for n to 11 do seq(T(n, k), k=1..n) end do; # yields sequence in triangular form
|
|
CROSSREFS
|
Cf. A000142, A000166, A002467, A028417, A126074.
Sequence in context: A058054 A011352 A134895 this_sequence A057075 A156788 A130801
Adjacent sequences: A145874 A145875 A145876 this_sequence A145878 A145879 A145880
|
|
KEYWORD
|
nonn,tabl
|
|
AUTHOR
|
Emeric Deutsch (deutsch(AT)duke.poly.edu), Oct 27 2008
|
|
|
Search completed in 0.002 seconds
|
