|
| |
|
|
A038205
|
|
Number of derangements of n where minimal cycle size is at least 3.
|
|
6
| |
|
|
1, 0, 0, 2, 6, 24, 160, 1140, 8988, 80864, 809856, 8907480, 106877320, 1389428832, 19452141696, 291781655984, 4668504894480, 79364592318720, 1428562679845888, 27142690734936864, 542853814536802656, 11399930109077490560
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,4
|
|
|
COMMENTS
| Permutations with no cycles of length 1 or 2.
Related to (and bounded by) "derangements" (A000166). Minimal cycle size 3 is interesting because of its physical analog. Consider a fully-connected network of n nodes where the objects stored at the nodes must derange but can't do so in such a way that any two objects would collide along the connecting "pipe" between their nodes.
|
|
|
REFERENCES
| H. S. Wilf, Generatingfunctionology, Academic Press, NY, 1990, p. 147, Eq. 5.2.9 (q=2).
G. Paquin, D\'enombrement de multigraphes enrichis, M\'emoire, Math. Dept., Univ. Qu\'ebec \`a Montr\'eal, 2004.
|
|
|
LINKS
| H. S. Wilf, Generatingfunctionology, 2nd edn., Academic Press, NY, 1994, p. 176, Eq. 5.2.9 (q=2).
Kruchinin Vladimir Victorovich, Composition of ordinary generating functions, arXiv:1009.2565
|
|
|
FORMULA
| a(n) = Sum_{i=3..n} C(n-1,i-1) * (i-1)! * a(n-i).
E.g.f.: exp(-x-x^2/2)/(1-x) = exp( Sum_{k>2} x^k / k ).
a(n) = n! * sum(m=1..n, sum(k=0..m, k!*(-1)^(m-k) *binomial(m,k) *sum(i=0..n-m, abs(stirling1(i+k,k)) *binomial(m-k,n-m-i) *2^(-n+m+i) /(i+k)!))/m!); a(0)=1. - From Vladimir Kruchinin (kru(AT)ie.tusur.ru), Feb 01 2011
a(n)=A000166(n)-A158243(n). [Weisenhorn Paul (weisenhorn-f.p(AT)online.de), May 29 2010]
|
|
|
EXAMPLE
| a(5) = 24 because, with a minimum cycle size of 3, the only way to derange all 5 elements is to have them move around in one large 5-cycle. The number of possible moves is (5-1)! = 4! = 24.
|
|
|
MAPLE
| ZL2:=[S, {S=Set(Cycle(Z, card>2))}, labeled] :seq(count(ZL2, size=n), n=0..21); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Sep 26 2007
with (combstruct):a:=proc(m) [ZZ, {ZZ=Set(Cycle(Z, card>m))}, labeled]; end: A038205:=a(2):seq(count(A038205, size=n), n=0..21); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Oct 02 2007
Contribution from Weisenhorn Paul (weisenhorn-f.p(AT)online.de), May 29 2010: (Start)
G:=exp(-z-z/2)/(1-z); Gser:=simplyfy(series(G, z, 0, 26);
for n from 0 to 25 do a(n):=n!*coeff(Gser, z, n): end do:
(End)
|
|
|
MATHEMATICA
| max = 21; f[x_] := Exp[-x - x^2/2]/(1 - x); CoefficientList[ Series[ f[x], {x, 0, max}], x]*Range[0, max]! (* From Jean-François Alcover, Dec 07 2011, after Vladimir Kruchinin *)
|
|
|
CROSSREFS
| Cf. A000166, A047865, A158243.
Sequence in context: A013010 A009608 A012715 * A012361 A121773 A012711
Adjacent sequences: A038202 A038203 A038204 * A038206 A038207 A038208
|
|
|
KEYWORD
| nonn,easy,nice
|
|
|
AUTHOR
| Charles G. Moore (cmoore(AT)microsoft.com), N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
EXTENSIONS
| Definition corrected by Brendan McKay, Jun 02 2007
|
| |
|
|
