%I M2782 N1118 #70 Sep 04 2023 12:33:00
%S 1,1,1,3,9,21,81,351,1233,5769,31041,142011,776601,4874013,27027729,
%T 168369111,1191911841,7678566801,53474964993,418199988339,
%U 3044269834281,23364756531621,199008751634001,1605461415071823
%N Number of degree-n permutations of order dividing 3.
%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).
%D R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Example 5.2.10.
%H Seiichi Manyama, <a href="/A001470/b001470.txt">Table of n, a(n) for n = 0..631</a> (terms 0..100 from T. D. Noe)
%H Joerg Arndt, <a href="http://jjj.de/pub/arndt-rand-perm-thesis.pdf">Generating Random Permutations</a>, PhD thesis, Australian National University, Canberra, Australia, (2010).
%H Marcello Artioli, Giuseppe Dattoli, Silvia Licciardi, and Simonetta Pagnutti, <a href="https://arxiv.org/abs/1703.07262">Motzkin Numbers: an Operational Point of View</a>, arXiv:1703.07262 [math.CO], 2017. See p. 7.
%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 a(n) = Sum_{j=0..floor(n/3)} n!/(j!*(n-3j)!*(3^j)) (the latter formula from _Roger Cuculière_).
%F E.g.f.: exp(x + (1/3)*x^3).
%F D-finite with recurrence: a(n) = a(n-1) + (n-1)*(n-2)*a(n-3). - _Geoffrey Critzer_, Feb 03 2009
%F 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
%F 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
%t 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 *)
%t With[{nn=30},CoefficientList[Series[Exp[x+x^3/3],{x,0,nn}],x] Range[ 0,nn]!] (* _Harvey P. Dale_, Aug 12 2016 *)
%o (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 */
%o (Magma) R<x>:=PowerSeriesRing(Rationals(), 40); Coefficients(R!(Laplace( Exp(x+x^3/3) ))); // _G. C. Greubel_, Sep 03 2023
%o (SageMath)
%o def A001470_list(prec):
%o P.<x> = PowerSeriesRing(QQ, prec)
%o return P( exp(x+x^3/3) ).egf_to_ogf().list()
%o A001470_list(40) # _G. C. Greubel_, Sep 03 2023
%Y Cf. A000085, A001472.
%Y Column k=3 of A008307.
%K easy,nonn,nice
%O 0,4
%A _N. J. A. Sloane_, _J. H. Conway_ and _Simon Plouffe_