A364967 Number T(n,k) of permutations of [n] for which the difference between the longest and the shortest cycle length is k; triangle T(n,k), n>=0, 0<=k<=max(0,n-2), read by rows.

1, 1, 2, 3, 3, 10, 6, 8, 25, 45, 20, 30, 176, 60, 250, 90, 144, 721, 861, 770, 1344, 504, 840, 6406, 1778, 7980, 6300, 8736, 3360, 5760, 42561, 23283, 38808, 75348, 45360, 66240, 25920, 45360, 436402, 84150, 363680, 456120, 708048, 378000, 572400, 226800, 403200

Offset: 0

Author

Alois P. Heinz, Aug 14 2023

Keywords

• nonn
• tabf

Comments

T(0,0) = 1 by convention.

Examples

			T(4,0) = 10: (1)(2)(3)(4), (12)(34), (13)(24), (14)(23), (1234), (1243), (1324), (1342), (1423), (1432).
T(4,1) = 6: (1)(2)(34), (1)(23)(4), (1)(24)(3), (12)(3)(4), (13)(2)(4), (14)(2)(3).
T(4,2) = 8: (1)(234), (1)(243), (123)(4), (132)(4), (124)(3), (142)(3), (134)(2), (143)(2).
Triangle T(n,k) begins:
      1;
      1;
      2;
      3,     3;
     10,     6,     8;
     25,    45,    20,    30;
    176,    60,   250,    90,   144;
    721,   861,   770,  1344,   504,   840;
   6406,  1778,  7980,  6300,  8736,  3360,  5760;
  42561, 23283, 38808, 75348, 45360, 66240, 25920, 45360;
  ...
		

Links

• Alois P. Heinz, Rows n = 0..150, flattened
• Wikipedia, Permutation

Crossrefs

Row sums give A000142.

Column k=0 gives A005225 (for n>=1).

T(n+1,n-1) gives A001048(n) (for n>=1).

Cf. A126074, A145877, A364971, A365229.

Programs

Maple

b:= proc(n, l, m) option remember; `if`(n=0, x^(m-l), add(
     b(n-j, min(l, j), max(m, j))*binomial(n-1, j-1)*(j-1)!, j=1..n))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n$2, 0)):
seq(T(n), n=0..12);

Mathematica

b[n_, l_, m_] := b[n, l, m] = If[n == 0, x^(m - l), Sum[b[n - j, Min[l, j], Max[m, j]]*Binomial[n - 1, j - 1]*(j - 1)!, {j, 1, n}]];
T[n_] := CoefficientList[b[n, n, 0], x];
Table[T[n], {n, 0, 12}] // Flatten (* Jean-François Alcover, Dec 08 2023, after Alois P. Heinz *)

Formula

T(n,k) == 0 (mod k!).

Sum_{k=0..max(0,n-2)} T(n,k)/k! = A365229(n).