A275309 Number of set partitions of [n] with decreasing block sizes.

1, 1, 1, 3, 4, 11, 36, 82, 239, 821, 3742, 10328, 42934, 156070, 729249, 4025361, 15032099, 68746675, 334541624, 1645575386, 9104991312, 65010298257, 282768687257, 1616844660914, 8660050947383, 53262316928024, 309119883729116, 2185141720645817

Offset

0,4

Links

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

Wikipedia, Partition of a set

Example

a(3) = 3: 123, 12|3, 13|2.
a(4) = 4: 1234, 123|4, 124|3, 134|2.
a(5) = 11: 12345, 1234|5, 1235|4, 123|45, 1245|3, 124|35, 125|34, 1345|2, 134|25, 135|24, 145|23.

Maple

b:= proc(n, i) option remember;
      `if`(n>i*(i+1)/2, 0, `if`(n=0, 1, b(n, i-1)+
      `if`(i>n, 0, b(n-i, i-1)*binomial(n-1, i-1))))
    end:
a:= n-> b(n$2):
seq(a(n), n=0..35);

Mathematica

b[n_, i_] := b[n, i] = If[n > i*(i + 1)/2, 0, If[n == 0, 1, b[n, i - 1] +  If[i > n, 0, b[n - i, i - 1]*Binomial[n - 1, i - 1]]]]; a[n_] := b[n, n]; Table[a[n], {n, 0, 35}] (* Jean-François Alcover, Jan 21 2017, translated from Maple *)

Crossrefs

Cf. A007837, A038041, A275310, A275311, A275312, A275313, A286073.

Sequence in context: A038559 A242044 A344263 * A119042 A042273 A179167

Adjacent sequences: A275306 A275307 A275308 * A275310 A275311 A275312

Keyword

nonn

Author

Alois P. Heinz, Jul 22 2016

Status

approved