A211871 -id:A211871 - cp's OEIS frontend

A211880 Number of permutations of n elements with no fixed points and largest cycle of length 3.

0, 0, 0, 2, 0, 20, 40, 210, 1120, 4760, 25200, 157850, 800800, 5345340, 35035000, 222472250, 1648046400, 12000388400, 88529240800, 720929459250, 5786188408000, 48072795270500, 424300329453000, 3731123025279650, 34083741984292000, 323768324084205000

Offset: 0

Alois P. Heinz, Feb 13 2013

nonn

a(n) = A055814(n) - A123023(n). - Vaclav Kotesovec, Oct 09 2013

			a(3) = 2: (2,3,1), (3,1,2).

Alois P. Heinz, Table of n, a(n) for n = 0..250

Column k=3 of A211871.

Cf. A055814, A123023.

egf:= (exp(x^3/3)-1)*exp(x^2/2):
a:= n-> n! *coeff(series(egf, x, n+1), x, n):
seq(a(n), n=0..30);

A[n_, k_] := A[n, k] = If[n < 0, 0, If[n == 0, 1,
     Sum[Product[n - i, {i, 1, j - 1}] A[n - j, k], {j, 2, k}]]];
T[n_, k_] := A[n, k] - If[k == 0, 0, A[n, k - 1]];
a[n_] := T[n, 3];
Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Sep 03 2021, after Alois P. Heinz in A211871 *)

E.g.f.: (exp(x^3/3)-1) * exp(x^2/2).

Recurrence: (n-3)*a(n) = (n-1)*(2*n-5)*a(n-2) + (n-3)*(n-2)*(n-1)*a(n-3) - (n-3)*(n-2)*(n-1)*a(n-4) - (n-4)*(n-3)*(n-2)*(n-1)*a(n-5). - Vaclav Kotesovec, Oct 09 2013

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

A211880 Number of permutations of n elements with no fixed points and largest cycle of length 3.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula