0,4

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.

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.

H. S. Wilf, Generatingfunctionology, 2nd edn., Academic Press, NY, 1994, p. 176, Eq. 5.2.9 (q=2).

a(n) = Sum C(n-1, i-1)(i-1)!a(n-i), i = 3 ... n. E.g.f.: exp(-x-x^2/2)/(1-x).

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.

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

Cf. A047865, A000166.

Sequence in context: A013010 A009608 A012715 this_sequence A012361 A121773 A012711

Adjacent sequences: A038202 A038203 A038204 this_sequence A038206 A038207 A038208

nonn,easy,nice

Charles G. Moore (cmoore(AT)microsoft.com), njas

Definition corrected by Brendan McKay, Jun 02 2007