A001470 Number of degree-n permutations of order dividing 3.

1, 1, 1, 3, 9, 21, 81, 351, 1233, 5769, 31041, 142011, 776601, 4874013, 27027729, 168369111, 1191911841, 7678566801, 53474964993, 418199988339, 3044269834281, 23364756531621, 199008751634001, 1605461415071823, 13428028220072049, 123280859122040601

Offset: 0

Author

N. J. A. Sloane, J. H. Conway and Simon Plouffe

Keywords

• easy
• nonn
• nice
• 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

• Seiichi Manyama, Table of n, a(n) for n = 0..631 (terms 0..100 from T. D. Noe)
• Joerg Arndt, Generating Random Permutations, PhD thesis, Australian National University, Canberra, Australia, (2010).
• Marcello Artioli, Giuseppe Dattoli, Silvia Licciardi, and Simonetta Pagnutti, Motzkin Numbers: an Operational Point of View, arXiv:1703.07262 [math.CO], 2017. See p. 7.
• L. Moser and M. Wyman, On Solutions of x^d = 1 in Symmetric Groups, Canad. J. Math., 7 (1955), 159-168.

Crossrefs

Cf. A000085, A001472.

Column k=3 of A008307.

Programs

Magma

R:=PowerSeriesRing(Rationals(), 40); Coefficients(R!(Laplace( Exp(x+x^3/3) ))); // G. C. Greubel, Sep 03 2023

Maple

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

Mathematica

a[n_] := HypergeometricPFQ[{(1-n)/3, (2-n)/3, -n/3}, {}, -9]; Table[a[n], {n, 0, 23}] (* Jean-François Alcover, Nov 03 2011 *)
With[{nn=30},CoefficientList[Series[Exp[x+x^3/3],{x,0,nn}],x] Range[ 0,nn]!] (* Harvey P. Dale, Aug 12 2016 *)

Maxima

a(n):=n!*sum(if mod(n-k,2)=0 then binomial(k,(3*k-n)/2)*(1/3)^((n-k)/2)/k! else 0,k,floor(n/3),n); /* Vladimir Kruchinin, Sep 07 2010 */

SageMath

def A001470_list(prec):
    P. = PowerSeriesRing(QQ, prec)
    return P( exp(x+x^3/3) ).egf_to_ogf().list()
A001470_list(40) # G. C. Greubel, Sep 03 2023

Formula

a(n) = Sum_{j=0..floor(n/3)} n!/(j!*(n-3j)!*(3^j)) (the latter formula from Roger Cuculière).

E.g.f.: exp(x + (1/3)*x^3).

D-finite with recurrence: a(n) = a(n-1) + (n-1)*(n-2)*a(n-3). - Geoffrey Critzer, Feb 03 2009

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

a(n) ~ n^(2*n/3)*exp(n^(1/3)-2*n/3)/sqrt(3) * (1 - 1/(6*n^(1/3)) + 25/(72*n^(2/3))). - Vaclav Kotesovec, Jul 28 2013