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

Links

Table of n, a(n) for n=0..35.

Formula

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

Example

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}

Mathematica

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

Prog

(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

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.

Sequence in context: A109165 A018344 A284181 * A291249 A365441 A260744

Adjacent sequences: A365373 A365374 A365375 * A365377 A365378 A365379

Keyword

nonn

Author

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

Status

approved