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

1, 0, 1, 6, 57, 680, 9945, 172032, 3438673, 78003648, 1980083025, 55616359040, 1712630427849, 57375166877184, 2077563829893097, 80859304977696000, 3366275257190794785, 149270897223530835968, 7024011523121427204897, 349574012216588890718208

Offset

0,4

Comments

E.g.f. equals the square-root of the e.g.f. of A134095. - Paul D. Hanna, Oct 11 2007

References

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

Links

Alois P. Heinz, Table of n, a(n) for n = 0..386

Formula

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)!.

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

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

Example

E.g.f. A(x) = 1 + 0*x + 1*x^2/2! + 6*x^3/3! + 57*x^4/4! + 680*x^5/5! +...
The formula A(x) = 1/sqrt(1 - LambertW(-x)^2 ) is illustrated by:
A(x) = 1/sqrt(1 - (x+ x^2+ 3^2*x^3/3!+ 4^3*x^4/4!+ 5^4*x^5/5! +...)^2).

Mathematica

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 *)

Prog

(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

Crossrefs

Cf. A134095.

Column k=2 of A246609.

Sequence in context: A207412 A362167 A324447 * A153851 A141372 A306030

Adjacent sequences: A060432 A060433 A060434 * A060436 A060437 A060438

Keyword

nonn

Author

Vladeta Jovovic, Apr 07 2001

Extensions

More terms from Alois P. Heinz, Aug 26 2014

Status

approved