Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%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_