login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Please make a donation (tax deductible in USA) to keep the OEIS running. Over 5000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".

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. 9
1, 1, 2, 6, 18, 66, 276, 1212, 5916, 31068, 171576, 1014696, 6319512, 41143896, 281590128, 2007755856, 14871825936, 114577550352, 913508184096, 7526682826848, 64068860545056, 561735627038496, 5068388485760832, 47026385852423616, 447837548306401728 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

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))

REFERENCES

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

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..300

I. Mezo, Periodicity of the last digits of some combinatorial sequences, arXiv preprint arXiv:1308.1637, 2013

R. Petuchovas, Asymptotic analysis of the cyclic structure of permutations, arXiv:1611.02934 [math.CO], p. 6, 2016.

Dennis P. Walsh, Derivation of the sequence

FORMULA

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)))

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

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

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

EXAMPLE

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).

MAPLE

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

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

    end:

seq(a(n), n=0..30);  # Alois P. Heinz, Jun 06 2013

MATHEMATICA

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

CROSSREFS

Cf. A000085, A070945-A070947.

Sequence in context: A150076 A150077 A173385 * A053496 A079577 A150078

Adjacent sequences:  A057690 A057691 A057692 * A057694 A057695 A057696

KEYWORD

nonn,changed

AUTHOR

Dennis P. Walsh, Oct 20 2000

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy .

Last modified December 11 03:15 EST 2016. Contains 279034 sequences.