cp's OEIS Frontend

A201546 The number of permutations of {1,2,...,2n} that contain a cycle of length greater than n.

%I A201546 #43 Sep 05 2025 15:14:39
%S A201546 1,14,444,25584,2342880,312888960,57424792320,13869128448000,
%T A201546 4264876094976000,1627055289796608000,754132445894209536000,
%U A201546 417405110861381271552000,271933770461631065948160000,205985221930119691492392960000,179512031423815845458883379200000
%N A201546 The number of permutations of {1,2,...,2n} that contain a cycle of length greater than n.
%D A201546 Richcard Stanley, Enumerative Combinatorics Volume 1 second edition, Cambridge Univ. Press, 2011, page 194 solution 119.
%H A201546 Alois P. Heinz, <a href="/A201546/b201546.txt">Table of n, a(n) for n = 1..100</a>
%H A201546 Wikipedia, <a href="http://en.wikipedia.org/wiki/Random_permutation_statistics">Random permutation statistics</a>
%F A201546 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.
%F A201546 a(n)/(2n)! is the coefficient of x^(2n) in G(x).
%F A201546 a(n) = (2*n)! * (H(2*n) - H(n)) where H(n) = Sum_{k=1..n} 1/k.
%F A201546 a(n) = Sum_{k=n+1..2n} C(2n,k)*(k-1)!*(2n-k)!. - _Geoffrey Critzer_, Jun 01 2013
%F A201546 a(n) ~ sqrt(Pi)*log(2)*2^(2*n+1)*n^(2*n+1/2)/exp(2*n). - _Vaclav Kotesovec_, Sep 29 2013
%e A201546 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.
%p A201546 a:= proc(n) option remember; `if`(n<2, n,
%p A201546       (6-12*n+8*n^2)*a(n-1)-4*(n-1)^2*(2*n-3)^2*a(n-2))
%p A201546     end:
%p A201546 seq(a(n), n=1..20);  # _Alois P. Heinz_, Jun 13 2013
%t A201546 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]
%o A201546 (PARI) a(n) = (2*n)!*sum(k=1, n, 1/(n+k)); \\ _Seiichi Manyama_, May 18 2025
%K A201546 nonn,changed
%O A201546 1,2
%A A201546 _Geoffrey Critzer_, Dec 02 2011