login
Number of permutations on n letters that have only cycles of length 4 or less.
6

%I #25 Mar 29 2019 18:54:43

%S 1,1,2,6,24,96,456,2472,14736,92304,632736,4661856,36364032,297668736,

%T 2583425664,23550535296,224086162176,2221083839232,22976670905856,

%U 246829966447104,2745834333566976,31605782067081216,376290722808502272

%N Number of permutations on n letters that have only cycles of length 4 or less.

%D Dennis P. Walsh, The Number of Permutations with Only Small Cycles, preprint [From _Geoffrey Critzer_, May 24 2009]

%H Michael De Vlieger, <a href="/A070945/b070945.txt">Table of n, a(n) for n = 0..499</a>

%H P. L. Krapivsky, J. M. Luck, <a href="https://arxiv.org/abs/1902.04365">Coverage fluctuations in theater models</a>, arXiv:1902.04365 [cond-mat.stat-mech], 2019.

%H I. Mezo, <a href="http://arxiv.org/abs/1308.1637">Periodicity of the last digits of some combinatorial sequences</a>, arXiv preprint arXiv:1308.1637 [math.CO], 2013 and <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Mezo/mezo19.html">J. Int. Seq. 17 (2014) #14.1.1</a> .

%H R. Petuchovas, <a href="https://arxiv.org/abs/1611.02934">Asymptotic analysis of the cyclic structure of permutations</a>, arXiv:1611.02934 [math.CO], p. 6, 2016.

%F E.g.f.: exp(x + 1/2*x^2 + 1/3*x^3 + 1/4*x^4).

%p with (combstruct):a:=proc(m) [ZL, {ZL=Set(Cycle(Z, m>=card))}, labeled]; end: A:=a(4):seq(count(A, size=n), n=0..22); # _Zerinvary Lajos_, Jun 11 2008

%p G := exp(x+(1/2)*x^2+(1/3)*x^3+(1/4)*x^4): seq(factorial(n)*coeftayl(G, x = 0, n), n = 0 .. 22); # _Emeric Deutsch_, Jun 21 2009

%t Table[Sum[Binomial[n, 4 i]*(4 i)!/(i!*4^i)* Sum[Binomial[n - 4 i, 3 j]*(3 j)!/(j!*3^j)* Sum[Binomial[n - 4 i - 3 j, 2 k]*(2 k)!/(k!*2^k), {k, 0, n}], {j, 0, n}], {i, 0, n}], {n, 0, 22}] (* _Geoffrey Critzer_, May 24 2009 *)

%t With[{nn = 23, k = 5}, CoefficientList[Exp[-Log[1 - x] + O[x]^k // Normal] + O[x]^nn, x] Range[0, nn - 1]!] (* _Michael De Vlieger_, Mar 29 2019, after _Jean-François Alcover_ at A070947 *)

%Y Cf. A057693.

%K nonn

%O 0,3

%A _N. J. A. Sloane_ and Sharon Sela, May 18 2002