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