login
Number of degree-n permutations of order dividing 4.
(Formerly M1292 N0495)
39

%I M1292 N0495 #53 Sep 08 2022 08:44:29

%S 1,1,2,4,16,56,256,1072,6224,33616,218656,1326656,9893632,70186624,

%T 574017536,4454046976,40073925376,347165733632,3370414011904,

%U 31426411211776,328454079574016,3331595921852416,37125035407900672,400800185285464064

%N Number of degree-n permutations of order dividing 4.

%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 T. D. Noe, <a href="/A001472/b001472.txt">Table of n, a(n) for n=0..200</a>

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=25">Encyclopedia of Combinatorial Structures 25</a>

%H Vladimir Victorovich Kruchinin, <a href="http://arxiv.org/abs/1009.2565">Composition of ordinary generating functions</a>, arXiv:1009.2565 [math.CO], 2010.

%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 E.g.f.: exp(x + x^2/2 + x^4/4).

%F D-finite with recurrence: a(0)=1, a(1)=1, a(2)=2, a(3)=4, a(n) = a(n-1) + (n-1)*a(n-2) + (n^3-6*n^2+11*n-6)*a(n-4) for n>3. - H. Palsdottir (hronn07(AT)ru.is), Sep 19 2008

%F a(n) = n!*Sum_{k=1..n} (1/k!)*(Sum_{j=floor((4*k-n)/3)..k} binomial(k,j) * binomial(j,n-4*k+3*j) * (1/2)^(n-4*k+3*j)*(1/4)^(k-j), n>0. - _Vladimir Kruchinin_, Sep 07 2010

%F a(n) ~ n^(3*n/4)*exp(n^(1/4)-3*n/4+sqrt(n)/2-1/8)/2 * (1 - 1/(4*n^(1/4)) + 17/(96*sqrt(n)) + 47/(128*n^(3/4))). - _Vaclav Kotesovec_, Aug 09 2013

%t n = 23; CoefficientList[Series[Exp[x+x^2/2+x^4/4], {x, 0, n}], x] * Table[k!, {k, 0, n}] (* _Jean-François Alcover_, May 18 2011 *)

%o (Maxima) a(n):=n!*sum(sum(binomial(k,j)*binomial(j,n-4*k+3*j)*(1/2)^(n-4*k+3*j)*(1/4)^(k-j),j,floor((4*k-n)/3),k)/k!,k,1,n); /* _Vladimir Kruchinin_, Sep 07 2010 */

%o (PARI) N=33; x='x+O('x^N); egf=exp(x+x^2/2+x^4/4); Vec(serlaplace(egf)) /* _Joerg Arndt_, Sep 15 2012 */

%o (Magma) m:=30; R<x>:=PowerSeriesRing(Rationals(), m); b:=Coefficients(R!( Exp(x + x^2/2 +x^4/4) )); [Factorial(n-1)*b[n]: n in [1..m]]; // _G. C. Greubel_, May 14 2019

%o (Sage) m = 30; T = taylor(exp(x + x^2/2 + x^4/4), x, 0, m); [factorial(n)*T.coefficient(x, n) for n in (0..m)] # _G. C. Greubel_, May 14 2019

%Y Cf. A000085, A001470, A053495.

%Y Column k=4 of A008307.

%K nonn,nice,easy

%O 0,3

%A _N. J. A. Sloane_ and _J. H. Conway_