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,3

Links

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

Formula

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

Example

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}

Mathematica

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

Prog

(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<<n)-c # Chai Wah Wu, Sep 09 2023

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.

Sequence in context: A320271 A056532 A079289 * A048811 A142155 A092351

Adjacent sequences: A365374 A365375 A365376 * A365378 A365379 A365380

Keyword

nonn

Author

Gus Wiseman, Sep 08 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

Status

approved