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
Examples
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; ...
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.
Crossrefs
Programs
-
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 *)
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.
Comments