A001471 Number of degree-n permutations of order exactly 3.

0, 0, 0, 2, 8, 20, 80, 350, 1232, 5768, 31040, 142010, 776600, 4874012, 27027728, 168369110, 1191911840, 7678566800, 53474964992, 418199988338, 3044269834280, 23364756531620, 199008751634000, 1605461415071822

Offset: 0

Author

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

Keywords

• nonn
• easy
• nice

Comments

a(n) is the number of non-symmetric permutation matrices A of dimension n such that A^2 is the transpose of A. - Torlach Rush, Jul 09 2020

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

Links

• T. D. Noe, Table of n, a(n) for n = 0..100
• 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, A001472, A052501, A053496-A053505, A001189, A001471, A001473, A061121-A061128.

Column k=3 of A057731.

Programs

Magma

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

Mathematica

a[n_] := HypergeometricPFQ[{1/3-n/3, 2/3-n/3, -n/3}, {}, -9] - 1; Table[a[n], {n, 0, 23}] (* Jean-François Alcover, Oct 19 2011 *)
nxt[{n_,a_,b_,c_}]:={n+1,b,c,c+(1+a)(n-1)(n-2)}; NestList[nxt,{3,0,0,0},25][[;;,2]] (* Harvey P. Dale, Mar 09 2024 *)

PARI

a(n)=sum(j=1,n\3, n!/(j!*(n-3*j)!*(3^j))) \\ Charles R Greathouse IV, Jun 21 2017

PARI

first(n)=my(v=vector(n+1)); for(i=3,n, v[i+1]=v[i] + (1+v[i-2])*(i-1)*(i-2)); v \\ Charles R Greathouse IV, Jul 10 2020

Sage

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

Formula

From Henry Bottomley, Jan 26 2001: (Start)

a(n) = a(n-1) + (1 + a(n-3))*(n-1)(n-2).

a(n) = Sum_{j=1..floor(n/3)} n!/(j!*(n-3*j)!*(3^j)).

a(n) = A001470(n) - 1. (End)

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