|
| |
|
|
A057693
|
|
Number of permutations on n letters that have only cycles of length 3 or less.
|
|
6
| |
|
|
1, 2, 6, 18, 66, 276, 1212, 5916, 31068, 171576, 1014696, 6319512, 41143896, 281590128, 2007755856, 14871825936, 114577550352, 913508184096, 7526682826848, 64068860545056, 561735627038496, 5068388485760832
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,2
|
|
|
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
| 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. [From Geoffrey Critzer (critzer.geoffrey(AT)usd443.org), May 23 2009]
|
|
|
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).
|
|
|
CROSSREFS
| Cf. A000085, A070945-A070947.
Sequence in context: A150076 A150077 A173385 * A053496 A079577 A150078
Adjacent sequences: A057690 A057691 A057692 * A057694 A057695 A057696
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| Dennis P. Walsh (dwalsh(AT)mtsu.edu), Oct 20 2000
|
| |
|
|
