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

0, 1, 2, 3, 6, 9, 17, 26, 49, 72, 134, 201, 366, 544, 984, 1436, 2614, 3838, 6770, 10019, 17767, 25808, 45597, 66671, 116461, 169747, 295922, 428090, 750343, 1086245, 1863608, 2721509, 4705456, 6759500, 11660244, 16877655, 28879255, 41778027, 71384579, 102527811, 176151979

Offset: 0

Author

Gus Wiseman, Sep 08 2023

Keywords

• nonn

Examples

			The a(1) = 1 through a(6) = 17 subsets:
  {}  {}   {}   {}     {}     {}
      {1}  {1}  {1}    {1}    {1}
           {2}  {2}    {2}    {2}
                {3}    {3}    {3}
                {1,2}  {4}    {4}
                {2,3}  {1,2}  {5}
                       {1,3}  {1,2}
                       {2,4}  {1,3}
                       {3,4}  {1,4}
                              {2,3}
                              {2,5}
                              {3,4}
                              {3,5}
                              {4,5}
                              {1,3,4}
                              {2,3,5}
                              {3,4,5}
		

Links

• David A. Corneth, Table of n, a(n) for n = 0..60

Crossrefs

The complement w/ re-usable parts is A365073.

The complement is counted by A365376.

The version with re-usable parts is A365380.

A000009 counts sets summing to n, multisets A000041.

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

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

A364350 counts combination-free strict partitions, complement A364839.

A365046 counts combination-full subsets, differences of A364914.

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

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

Programs

Mathematica

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

PARI

isok(s, n) = forsubset(#s, ss, if (vecsum(vector(#ss, k, s[ss[k]])) == n, return(0))); return(1);
a(n) = my(nb=0); forsubset(n, s, if (isok(s, n), nb++)); nb; \\ Michel Marcus, Sep 09 2023

Python

from itertools import combinations, chain
from sympy.utilities.iterables import partitions
def A365377(n):
    if n == 0: return 0
    nset = set(range(1,n+1))
    s, c = [set(p) for p in partitions(n,m=n,k=n) if max(p.values(),default=1) == 1], 1
    for a in chain.from_iterable(combinations(nset,m) for m in range(2,n+1)):
        if sum(a) >= n:
            aset = set(a)
            for p in s:
                if p.issubset(aset):
                    c += 1
                    break
    return (1<Chai Wah Wu, Sep 09 2023

Formula

a(n) = 2^n-A365376(n). - Chai Wah Wu, Sep 09 2023

Extensions

a(16)-a(27) from Michel Marcus, Sep 09 2023

a(28)-a(32) from Chai Wah Wu, Sep 09 2023

a(33)-a(35) from Chai Wah Wu, Sep 10 2023

More terms from David A. Corneth, Sep 10 2023