A287640 Number T(n,k) of set partitions of [n], where k is minimal such that for all j in [n]: j is member of block b implies b = 1 or at least one of j-1, ..., j-k is member of a block >= b-1; triangle T(n,k), n >= 0, 0 <= k <= max(floor(n/2), n-2), read by rows.

1, 1, 1, 1, 1, 4, 1, 13, 1, 1, 41, 9, 1, 1, 131, 59, 11, 1, 1, 428, 344, 88, 15, 1, 1, 1429, 1906, 634, 146, 23, 1, 1, 4861, 10345, 4389, 1231, 280, 39, 1, 1, 16795, 55901, 30006, 9835, 2763, 602, 71, 1, 1, 58785, 303661, 205420, 77178, 25014, 6967, 1408, 135, 1

Offset

0,6

Links

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

Wikipedia, Partition of a set

Formula

T(n,k) = A287641(n,k) - A287641(n,k-1) for k>0, T(n,0) = 1.

T(n+4,n+1) = A168415(n) for n>0.

Example

T(4,0) = 1: 1234.
T(4,1) = 13: 123|4, 124|3, 12|34, 12|3|4, 134|2, 13|24, 14|23, 1|234, 1|23|4, 14|2|3, 1|24|3, 1|2|34, 1|2|3|4.
T(4,2) = 1: 13|2|4.
T(5,2) = 9: 124|3|5, 135|2|4, 13|25|4, 13|2|45, 13|2|4|5, 14|23|5, 14|2|35, 14|2|3|5, 1|24|3|5.
T(6,3) = 11: 1245|3|6, 1346|2|5, 134|26|5, 134|2|56, 134|2|5|6, 145|23|6, 145|2|36, 145|2|3|6, 14|25|3|6, 15|24|3|6, 1|245|3|6.
T(6,4) = 1: 1345|2|6.
T(7,4) = 15: 12456|3|7, 13457|2|6, 1345|27|6, 1345|2|67, 1345|2|6|7, 1456|23|7, 1456|2|37, 1456|2|3|7, 145|26|3|7, 146|25|3|7, 14|256|3|7, 156|24|3|7, 15|246|3|7, 16|245|3|7, 1|2456|3|7.
Triangle T(n,k) begins:
  1;
  1;
  1,    1;
  1,    4;
  1,   13,     1;
  1,   41,     9,    1;
  1,  131,    59,   11,    1;
  1,  428,   344,   88,   15,   1;
  1, 1429,  1906,  634,  146,  23,  1;
  1, 4861, 10345, 4389, 1231, 280, 39, 1;
  ...

Maple

b:= proc(n, l) option remember; `if`(n=0 or l=[], 1, add(b(n-1,
      [seq(max(l[i], j), i=2..nops(l)), j]), j=1..l[1]+1))
    end:
T:= (n, k)-> `if`(k=0, 1, b(n, [0$k])-b(n, [0$k-1])):
seq(seq(T(n, k), k=0..max(n/2, n-2)), n=0..12);

Mathematica

b[n_, l_] := b[n, l] = If[n == 0 || l == {}, 1, Sum[b[n-1, Append[Table[ Max[l[[i]], j], {i, 2, Length[l]}], j]], {j, 1, l[[1]] + 1}]];
T[n_, k_] := If[k == 0, 1, b[n, Table[0, k]] - b[n, Table[0, k - 1]]];
Table[T[n, k], {n, 0, 12}, { k, 0, Max[n/2, n - 2]}] // Flatten (* Jean-François Alcover, May 22 2018, translated from Maple *)

Crossrefs

Columns k=0-1 give: A000012, A001453.

Row sums give A000110.

Cf. A168415, A287213, A287215, A287416, A287641.

Sequence in context: A135704 A373394 A002564 * A322078 A019428 A303547

Adjacent sequences: A287637 A287638 A287639 * A287641 A287642 A287643

Keyword

nonn,tabf

Author

Alois P. Heinz, May 28 2017

Status

approved