A370947 Number of partitions of [n] whose singletons sum to n.

1, 1, 0, 1, 2, 6, 20, 78, 307, 1486, 6974, 38584, 212268, 1321886, 8186322, 57015161, 391153290, 2976480926, 22534577137, 185638964675, 1522358748758, 13558705354828, 119620910388056, 1137343427864934, 10770667246889494, 108819371313460263, 1095389086585963202

Offset: 0

Author

Alois P. Heinz, Mar 06 2024

Keywords

• nonn

Examples

			a(0) = 1: the empty partition.
a(1) = 1: 1.
a(3) = 1: 12|3.
a(4) = 2: 123|4, 1|24|3.
a(5) = 6: 1234|5, 12|34|5, 13|24|5, 14|23|5, 1|235|4, 145|2|3.
a(6) = 20: 12345|6, 123|45|6, 124|35|6, 125|34|6, 12|345|6, 134|25|6, 135|24|6, 13|245|6, 1356|2|4, 13|2|4|56, 145|23|6, 14|235|6, 15|234|6, 1|2346|5, 1|23|46|5, 1|24|36|5, 1|26|34|5, 15|2|36|4, 16|2|35|4, 1|2|3|456.
		

Links

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

Crossrefs

Main diagonal of A370945.

Cf. A000009, A000110, A000296.

Programs

Maple

h:= proc(n) option remember; `if`(n=0, 1,
      add(h(n-j)*binomial(n-1, j-1), j=2..n))
    end:
b:= proc(n, i, m) option remember; `if`(n>i*(i+1)/2, 0,
     `if`(n=0, h(m), b(n, i-1, m)+b(n-i, min(n-i, i-1), m-1)))
    end:
a:= n-> b(n$3):
seq(a(n), n=0..26);

Mathematica

h[n_] := h[n] = If[n == 0, 1, Sum[h[n-j]*Binomial[n-1, j-1], {j, 2, n}]];
b[n_, i_, m_] := b[n, i, m] = If[n > i*(i + 1)/2, 0, If[n == 0, h[m], b[n, i - 1, m] + b[n - i, Min[n - i, i - 1], m - 1]]];
a[n_] := b[n, n, n];
Table[a[n], {n, 0, 26}] (* Jean-François Alcover, Mar 08 2024, after Alois P. Heinz *)

Formula

a(n) = A370945(n,n).