login
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.
4

%I #34 Dec 08 2023 07:11:48

%S 1,1,2,3,3,10,6,8,25,45,20,30,176,60,250,90,144,721,861,770,1344,504,

%T 840,6406,1778,7980,6300,8736,3360,5760,42561,23283,38808,75348,45360,

%U 66240,25920,45360,436402,84150,363680,456120,708048,378000,572400,226800,403200

%N 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.

%C T(0,0) = 1 by convention.

%H Alois P. Heinz, <a href="/A364967/b364967.txt">Rows n = 0..150, flattened</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Permutation">Permutation</a>

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

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

%e T(4,0) = 10: (1)(2)(3)(4), (12)(34), (13)(24), (14)(23), (1234), (1243), (1324), (1342), (1423), (1432).

%e T(4,1) = 6: (1)(2)(34), (1)(23)(4), (1)(24)(3), (12)(3)(4), (13)(2)(4), (14)(2)(3).

%e T(4,2) = 8: (1)(234), (1)(243), (123)(4), (132)(4), (124)(3), (142)(3), (134)(2), (143)(2).

%e Triangle T(n,k) begins:

%e 1;

%e 1;

%e 2;

%e 3, 3;

%e 10, 6, 8;

%e 25, 45, 20, 30;

%e 176, 60, 250, 90, 144;

%e 721, 861, 770, 1344, 504, 840;

%e 6406, 1778, 7980, 6300, 8736, 3360, 5760;

%e 42561, 23283, 38808, 75348, 45360, 66240, 25920, 45360;

%e ...

%p b:= proc(n, l, m) option remember; `if`(n=0, x^(m-l), add(

%p b(n-j, min(l, j), max(m, j))*binomial(n-1, j-1)*(j-1)!, j=1..n))

%p end:

%p T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n$2, 0)):

%p seq(T(n), n=0..12);

%t 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 T[n_] := CoefficientList[b[n, n, 0], x];

%t Table[T[n], {n, 0, 12}] // Flatten (* _Jean-François Alcover_, Dec 08 2023, after _Alois P. Heinz_ *)

%Y Row sums give A000142.

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

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

%Y Cf. A126074, A145877, A364971, A365229.

%K nonn,tabf

%O 0,3

%A _Alois P. Heinz_, Aug 14 2023