login
Number T(n,k) of ordered set partitions of [n] where k is minimal such that for each block b the smallest integer interval containing b has at most k elements; triangle T(n,k), n>=0, 0<=k<=n, read by rows.
14

%I #18 Feb 17 2023 11:07:14

%S 1,0,1,0,2,1,0,6,4,3,0,24,20,18,13,0,120,114,118,114,75,0,720,750,878,

%T 924,870,541,0,5040,5616,7224,8152,8760,7818,4683,0,40320,47304,65514,

%U 79682,90084,94560,81078,47293,0,362880,443400,652446,845874,998560,1135776,1148016,954474,545835

%N Number T(n,k) of ordered set partitions of [n] where k is minimal such that for each block b the smallest integer interval containing b has at most k elements; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

%H Alois P. Heinz, <a href="/A276891/b276891.txt">Rows n = 0..21, flattened</a>

%F T(n,k) = A276890(n,k) - A276890(n,k-1) for k>0, T(n,0) = A000007(n).

%e Triangle T(n,k) begins:

%e 1;

%e 0, 1;

%e 0, 2, 1;

%e 0, 6, 4, 3;

%e 0, 24, 20, 18, 13;

%e 0, 120, 114, 118, 114, 75;

%e 0, 720, 750, 878, 924, 870, 541;

%e 0, 5040, 5616, 7224, 8152, 8760, 7818, 4683;

%e 0, 40320, 47304, 65514, 79682, 90084, 94560, 81078, 47293;

%e ...

%p b:= proc(n, m, l) option remember; `if`(n=0, m!,

%p add(b(n-1, max(m, j), [subsop(1=NULL, l)[],

%p `if`(j<=m, 0, j)]), j={l[], m+1} minus {0}))

%p end:

%p A:= (n, k)-> `if`(k=0, `if`(n=0, 1, 0),

%p `if`(k=1, n!, b(n, 0, [0$(k-1)]))):

%p T:= (n, k)-> A(n, k) -`if`(k=0, 0, A(n, k-1)):

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

%t b[n_, m_, l_List] := b[n, m, l] = If[n == 0, m!, Sum[b[n - 1, Max[m, j], Append[ReplacePart[l, 1 -> Nothing], If[j <= m, 0, j]]], {j, Append[l, m + 1] ~Complement~ {0}}]]; A[n_, k_] := If[k == 0, If[n == 0, 1, 0], If[k == 1, n!, b[n, 0, Array[0 &, k - 1]]]]; T [n_, k_] := A[n, k] - If[k == 0, 0, A[n, k - 1]]; Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* _Jean-François Alcover_, Feb 04 2017, translated from Maple *)

%Y Columns k=0-10 give: A000007, A000142 (for n>0), A320615, A320616, A320617, A320618, A320619, A320620, A320621, A320622, A320623.

%Y Row sums give: A000670.

%Y Main diagonal gives A000670(n-1) for n>0.

%Y T(2n,n) gives A276892.

%Y Cf. A276727, A276890.

%K nonn,tabl

%O 0,5

%A _Alois P. Heinz_, Sep 21 2016