cp's OEIS Frontend

A365377 Number of subsets of {1..n} without a subset summing to n.

%I A365377 #36 Sep 11 2023 02:31:43
%S A365377 0,1,2,3,6,9,17,26,49,72,134,201,366,544,984,1436,2614,3838,6770,
%T A365377 10019,17767,25808,45597,66671,116461,169747,295922,428090,750343,
%U A365377 1086245,1863608,2721509,4705456,6759500,11660244,16877655,28879255,41778027,71384579,102527811,176151979
%N A365377 Number of subsets of {1..n} without a subset summing to n.
%H A365377 David A. Corneth, <a href="/A365377/b365377.txt">Table of n, a(n) for n = 0..60</a>
%F A365377 a(n) = 2^n-A365376(n). - _Chai Wah Wu_, Sep 09 2023
%e A365377 The a(1) = 1 through a(6) = 17 subsets:
%e A365377   {}  {}   {}   {}     {}     {}
%e A365377       {1}  {1}  {1}    {1}    {1}
%e A365377            {2}  {2}    {2}    {2}
%e A365377                 {3}    {3}    {3}
%e A365377                 {1,2}  {4}    {4}
%e A365377                 {2,3}  {1,2}  {5}
%e A365377                        {1,3}  {1,2}
%e A365377                        {2,4}  {1,3}
%e A365377                        {3,4}  {1,4}
%e A365377                               {2,3}
%e A365377                               {2,5}
%e A365377                               {3,4}
%e A365377                               {3,5}
%e A365377                               {4,5}
%e A365377                               {1,3,4}
%e A365377                               {2,3,5}
%e A365377                               {3,4,5}
%t A365377 Table[Length[Select[Subsets[Range[n]], FreeQ[Total/@Subsets[#],n]&]],{n,0,10}]
%o A365377 (PARI) isok(s, n) = forsubset(#s, ss, if (vecsum(vector(#ss, k, s[ss[k]])) == n, return(0))); return(1);
%o A365377 a(n) = my(nb=0); forsubset(n, s, if (isok(s, n), nb++)); nb; \\ _Michel Marcus_, Sep 09 2023
%o A365377 (Python)
%o A365377 from itertools import combinations, chain
%o A365377 from sympy.utilities.iterables import partitions
%o A365377 def A365377(n):
%o A365377     if n == 0: return 0
%o A365377     nset = set(range(1,n+1))
%o A365377     s, c = [set(p) for p in partitions(n,m=n,k=n) if max(p.values(),default=1) == 1], 1
%o A365377     for a in chain.from_iterable(combinations(nset,m) for m in range(2,n+1)):
%o A365377         if sum(a) >= n:
%o A365377             aset = set(a)
%o A365377             for p in s:
%o A365377                 if p.issubset(aset):
%o A365377                     c += 1
%o A365377                     break
%o A365377     return (1<<n)-c # _Chai Wah Wu_, Sep 09 2023
%Y A365377 The complement w/ re-usable parts is A365073.
%Y A365377 The complement is counted by A365376.
%Y A365377 The version with re-usable parts is A365380.
%Y A365377 A000009 counts sets summing to n, multisets A000041.
%Y A365377 A000124 counts distinct possible sums of subsets of {1..n}.
%Y A365377 A124506 appears to count combination-free subsets, differences of A326083.
%Y A365377 A364350 counts combination-free strict partitions, complement A364839.
%Y A365377 A365046 counts combination-full subsets, differences of A364914.
%Y A365377 A365381 counts subsets of {1..n} with a subset summing to k.
%Y A365377 Cf. A007865, A085489, A088809, A093971, A103580, A151897, A236912, A237113, A237668, A326080, A364349, A364534.
%K A365377 nonn
%O A365377 0,3
%A A365377 _Gus Wiseman_, Sep 08 2023
%E A365377 a(16)-a(27) from _Michel Marcus_, Sep 09 2023
%E A365377 a(28)-a(32) from _Chai Wah Wu_, Sep 09 2023
%E A365377 a(33)-a(35) from _Chai Wah Wu_, Sep 10 2023
%E A365377 More terms from _David A. Corneth_, Sep 10 2023