A287667 Number 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-4 is member of a block >= b-1.

1, 1, 2, 5, 15, 52, 203, 876, 4116, 20827, 112538, 645045, 3900512, 24769152, 164546915, 1139818861, 8209631792, 61331709492, 474221335902, 3787741281763, 31199052157724, 264605708064825, 2307562757319104, 20666169125398768, 189855243829576499

Offset: 0

Author

Alois P. Heinz, May 29 2017

Keywords

• nonn

Examples

			a(7) = 876 = 877 - 1 = A000110(7) - 1 counts all set partitions of [7] except: 13456|2|7.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..90
• Wikipedia, Partition of a set

Crossrefs

Column k=4 of A287641.

Cf. A000110.

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-> b(n, [0$4]):
seq(a(n), n=0..26);

Mathematica

b[n_, l_] := b[n, l] = If[n == 0, 1, Sum[b[n - 1, Append[Table[Max[l[[i]], j], {i, 2, Length[l]}], j]], {j, 1, l[[1]] + 1}]];
a[n_] := b[n, Table[0, 4]];
Table[a[n], {n, 0, 26}] (* Jean-François Alcover, May 27 2018, from Maple *)

Formula

a(n) = A287641(n,4).

a(n) = A000110(n) for n <= 6.