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

%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_