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

Comments

T(0,0) = 1 by convention.

Links

Alois P. Heinz, Rows n = 0..150, flattened

Wikipedia, Permutation

Formula

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

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

Example

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

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

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.

Sequence in context: A371567 A110042 A306101 * A337432 A123027 A100652

Adjacent sequences: A364964 A364965 A364966 * A364968 A364969 A364970

Keyword

nonn,tabf

Author

Alois P. Heinz, Aug 14 2023

Status

approved