%I M1833 N0727 #38 Mar 09 2024 17:18:06
%S 0,0,0,2,8,20,80,350,1232,5768,31040,142010,776600,4874012,27027728,
%T 168369110,1191911840,7678566800,53474964992,418199988338,
%U 3044269834280,23364756531620,199008751634000,1605461415071822
%N Number of degree-n permutations of order exactly 3.
%C 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
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H T. D. Noe, <a href="/A001471/b001471.txt">Table of n, a(n) for n = 0..100</a>
%H L. Moser and M. Wyman, <a href="http://dx.doi.org/10.4153/CJM-1955-020-0">On solutions of x^d = 1 in symmetric groups</a>, Canad. J. Math., 7 (1955), 159-168.
%F From _Henry Bottomley_, Jan 26 2001: (Start)
%F a(n) = a(n-1) + (1 + a(n-3))*(n-1)(n-2).
%F a(n) = Sum_{j=1..floor(n/3)} n!/(j!*(n-3*j)!*(3^j)).
%F a(n) = A001470(n) - 1. (End)
%F E.g.f.: exp(x + x^3/3) - exp(x).
%t 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 *)
%t 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 *)
%o (PARI) a(n)=sum(j=1,n\3, n!/(j!*(n-3*j)!*(3^j))) \\ _Charles R Greathouse IV_, Jun 21 2017
%o (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
%o (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
%o (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
%Y Cf. A000085, A001470, A001472, A052501, A053496-A053505, A001189, A001471, A001473, A061121-A061128.
%Y Column k=3 of A057731.
%K nonn,easy,nice
%O 0,4
%A _N. J. A. Sloane_ and _J. H. Conway_