login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A057693 Number of permutations on n letters that have only cycles of length 3 or less. 13

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

%S 1,1,2,6,18,66,276,1212,5916,31068,171576,1014696,6319512,41143896,

%T 281590128,2007755856,14871825936,114577550352,913508184096,

%U 7526682826848,64068860545056,561735627038496,5068388485760832,47026385852423616,447837548306401728

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

%C Related to sequence A000085 since it can be shown that sequence A000085 represents the number of permutations (on n letters) that have only cycles of length 2 or less. Letting b(i) denote the i-th term of the sequence A000085, we obtain a(n)=sum(binomial(n,3*j)*(3*j)!*(1/3)^j*b(n-3*j)/j!,j=0..floor(n/3))

%D Dennis P. Walsh, The number of permutations with only small cycles, preprint.

%H Alois P. Heinz, <a href="/A057693/b057693.txt">Table of n, a(n) for n = 0..300</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, 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.

%H Dennis P. Walsh, <a href="http://www.mtsu.edu/~dwalsh/3cycles.gif">Derivation of the sequence</a>

%F a(n) = sum(binomial((n, 3 * j) * (3 * j)! * (1/3)^j/j! * sum(binomial(n-3 * j, 2 * k) * (2 * k)! * (1/2)^k/k!, k=0..floor((n-3 * j)/2)), j=0..floor(n/3)))

%F E.g.f.: exp( x + (x^2)/2 + (x^3)/3 ). Replacing 3 by "length k or less" in the definition of the sequence the E.g.f. is exp( x + (x^2)/2 + ... + (x^k)/k ). - Sharon Sela (sharonsela(AT)hotmail.com), May 16 2002

%F a(n) = a(n-1)+(n-1)*a(n-2)+(n-1)(n-2)*a(n-3). Generally, for n-permutations that have only cycles of length k or less the recurrence is: a(n)=Sum_i=0...k-1;P(n-1,i)*a(n-i-1) where P(x,i) is the falling factorial. - _Geoffrey Critzer_, May 23 2009

%F a(n) ~ n^(2*n/3)*exp(-2*n/3-5/18+5/6*n^(1/3)+1/2*n^(2/3))/sqrt(3) * (1 + 31/(324*n^(1/3)) + 302669/(1049760*n^(2/3))). - _Vaclav Kotesovec_, Aug 15 2013

%e For example, a(4)=18 since there are 6 permutations with cycles of length 4 to exclude from the 24 permutations on 4 letters, namely (1 2 3 4), (1 2 4 3), (1 3 2 4), (1 3 4 2), (1 4 2 3) and (1 4 3 2).

%p a:= proc(n) option remember; `if`(n<3, n!,

%p a(n-1) +(n-1)*a(n-2) +(n-1)*(n-2)*a(n-3))

%p end:

%p seq(a(n), n=0..30); # _Alois P. Heinz_, Jun 06 2013

%t nn=20;Range[0,nn]!CoefficientList[Series[Exp[ x + x^2/2 + x^3/3],{x,0,nn}],x] (* _Geoffrey Critzer_, Oct 28 2012 *)

%Y Cf. A000085, A070945-A070947.

%K nonn

%O 0,3

%A _Dennis P. Walsh_, Oct 20 2000

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 06:34 EDT 2024. Contains 371265 sequences. (Running on oeis4.)