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

1, 1, 2, 5, 10, 23, 47, 102, 207, 440, 890, 1847, 3730, 7648, 15400, 31332, 62922, 127234, 255374, 514269, 1030809, 2071344, 4148707, 8321937, 16660755, 33384685, 66812942, 133789638, 267685113, 535784667, 1071878216, 2144762139, 4290261840, 8583175092, 17168208940, 34342860713

Offset: 0

Author

Gus Wiseman, Sep 08 2023

Keywords

• nonn

Examples

			The a(1) = 1 through a(4) = 10 sets:
  {1}  {2}    {3}      {4}
       {1,2}  {1,2}    {1,3}
              {1,3}    {1,4}
              {2,3}    {2,4}
              {1,2,3}  {3,4}
                       {1,2,3}
                       {1,2,4}
                       {1,3,4}
                       {2,3,4}
                       {1,2,3,4}
		

Crossrefs

The case containing n is counted by A131577.

The version with re-usable parts is A365073.

The complement is counted by A365377.

The complement w/ re-usable parts is A365380.

Main diagonal of A365381.

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.

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

Programs

Mathematica

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

PARI

isok(s, n) = forsubset(#s, ss, if (vecsum(vector(#ss, k, s[ss[k]])) == n, 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 A365376(n):
    if n == 0: return 1
    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 c # Chai Wah Wu, Sep 09 2023

Formula

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

Extensions

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

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

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