login
Number of functions f: {1,2,...,n} -> {1,2,...,n} with even cycles only.
12

%I #30 Jul 15 2024 15:15:45

%S 1,0,1,6,57,680,9945,172032,3438673,78003648,1980083025,55616359040,

%T 1712630427849,57375166877184,2077563829893097,80859304977696000,

%U 3366275257190794785,149270897223530835968,7024011523121427204897,349574012216588890718208

%N Number of functions f: {1,2,...,n} -> {1,2,...,n} with even cycles only.

%C E.g.f. equals the square-root of the e.g.f. of A134095. - _Paul D. Hanna_, Oct 11 2007

%D I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, Wiley, N.Y., 1983.

%H Alois P. Heinz, <a href="/A060435/b060435.txt">Table of n, a(n) for n = 0..386</a>

%F E.g.f.: 1/sqrt(1-(LambertW(-x))^2). a(n)=(n-1)!*Sum_{k=0..floor((n-2)/2)} (k+1)/2^(2*k+1)*binomial(2*k+2, k+1)*n^(n-2-2*k)/(n-2-2*k)!.

%F A134095(n) = Sum_{k=0..n} C(n,k) * a(n-k) * a(k) with a(0)=1 and a(1)=0 where A134095(n) = Sum_{k=0..n} C(n,k) * (n-k)^k * k^(n-k). - _Paul D. Hanna_, Oct 11 2007

%F a(n) ~ n! * 2^(3/4)*Gamma(3/4)*exp(n)/(4*Pi*n^(3/4)) * (1- 5*Pi/ (24*Gamma(3/4)^2*sqrt(n))). - _Vaclav Kotesovec_, Sep 24 2013

%e E.g.f. A(x) = 1 + 0*x + 1*x^2/2! + 6*x^3/3! + 57*x^4/4! + 680*x^5/5! +...

%e The formula A(x) = 1/sqrt(1 - LambertW(-x)^2 ) is illustrated by:

%e A(x) = 1/sqrt(1 - (x+ x^2+ 3^2*x^3/3!+ 4^3*x^4/4!+ 5^4*x^5/5! +...)^2).

%t t = Sum[n^(n - 1) x^n/n!, {n, 1, 20}]; Range[0, 20]! CoefficientList[Series[(1/(1 - t^2))^(1/2), {x, 0, 20}], x] (* _Geoffrey Critzer_, Dec 07 2011 *)

%o (PARI) {a(n)=local(LambertW=sum(k=0,n,(-x)^(k+1)*(k+1)^k/(k+1)!) +x*O(x^n)); n!*polcoeff(1/sqrt(1-subst(LambertW,x,-x)^2),n)} \\ _Paul D. Hanna_, Oct 11 2007

%Y Cf. A134095.

%Y Column k=2 of A246609.

%K nonn

%O 0,4

%A _Vladeta Jovovic_, Apr 07 2001

%E More terms from _Alois P. Heinz_, Aug 26 2014