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,10

Comments

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)

Links

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.

Formula

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.

Example

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

Maple

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

Mathematica

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

Crossrefs

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.

Sequence in context: A245492 A298203 A298209 * A194586 A288437 A287736

Adjacent sequences: A211868 A211869 A211870 * A211872 A211873 A211874

Keyword

nonn,tabl

Author

Alois P. Heinz, Feb 12 2013

Status

approved