A055814 -id:A055814 - cp's OEIS frontend

A211871 Number T(n,k) of permutations of n elements with no fixed points and largest cycle of length k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 0, 0, 0, 0, 1, 0, 0, 0, 2, 0, 0, 3, 0, 6, 0, 0, 0, 20, 0, 24, 0, 0, 15, 40, 90, 0, 120, 0, 0, 0, 210, 420, 504, 0, 720, 0, 0, 105, 1120, 2520, 2688, 3360, 0, 5040, 0, 0, 0, 4760, 15120, 27216, 20160, 25920, 0, 40320, 0, 0, 945, 25200, 126000, 193536, 226800, 172800, 226800, 0, 362880

Offset: 0

Alois P. Heinz, Feb 12 2013

From Steven Finch, Sep 27 2021: (Start)
A permutation without fixed points is called a derangement.
For the statistic "length of the smallest cycle", see A348075. (End)

			T(0,0) = 1: (), the empty permutation.
T(2,2) = 1: (2,1).
T(3,3) = 2: (2,3,1), (3,1,2).
T(4,2) = 3: (2,1,4,3), (3,4,1,2), (4,3,2,1).
T(4,4) = 6: (2,4,1,3), (2,3,4,1), (3,1,4,2), (3,4,2,1), (4,1,2,3), (4,3,1,2).
Triangle T(n,k) begins:
  1;
  0,  0;
  0,  0,   1;
  0,  0,   0,    2;
  0,  0,   3,    0,    6;
  0,  0,   0,   20,    0,   24;
  0,  0,  15,   40,   90,    0,  120;
  0,  0,   0,  210,  420,  504,    0, 720;
  0,  0, 105, 1120, 2520, 2688, 3360,   0, 5040;
  ...

Alois P. Heinz, Rows n = 0..140, flattened
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.

Columns k=0-3 give: A000007, A000004, A123023 for n>0, A211880.
Row sums give A000166.
Diagonal gives: A000142(n-1) for n>1.
T(n,0) + T(n,2) + T(n,3) gives A055814(n).
Cf. A348075.

A:= proc(n,k) option remember; `if`(n<0, 0, `if`(n=0, 1,
       add(mul(n-i, i=1..j-1)*A(n-j,k), j=2..k)))
    end:
T:= (n, k)-> A(n, k) -`if`(k=0,0,A(n, k-1)):
seq(seq(T(n,k), k=0..n), n=0..12);

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]];
Table[Table[T[n, k], {k, 0, n}], {n, 0, 12}] // Flatten (* Jean-François Alcover, Dec 27 2013, translated from Maple *)

E.g.f. of column k>1: (exp(x^k/k)-1) * exp(Sum_{j=2..k-1} x^j/j); e.g.f. of column k<=1: 1-k.

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

Original entry on oeis.org

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

cp's OEIS Frontend

A211871 Number T(n,k) of permutations of n elements with no fixed points and largest cycle of length k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula