|
|
A201546
|
|
The number of permutations of {1,2,...,2n} that contain a cycle of length greater than n.
|
|
2
|
|
|
1, 14, 444, 25584, 2342880, 312888960, 57424792320, 13869128448000, 4264876094976000, 1627055289796608000, 754132445894209536000, 417405110861381271552000, 271933770461631065948160000, 205985221930119691492392960000, 179512031423815845458883379200000
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
(2n)!*(H(2n)-H(n)) where H(n) is the harmonic number. See "One Hundred Prisoners" in Wikipedia reference below.
|
|
REFERENCES
|
Richcard Stanley, Enumerative Combinatorics Volume 1 second edition, Cambridge Univ. Press, 2011, page 194 solution 119.
|
|
LINKS
|
|
|
FORMULA
|
The E.g.f. for the number of n-permutations that have a cycle of length greater than k is G(x)=1/(1-x) - exp(A(x)) where A(x)=Sum_{j=1..k}x^j/j.
a(n)/(2n)! is the coefficient of x^(2n) in G(x).
a(n) ~ sqrt(Pi)*log(2)*2^(2*n+1)*n^(2*n+1/2)/exp(2*n). - Vaclav Kotesovec, Sep 29 2013
|
|
EXAMPLE
|
a(2)=14 because there are 6 permutations of {1,2,3,4} that contain a cycle of length four and 8 that contain a cycle of length three. 6+8=14.
|
|
MAPLE
|
a:= proc(n) option remember; `if`(n<2, n,
(6-12*n+8*n^2)*a(n-1)-4*(n-1)^2*(2*n-3)^2*a(n-2))
end:
|
|
MATHEMATICA
|
Drop[Table[a = Sum[x^j/j, {j, 1, n}]; Coefficient[Series[1/(1 - x) - Exp[a], {x, 0, 40}], x^(2 n)]*(2 n)!, {n, 1, 40}], -20]
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|