cp's OEIS Frontend

A365376 Number of subsets of {1..n} with a subset summing to n.

%I A365376 #36 Dec 30 2023 17:01:01
%S A365376 1,1,2,5,10,23,47,102,207,440,890,1847,3730,7648,15400,31332,62922,
%T A365376 127234,255374,514269,1030809,2071344,4148707,8321937,16660755,
%U A365376 33384685,66812942,133789638,267685113,535784667,1071878216,2144762139,4290261840,8583175092,17168208940,34342860713
%N A365376 Number of subsets of {1..n} with a subset summing to n.
%F A365376 a(n) = 2^n-A365377(n). - _Chai Wah Wu_, Sep 09 2023
%e A365376 The a(1) = 1 through a(4) = 10 sets:
%e A365376   {1}  {2}    {3}      {4}
%e A365376        {1,2}  {1,2}    {1,3}
%e A365376               {1,3}    {1,4}
%e A365376               {2,3}    {2,4}
%e A365376               {1,2,3}  {3,4}
%e A365376                        {1,2,3}
%e A365376                        {1,2,4}
%e A365376                        {1,3,4}
%e A365376                        {2,3,4}
%e A365376                        {1,2,3,4}
%t A365376 Table[Length[Select[Subsets[Range[n]],MemberQ[Total/@Subsets[#],n]&]],{n,0,10}]
%o A365376 (PARI) isok(s, n) = forsubset(#s, ss, if (vecsum(vector(#ss, k, s[ss[k]])) == n, return(1)));
%o A365376 a(n) = my(nb=0); forsubset(n, s, if (isok(s, n), nb++)); nb; \\ _Michel Marcus_, Sep 09 2023
%o A365376 (Python)
%o A365376 from itertools import combinations, chain
%o A365376 from sympy.utilities.iterables import partitions
%o A365376 def A365376(n):
%o A365376     if n == 0: return 1
%o A365376     nset = set(range(1,n+1))
%o A365376     s, c = [set(p) for p in partitions(n,m=n,k=n) if max(p.values(),default=1) == 1], 1
%o A365376     for a in chain.from_iterable(combinations(nset,m) for m in range(2,n+1)):
%o A365376         if sum(a) >= n:
%o A365376             aset = set(a)
%o A365376             for p in s:
%o A365376                 if p.issubset(aset):
%o A365376                     c += 1
%o A365376                     break
%o A365376     return c # _Chai Wah Wu_, Sep 09 2023
%Y A365376 The case containing n is counted by A131577.
%Y A365376 The version with re-usable parts is A365073.
%Y A365376 The complement is counted by A365377.
%Y A365376 The complement w/ re-usable parts is A365380.
%Y A365376 Main diagonal of A365381.
%Y A365376 A000009 counts sets summing to n, multisets A000041.
%Y A365376 A000124 counts distinct possible sums of subsets of {1..n}.
%Y A365376 A124506 appears to count combination-free subsets, differences of A326083.
%Y A365376 A364350 counts combination-free strict partitions, complement A364839.
%Y A365376 A365046 counts combination-full subsets, differences of A364914.
%Y A365376 Cf. A007865, A085489, A088809, A093971, A103580, A151897, A236912, A237668, A326080, A364534.
%K A365376 nonn
%O A365376 0,3
%A A365376 _Gus Wiseman_, Sep 08 2023
%E A365376 a(16)-a(25) from _Michel Marcus_, Sep 09 2023
%E A365376 a(26)-a(32) from _Chai Wah Wu_, Sep 09 2023
%E A365376 a(33)-a(35) from _Chai Wah Wu_, Sep 10 2023