cp's OEIS Frontend

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

%I A370947 #17 Mar 08 2024 07:12:25
%S A370947 1,1,0,1,2,6,20,78,307,1486,6974,38584,212268,1321886,8186322,
%T A370947 57015161,391153290,2976480926,22534577137,185638964675,1522358748758,
%U A370947 13558705354828,119620910388056,1137343427864934,10770667246889494,108819371313460263,1095389086585963202
%N A370947 Number of partitions of [n] whose singletons sum to n.
%H A370947 Alois P. Heinz, <a href="/A370947/b370947.txt">Table of n, a(n) for n = 0..577</a>
%H A370947 Wikipedia, <a href="https://en.wikipedia.org/wiki/Partition_of_a_set">Partition of a set</a>
%F A370947 a(n) = A370945(n,n).
%e A370947 a(0) = 1: the empty partition.
%e A370947 a(1) = 1: 1.
%e A370947 a(3) = 1: 12|3.
%e A370947 a(4) = 2: 123|4, 1|24|3.
%e A370947 a(5) = 6: 1234|5, 12|34|5, 13|24|5, 14|23|5, 1|235|4, 145|2|3.
%e A370947 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 A370947 h:= proc(n) option remember; `if`(n=0, 1,
%p A370947       add(h(n-j)*binomial(n-1, j-1), j=2..n))
%p A370947     end:
%p A370947 b:= proc(n, i, m) option remember; `if`(n>i*(i+1)/2, 0,
%p A370947      `if`(n=0, h(m), b(n, i-1, m)+b(n-i, min(n-i, i-1), m-1)))
%p A370947     end:
%p A370947 a:= n-> b(n$3):
%p A370947 seq(a(n), n=0..26);
%t A370947 h[n_] := h[n] = If[n == 0, 1, Sum[h[n-j]*Binomial[n-1, j-1], {j, 2, n}]];
%t A370947 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 A370947 a[n_] := b[n, n, n];
%t A370947 Table[a[n], {n, 0, 26}] (* _Jean-François Alcover_, Mar 08 2024, after _Alois P. Heinz_ *)
%Y A370947 Main diagonal of A370945.
%Y A370947 Cf. A000009, A000110, A000296.
%K A370947 nonn
%O A370947 0,5
%A A370947 _Alois P. Heinz_, Mar 06 2024