A276727 Number T(n,k) of 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.
1, 0, 1, 0, 1, 1, 0, 1, 2, 2, 0, 1, 4, 5, 5, 0, 1, 7, 12, 17, 15, 0, 1, 12, 29, 45, 64, 52, 0, 1, 20, 66, 121, 201, 265, 203, 0, 1, 33, 145, 336, 585, 966, 1197, 877, 0, 1, 54, 315, 901, 1741, 3172, 4971, 5852, 4140, 0, 1, 88, 676, 2347, 5375, 10100, 18223, 27267, 30751, 21147
Offset: 0
Examples
T(4,1) = 1: 1|2|3|4. T(4,2) = 4: 12|34, 12|3|4, 1|23|4, 1|2|34. T(4,3) = 5: 123|4, 13|24, 13|2|4, 1|234, 1|24|3. T(4,4) = 5: 1234, 124|3, 134|2, 14|23, 14|2|3. T(5,4) = 17: 1234|5, 124|35, 124|3|5, 134|25, 134|2|5, 13|245, 13|25|4, 14|235, 14|23|5, 1|2345, 1|235|4, 14|25|3, 14|2|35, 14|2|3|5, 1|245|3, 1|25|34, 1|25|3|4. Triangle T(n,k) begins: 1; 0, 1; 0, 1, 1; 0, 1, 2, 2; 0, 1, 4, 5, 5; 0, 1, 7, 12, 17, 15; 0, 1, 12, 29, 45, 64, 52; 0, 1, 20, 66, 121, 201, 265, 203; 0, 1, 33, 145, 336, 585, 966, 1197, 877; ...
Links
- Alois P. Heinz, Rows n = 0..20, flattened
Crossrefs
Programs
-
Maple
b:= proc(n, m, l) option remember; `if`(n=0, 1, add(b(n-1, max(m, j), [subsop(1=NULL, l)[], `if`(j<=m, 0, j)]), j={l[], m+1} minus {0})) end: A:= (n, k)-> `if`(n=0, 1, `if`(k<2, k, b(n, 0, [0$(k-1)]))): 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
b[n_, m_, l_List] := b[n, m, l] = If[n == 0, 1, 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[n == 0, 1, If[k < 2, k, 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, 12}, { k, 0, n}] // Flatten (* Jean-François Alcover, Feb 04 2017, translated from Maple *)