login
Number of degree-n permutations of order dividing 3.
(Formerly M2782 N1118)
50

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