A365377 - OEIS

%I #36 Sep 11 2023 02:31:43

%S 0,1,2,3,6,9,17,26,49,72,134,201,366,544,984,1436,2614,3838,6770,

%T 10019,17767,25808,45597,66671,116461,169747,295922,428090,750343,

%U 1086245,1863608,2721509,4705456,6759500,11660244,16877655,28879255,41778027,71384579,102527811,176151979

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

%H David A. Corneth, <a href="/A365377/b365377.txt">Table of n, a(n) for n = 0..60</a>

%F a(n) = 2^n-A365376(n). - _Chai Wah Wu_, Sep 09 2023

%e The a(1) = 1 through a(6) = 17 subsets:

%e   {}  {}   {}   {}     {}     {}

%e       {1}  {1}  {1}    {1}    {1}

%e            {2}  {2}    {2}    {2}

%e                 {3}    {3}    {3}

%e                 {1,2}  {4}    {4}

%e                 {2,3}  {1,2}  {5}

%e                        {1,3}  {1,2}

%e                        {2,4}  {1,3}

%e                        {3,4}  {1,4}

%e                               {2,3}

%e                               {2,5}

%e                               {3,4}

%e                               {3,5}

%e                               {4,5}

%e                               {1,3,4}

%e                               {2,3,5}

%e                               {3,4,5}

%t Table[Length[Select[Subsets[Range[n]], FreeQ[Total/@Subsets[#],n]&]],{n,0,10}]

%o (PARI) isok(s, n) = forsubset(#s, ss, if (vecsum(vector(#ss, k, s[ss[k]])) == n, return(0))); return(1);

%o a(n) = my(nb=0); forsubset(n, s, if (isok(s, n), nb++)); nb; \\ _Michel Marcus_, Sep 09 2023

%o (Python)

%o from itertools import combinations, chain

%o from sympy.utilities.iterables import partitions

%o def A365377(n):

%o     if n == 0: return 0

%o     nset = set(range(1,n+1))

%o     s, c = [set(p) for p in partitions(n,m=n,k=n) if max(p.values(),default=1) == 1], 1

%o     for a in chain.from_iterable(combinations(nset,m) for m in range(2,n+1)):

%o         if sum(a) >= n:

%o             aset = set(a)

%o             for p in s:

%o                 if p.issubset(aset):

%o                     c += 1

%o                     break

%o     return (1<<n)-c # _Chai Wah Wu_, Sep 09 2023

%Y The complement w/ re-usable parts is A365073.

%Y The complement is counted by A365376.

%Y The version with re-usable parts is A365380.

%Y A000009 counts sets summing to n, multisets A000041.

%Y A000124 counts distinct possible sums of subsets of {1..n}.

%Y A124506 appears to count combination-free subsets, differences of A326083.

%Y A364350 counts combination-free strict partitions, complement A364839.

%Y A365046 counts combination-full subsets, differences of A364914.

%Y A365381 counts subsets of {1..n} with a subset summing to k.

%Y Cf. A007865, A085489, A088809, A093971, A103580, A151897, A236912, A237113, A237668, A326080, A364349, A364534.

%K nonn

%O 0,3

%A _Gus Wiseman_, Sep 08 2023

%E a(16)-a(27) from _Michel Marcus_, Sep 09 2023

%E a(28)-a(32) from _Chai Wah Wu_, Sep 09 2023

%E a(33)-a(35) from _Chai Wah Wu_, Sep 10 2023

%E More terms from _David A. Corneth_, Sep 10 2023