|
%I #75 Feb 13 2023 07:58:18
%S 1,0,0,2,6,24,160,1140,8988,80864,809856,8907480,106877320,1389428832,
%T 19452141696,291781655984,4668504894480,79364592318720,
%U 1428562679845888,27142690734936864,542853814536802656,11399930109077490560,250798462399300784640
%N Number of derangements of n where minimal cycle size is at least 3.
%C Permutations with no cycles of length 1 or 2.
%C 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.
%D G. Paquin, Dénombrement de multigraphes enrichis, Mémoire, Math. Dept., Univ. Québec à Montréal, 2004.
%D H. S. Wilf, Generatingfunctionology, Academic Press, NY, 1990, p. 147, Eq. 5.2.9 (q=2).
%H Alois P. Heinz, <a href="/A038205/b038205.txt">Table of n, a(n) for n = 0..200</a> (first 51 terms from Arie Bos)
%H Joerg Arndt, <a href="http://jjj.de/pub/arndt-rand-perm-thesis.pdf">Generating Random Permutations</a>, PhD thesis, Australian National University, Canberra, Australia, (2010).
%H Poly H. da Silva, Arash Jamshidpey, and Simon Tavaré, <a href="https://arxiv.org/abs/2006.04840">Random derangements and the Ewens Sampling Formula</a>, arXiv:2006.04840 [math.PR], 2020.
%H J. East and R. D. Gray, <a href="http://arxiv.org/abs/1404.2359">Idempotent generators in finite partition monoids and related semigroups</a>, arXiv preprint arXiv:1404.2359, 2014. See Table 4.
%H Vladimir Kruchinin, <a href="http://arxiv.org/abs/1009.2565">Composition of ordinary generating functions</a>, arXiv:1009.2565 [math.CO], 2010.
%H G. Paquin, <a href="/A038205/a038205.pdf">Dénombrement de multigraphes enrichis</a>, Mémoire, Math. Dept., Univ. Québec à Montréal, 2004. [Cached copy, with permission]
%H H. S. Wilf, <a href="http://www.math.upenn.edu/~wilf/DownldGF.html">Generatingfunctionology</a>, 2nd edn., Academic Press, NY, 1994, p. 176, Eq. 5.2.9 (q=2).
%F a(n) = Sum_{i=3..n} binomial(n-1,i-1) * (i-1)! * a(n-i).
%F E.g.f.: exp(-x-x^2/2)/(1-x) = exp( Sum_{k>2} x^k / k ).
%F 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
%F a(n) = A000166(n) - A158243(n). - _Paul Weisenhorn_, May 29 2010
%F a(n) = (n-1)*a(n-1) + (n-1)*(n-2)*a(n-3). - _Peter Bala_, Apr 18 2012
%F a(n) ~ n! * exp(-3/2). - _Vaclav Kotesovec_, Jul 30 2013
%e 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.
%p with(combstruct): ZL2:=[S,{S=Set(Cycle(Z,card>2))},labeled] :seq(count(ZL2,size=n), n=0..21); # _Zerinvary Lajos_, Sep 26 2007
%p 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
%p 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
%t 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_ *)
%o (PARI) x='x+O('x^30); Vec(serlaplace(exp(-x-x^2/2)/(1-x))) \\ _G. C. Greubel_, Jun 25 2018
%o (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
%Y Cf. A000166, A047865, A158243.
%K nonn,easy,nice
%O 0,4
%A _Charles G. Moore_, _N. J. A. Sloane_
%E Definition corrected by _Brendan McKay_, Jun 02 2007
|
