A287641 Number A(n,k) of set partitions of [n] such that j is member of block b only if b = 1 or at least one of j-1, ..., j-k is member of a block >= b-1; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 5, 1, 1, 1, 2, 5, 14, 1, 1, 1, 2, 5, 15, 42, 1, 1, 1, 2, 5, 15, 51, 132, 1, 1, 1, 2, 5, 15, 52, 191, 429, 1, 1, 1, 2, 5, 15, 52, 202, 773, 1430, 1, 1, 1, 2, 5, 15, 52, 203, 861, 3336, 4862, 1, 1, 1, 2, 5, 15, 52, 203, 876, 3970, 15207, 16796, 1

Offset

0,9

Links

Alois P. Heinz, Antidiagonals n = 0..34, flattened

Wikipedia, Partition of a set

Formula

A(n,k) = Sum_{j=0..k} A287640(n,j).

Example

A(5,0) = 1: 12345.
A(5,1) = 42 = 52 - 10 = A000110(5) - 10 counts all set partitions of [5] except: 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, 134|2|5.
A(5,2) = 51 = 52 - 1 = A000110(5) - 1 counts all set partitions of [5] except: 134|2|5.
Square array A(n,k) begins:
  1,   1,   1,   1,   1,   1,   1,   1, ...
  1,   1,   1,   1,   1,   1,   1,   1, ...
  1,   2,   2,   2,   2,   2,   2,   2, ...
  1,   5,   5,   5,   5,   5,   5,   5, ...
  1,  14,  15,  15,  15,  15,  15,  15, ...
  1,  42,  51,  52,  52,  52,  52,  52, ...
  1, 132, 191, 202, 203, 203, 203, 203, ...
  1, 429, 773, 861, 876, 877, 877, 877, ...

Maple

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

Mathematica

b[0, _] = 1; b[n_, l_List] := b[n, l] = Sum[b[n - 1, Append[ Table[ Max[ l[[i]], j], {i, 2, Length[l]}], j]], {j, 1, l[[1]] + 1}];
A[n_, k_] := If[k == 0, 1, b[n, Table[0, k]]];
Table[A[n, d - n], {d, 0, 12}, {n, 0, d}] // Flatten (* Jean-François Alcover, Apr 30 2018, after Alois P. Heinz *)

Crossrefs

Columns k=0-10 give: A000012, A000108, A275605, A287666, A287667, A287668, A287669, A287670, A287671, A287672, A287673.

Main diagonal gives A000110.

Cf. A064645, A287214, A287216, A287417, A287640.

Sequence in context: A358273 A215894 A061545 * A265312 A241531 A362277

Adjacent sequences: A287638 A287639 A287640 * A287642 A287643 A287644

Keyword

nonn,tabl

Author

Alois P. Heinz, May 28 2017

Status

approved