A370947 - OEIS

%I #17 Mar 08 2024 07:12:25

%S 1,1,0,1,2,6,20,78,307,1486,6974,38584,212268,1321886,8186322,

%T 57015161,391153290,2976480926,22534577137,185638964675,1522358748758,

%U 13558705354828,119620910388056,1137343427864934,10770667246889494,108819371313460263,1095389086585963202

%N Number of partitions of [n] whose singletons sum to n.

%H Alois P. Heinz, <a href="/A370947/b370947.txt">Table of n, a(n) for n = 0..577</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Partition_of_a_set">Partition of a set</a>

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

%e a(0) = 1: the empty partition.

%e a(1) = 1: 1.

%e a(3) = 1: 12|3.

%e a(4) = 2: 123|4, 1|24|3.

%e a(5) = 6: 1234|5, 12|34|5, 13|24|5, 14|23|5, 1|235|4, 145|2|3.

%e 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.

%p h:= proc(n) option remember; `if`(n=0, 1,

%p       add(h(n-j)*binomial(n-1, j-1), j=2..n))

%p     end:

%p b:= proc(n, i, m) option remember; `if`(n>i*(i+1)/2, 0,

%p      `if`(n=0, h(m), b(n, i-1, m)+b(n-i, min(n-i, i-1), m-1)))

%p     end:

%p a:= n-> b(n$3):

%p seq(a(n), n=0..26);

%t h[n_] := h[n] = If[n == 0, 1, Sum[h[n-j]*Binomial[n-1, j-1], {j, 2, n}]];

%t 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]]];

%t a[n_] := b[n, n, n];

%t Table[a[n], {n, 0, 26}] (* _Jean-François Alcover_, Mar 08 2024, after _Alois P. Heinz_ *)

%Y Main diagonal of A370945.

%Y Cf. A000009, A000110, A000296.

%K nonn

%O 0,5

%A _Alois P. Heinz_, Mar 06 2024