A287672 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-9 is member of a block >= b-1.

1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213596, 27643917, 190873448, 1382311874, 10468191626, 82676728870, 679376431959, 5796059673820, 51241781683988, 468639956185787, 4426928995172738, 43131913020157751, 432877526792148982

Offset

0,3

Links

Alois P. Heinz, Table of n, a(n) for n = 0..30

Wikipedia, Partition of a set

Formula

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

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

Example

a(12) = 4213596 = 4213597 - 1 = A000110(12) - 1 counts all set partitions of [12] except: 13456789(10)(11)|2|(12).

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$9]):
seq(a(n), n=0..20);

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, 9]];
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, May 27 2018, from Maple *)

Crossrefs

Column k=9 of A287641.

Cf. A000110.

Sequence in context: A287589 A287282 A287260 * A203641 A192127 A287673

Adjacent sequences: A287669 A287670 A287671 * A287673 A287674 A287675

Keyword

nonn

Author

Alois P. Heinz, May 29 2017

Status

approved