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
Examples
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, ...
Links
- Alois P. Heinz, Antidiagonals n = 0..34, flattened
- Wikipedia, Partition of a set
Crossrefs
Programs
-
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 *)
Formula
A(n,k) = Sum_{j=0..k} A287640(n,j).