cp's OEIS Frontend

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

%I A370946 #17 Mar 08 2024 07:15:54
%S A370946 1,0,0,1,1,2,3,4,5,7,12,14,20,26,36,54,68,90,120,157,202,296,360,480,
%T A370946 612,803,1006,1317,1764,2198,2821,3592,4552,5754,7269,9074,11990,
%U A370946 14646,18586,23112,29208,35972,45277,55584,69350,87881,107609,133068,165038
%N A370946 Number of partitions of [n] whose non-singleton elements sum to n.
%H A370946 Alois P. Heinz, <a href="/A370946/b370946.txt">Table of n, a(n) for n = 0..5000</a>
%H A370946 Wikipedia, <a href="https://en.wikipedia.org/wiki/Partition_of_a_set">Partition of a set</a>
%F A370946 a(n) = A370945(n,n*(n-1)/2).
%e A370946 a(0) = 1: the empty partition.
%e A370946 a(3) = 1: 12|3.
%e A370946 a(4) = 1: 13|2|4.
%e A370946 a(5) = 2: 1|23|4|5, 14|2|3|5.
%e A370946 a(6) = 3: 123|4|5|6, 1|24|3|5|6, 15|2|3|4|6.
%e A370946 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.
%e A370946 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.
%e A370946 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.
%e A370946 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.
%p A370946 h:= proc(n) option remember; `if`(n=0, 1,
%p A370946       add(h(n-j)*binomial(n-1, j-1), j=2..n))
%p A370946     end:
%p A370946 b:= proc(n, i, m) option remember; `if`(n>i*(i+1)/2, 0,
%p A370946      `if`(n=0, h(m), b(n, i-1, m)+b(n-i, min(n-i, i-1), m+1)))
%p A370946     end:
%p A370946 a:= n-> b(n$2, 0):
%p A370946 seq(a(n), n=0..48);
%t A370946 h[n_] := h[n] = If[n == 0, 1, Sum[h[n-j]*Binomial[n-1, j-1], {j, 2, n}]];
%t A370946 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 A370946 a[n_] := b[n, n, 0];
%t A370946 Table[a[n], {n, 0, 48}] (* _Jean-François Alcover_, Mar 08 2024, after _Alois P. Heinz_ *)
%Y A370946 Cf. A161680, A370945.
%K A370946 nonn
%O A370946 0,6
%A A370946 _Alois P. Heinz_, Mar 06 2024