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).
Poly H. da Silva, Arash Jamshidpey, and Simon Tavaré, Random derangements and the Ewens Sampling Formula, arXiv:2006.04840 [math.PR], 2020.
J. East and R. D. Gray, Idempotent generators in finite partition monoids and related semigroups, arXiv preprint arXiv:1404.2359, 2014. See Table 4.
Vladimir Kruchinin, Composition of ordinary generating functions, arXiv:1009.2565 [math.CO], 2010.
G. Paquin, Dénombrement de multigraphes enrichis, Mémoire, Math. Dept., Univ. Québec à Montréal, 2004. [Cached copy, with permission]
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) = (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
KEYWORD
nonn,easy,nice
AUTHOR
EXTENSIONS
Definition corrected by Brendan McKay, Jun 02 2007
STATUS
approved