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,5

Links

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

Wikipedia, Partition of a set

Formula

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

Example

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.

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

Crossrefs

Main diagonal of A370945.

Cf. A000009, A000110, A000296.

Sequence in context: A150178 A150179 A150180 * A150181 A150182 A098469

Adjacent sequences: A370944 A370945 A370946 * A370948 A370949 A370950

Keyword

nonn

Author

Alois P. Heinz, Mar 06 2024

Status

approved