A370946 Number of partitions of [n] whose non-singleton elements sum to n.

1, 0, 0, 1, 1, 2, 3, 4, 5, 7, 12, 14, 20, 26, 36, 54, 68, 90, 120, 157, 202, 296, 360, 480, 612, 803, 1006, 1317, 1764, 2198, 2821, 3592, 4552, 5754, 7269, 9074, 11990, 14646, 18586, 23112, 29208, 35972, 45277, 55584, 69350, 87881, 107609, 133068, 165038

Offset

0,6

Links

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

Wikipedia, Partition of a set

Formula

a(n) = A370945(n,n*(n-1)/2).

Example

a(0) = 1: the empty partition.
a(3) = 1: 12|3.
a(4) = 1: 13|2|4.
a(5) = 2: 1|23|4|5, 14|2|3|5.
a(6) = 3: 123|4|5|6, 1|24|3|5|6, 15|2|3|4|6.
a(7) = 4: 124|3|5|6|7, 1|2|34|5|6|7, 1|25|3|4|6|7, 16|2|3|4|5|7.
a(8) = 5: 125|3|4|6|7|8, 134|2|5|6|7|8, 1|2|35|4|6|7|8, 1|26|3|4|5|7|8, 17|2|3|4|5|6|8.
a(9) = 7: 126|3|4|5|7|8|9, 135|2|4|6|7|8|9, 1|234|5|6|7|8|9, 1|2|3|45|6|7|8|9, 1|2|36|4|5|7|8|9, 1|27|3|4|5|6|8|9, 18|2|3|4|5|6|7|9.
a(10) = 12: 1234|5|6|7|8|9|10, 12|34|5|6|7|8|9|10, 127|3|4|5|6|8|9|10, 13|24|5|6|7|8|9|10, 136|2|4|5|7|8|9|10, 14|23|5|6|7|8|9|10, 1|235|4|6|7|8|9|10, 145|2|3|6|7|8|9|10, 1|2|3|46|5|7|8|9|10, 1|2|37|4|5|6|8|9|10, 1|28|3|4|5|6|7|9|10, 19|2|3|4|5|6|7|8|10.

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

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, 0];
Table[a[n], {n, 0, 48}] (* Jean-François Alcover, Mar 08 2024, after Alois P. Heinz *)

Crossrefs

Cf. A161680, A370945.

Sequence in context: A324989 A015856 A174165 * A240732 A060437 A133428

Adjacent sequences: A370943 A370944 A370945 * A370947 A370948 A370949

Keyword

nonn

Author

Alois P. Heinz, Mar 06 2024

Status

approved