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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A038205 Number of derangements of n where minimal cycle size is at least 3. 100
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; text; 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

G. Paquin, Dénombrement de multigraphes enrichis, Mémoire, Math. Dept., Univ. Québec à Montréal, 2004.

H. S. Wilf, Generatingfunctionology, Academic Press, NY, 1990, p. 147, Eq. 5.2.9 (q=2).

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..200 (first 51 terms from Arie Bos)

Joerg Arndt, Generating Random Permutations, PhD thesis, Australian National University, Canberra, Australia, (2010).

J. East, R. D. Gray, Idempotent generators in finite partition monoids and related semigroups, arXiv preprint arXiv:1404.2359, 2014. See Table 4.

G. Paquin, Dénombrement de multigraphes enrichis, Mémoire, Math. Dept., Univ. Québec à Montréal, 2004. [Cached copy, with permission]

Kruchinin Vladimir Victorovich, Composition of ordinary generating functions, arXiv:1009.2565

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

FORMULA

a(n) = Sum_{i=3..n} binomial(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. - Vladimir Kruchinin, Feb 01 2011

a(n) = A000166(n) - A158243(n). - Paul Weisenhorn, May 29 2010

a(n) = (n-1)*a(n-1) + (n-1)*(n-2)*a(n-3). - Peter Bala, Apr 18 2012

a(n) ~ n! * exp(-3/2). - Vaclav Kotesovec, Jul 30 2013

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

with(combstruct): ZL2:=[S, {S=Set(Cycle(Z, card>2))}, labeled] :seq(count(ZL2, size=n), n=0..21); # Zerinvary Lajos, 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, Oct 02 2007

G:= exp(-x-x^2/2)/(1-x): Gser:=series(G, x, 26): a:= n-> n!*coeff(Gser, x, n): seq(a(n), n=0..25); # Paul Weisenhorn, May 29 2010

MATHEMATICA

max = 21; f[x_] := Exp[-x - x^2/2]/(1 - x); CoefficientList[ Series[ f[x], {x, 0, max}], x]*Range[0, max]! (* Jean-François Alcover, Dec 07 2011, after Vladimir Kruchinin *)

PROG

(PARI) x='x+O('x^30); Vec(serlaplace(exp(-x-x^2/2)/(1-x))) \\ G. C. Greubel, Jun 25 2018

(MAGMA) m:=30; R<x>:=PowerSeriesRing(Rationals(), m); b:=Coefficients(R!(Exp(-x-x^2/2)/(1-x))); [Factorial(n-1)*b[n]: n in [1..m]]; // G. C. Greubel, Jun 25 2018

CROSSREFS

Cf. A000166, A047865, A158243.

Sequence in context: A275955 A009608 A012715 * A012361 A308111 A121773

Adjacent sequences:  A038202 A038203 A038204 * A038206 A038207 A038208

KEYWORD

nonn,easy,nice

AUTHOR

Charles G. Moore, N. J. A. Sloane

EXTENSIONS

Definition corrected by Brendan McKay, Jun 02 2007

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
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 19 04:40 EDT 2019. Contains 328211 sequences. (Running on oeis4.)