A001471 Number of degree-n permutations of order exactly 3. (Formerly M1833 N0727)

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,4

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.

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

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

Prog

(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
(Magma) m:=30; R<x>:=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
(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

Crossrefs

Cf. A000085, A001470, A001472, A052501, A053496-A053505, A001189, A001471, A001473, A061121-A061128.

Column k=3 of A057731.

Sequence in context: A133467 A091004 A005559 * A162585 A000159 A358681

Adjacent sequences: A001468 A001469 A001470 * A001472 A001473 A001474

Keyword

nonn,easy,nice

Author

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

Status

approved