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

Author

Alois P. Heinz, Jul 22 2016

Keywords

• nonn

Examples

			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.
		

Links

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

Crossrefs

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

Programs

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 *)