A001472 Number of degree-n permutations of order dividing 4.

1, 1, 2, 4, 16, 56, 256, 1072, 6224, 33616, 218656, 1326656, 9893632, 70186624, 574017536, 4454046976, 40073925376, 347165733632, 3370414011904, 31426411211776, 328454079574016, 3331595921852416, 37125035407900672, 400800185285464064, 4744829049220673536

Offset: 0

Author

N. J. A. Sloane and J. H. Conway

Keywords

• nonn
• nice
• easy
• changed

References

• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
• R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Example 5.2.10.

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..570 (first 201 terms from T. D. Noe)
• INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 25 (Dead link)
• Vladimir Victorovich Kruchinin, Composition of ordinary generating functions, arXiv:1009.2565 [math.CO], 2010.
• L. Moser and M. Wyman, On solutions of x^d = 1 in symmetric groups, Canad. J. Math., 7 (1955), 159-168.

Crossrefs

Cf. A000085, A001470, A053495.

Column k=4 of A008307.

Programs

Magma

m:=30; R:=PowerSeriesRing(Rationals(), m); b:=Coefficients(R!( Exp(x + x^2/2 +x^4/4) )); [Factorial(n-1)*b[n]: n in [1..m]]; // G. C. Greubel, May 14 2019

Maple

spec := [S, {S = Set(Union(Cycle(Z, card = 1), Cycle(Z, card = 2), Cycle(Z, card = 4)))}, labeled]; seq(combstruct[count](spec, size = n), n = 0 .. 23); # David Radcliffe, Aug 29 2025

Mathematica

n = 23; CoefficientList[Series[Exp[x+x^2/2+x^4/4], {x, 0, n}], x] * Table[k!, {k, 0, n}] (* Jean-François Alcover, May 18 2011 *)

Maxima

a(n):=n!*sum(sum(binomial(k,j)*binomial(j,n-4*k+3*j)*(1/2)^(n-4*k+3*j)*(1/4)^(k-j),j,floor((4*k-n)/3),k)/k!,k,1,n); /* Vladimir Kruchinin, Sep 07 2010 */

PARI

my(N=33, x='x+O('x^N)); egf=exp(x+x^2/2+x^4/4); Vec(serlaplace(egf)) /* Joerg Arndt, Sep 15 2012 */

Sage

m = 30; T = taylor(exp(x + x^2/2 + x^4/4), x, 0, m); [factorial(n)*T.coefficient(x, n) for n in (0..m)] # G. C. Greubel, May 14 2019

Formula

E.g.f.: exp(x + x^2/2 + x^4/4).

D-finite with recurrence: a(0)=1, a(1)=1, a(2)=2, a(3)=4, a(n) = a(n-1) + (n-1)*a(n-2) + (n^3-6*n^2+11*n-6)*a(n-4) for n>3. - H. Palsdottir (hronn07(AT)ru.is), Sep 19 2008

a(n) = n!*Sum_{k=1..n} (1/k!)*Sum_{j=floor((4*k-n)/3)..k} binomial(k,j) * binomial(j,n-4*k+3*j) * (1/2)^(n-4*k+3*j)*(1/4)^(k-j), n>0. - Vladimir Kruchinin, Sep 07 2010

a(n) ~ n^(3*n/4)*exp(n^(1/4)-3*n/4+sqrt(n)/2-1/8)/2 * (1 - 1/(4*n^(1/4)) + 17/(96*sqrt(n)) + 47/(128*n^(3/4))). - Vaclav Kotesovec, Aug 09 2013