A158243 -id:A158243 - cp's OEIS frontend

A038205 Number of derangements of n where minimal cycle size is at least 3.

1, 0, 0, 2, 6, 24, 160, 1140, 8988, 80864, 809856, 8907480, 106877320, 1389428832, 19452141696, 291781655984, 4668504894480, 79364592318720, 1428562679845888, 27142690734936864, 542853814536802656, 11399930109077490560, 250798462399300784640

Offset: 0

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

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.

			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.

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).

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.
Sergi Elizalde and Emeric Deutsch, The degree of asymmetry of a sequence, Enum. Combinat. Applic. 2 (2022) no 1 #S2R7, P(0,0,1,x).
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).

Cf. A000166, A047865, A158243.

m:=30; R:=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

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

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 *)

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

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

Definition corrected by Brendan McKay, Jun 02 2007

A348075 Triangular array read by rows: T(n,k) is the number of derangements whose shortest cycle has exactly k nodes; n >= 1, 1 <= k <= n.

Original entry on oeis.org

0, 0, 1, 0, 0, 2, 0, 3, 0, 6, 0, 20, 0, 0, 24, 0, 105, 40, 0, 0, 120, 0, 714, 420, 0, 0, 0, 720, 0, 5845, 2688, 1260, 0, 0, 0, 5040, 0, 52632, 22400, 18144, 0, 0, 0, 0, 40320, 0, 525105, 223200, 151200, 72576, 0, 0, 0, 0, 362880, 0, 5777090, 2522520, 1425600, 1330560, 0, 0, 0, 0, 0, 3628800

Offset: 1

Steven Finch, Sep 27 2021

For the statistic "length of the longest cycle", see A211871.

			Triangle begins:
  0;
  0,     1;
  0,     0,     2;
  0,     3,     0,     6;
  0,    20,     0,     0,   24;
  0,   105,    40,     0,    0,  120;
  0,   714,   420,     0,    0,    0,  720;
  0,  5845,  2688,  1260,    0,    0,    0, 5040;
  0, 52632, 22400, 18144,    0,    0,    0,    0, 40320;
  ...

Steven Finch, Permute, Graph, Map, Derange, arXiv:2111.05720 [math.CO], 2021.
D. Panario and B. Richmond, Exact largest and smallest size of components, Algorithmica, 31 (2001), 413-432.

Row sums give A000166, n >= 1.
Right border gives A000142.
Column 1 gives A000004.
Column 2 gives A158243.
Cf. A145877, A211871.

b:= proc(n, m) option remember; `if`(n=0, x^m, add((j-1)!*
      b(n-j, min(m, j))*binomial(n-1, j-1), j=2..n))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=1..n))(b(n$2)):
seq(T(n), n=1..12);  # Alois P. Heinz, Sep 27 2021

b[n_, m_] := b[n, m] = If[n == 0, x^m, Sum[(j - 1)!*
     b[n - j, Min[m, j]]*Binomial[n - 1, j - 1], {j, 2, n}]];
T[n_] := If[n == 1, {0}, CoefficientList[b[n, n], x] // Rest];
Table[T[n], {n, 1, 12}] // Flatten (* Jean-François Alcover, Oct 03 2021, after Alois P. Heinz *)

T(n,n) = A000142(n-1), n >= 2.
T(n,2) = A158243(n), n >= 2.
T(n,k) = A145877(n,k) for k >= 2.

cp's OEIS Frontend

A038205 Number of derangements of n where minimal cycle size is at least 3.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

Extensions