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

0, 0, 1, 2, 7, 15, 38, 79, 184, 378, 823, 1682, 3552, 7208, 14948, 30154, 61698, 124302, 252125, 506521, 1022768, 2051555, 4127633, 8272147, 16607469, 33258510, 66680774, 133467385, 267349211, 535007304, 1071020315, 2142778192, 4288207796

Offset: 0

Author

Gus Wiseman, Oct 07 2023

Keywords

• nonn
• more

Examples

			The subset S = {1,2,4} has subset {1,4} with sum 4+1 and {2,4} with sum 5+1 and {1,2,4} with sum 6+1, so S is counted under a(4), a(5), and a(6).
The a(0) = 0 through a(5) = 15 subsets:
  .  .  {1,2}  {1,3}    {1,4}      {1,5}
               {1,2,3}  {2,3}      {2,4}
                        {1,2,3}    {1,2,3}
                        {1,2,4}    {1,2,4}
                        {1,3,4}    {1,2,5}
                        {2,3,4}    {1,3,5}
                        {1,2,3,4}  {1,4,5}
                                   {2,3,4}
                                   {2,4,5}
                                   {1,2,3,4}
                                   {1,2,3,5}
                                   {1,2,4,5}
                                   {1,3,4,5}
                                   {2,3,4,5}
                                   {1,2,3,4,5}
		

Crossrefs

For pairs summing to n + 1 we have A167762, complement A038754.

For n instead of n + 1 we have A365376, for pairs summing to n A365544.

The complement is counted by A365377 shifted.

The complement for pairs summing to n is counted by A365377.

A068911 counts subsets of {1..n} w/o two distinct elements summing to n.

A093971/A088809/A364534 count certain types of sum-full subsets.

Cf. A004526, A004737, A008967, A046663, A238628, A365381, A365541.

Programs

Mathematica

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

Python

from itertools import combinations
from sympy.utilities.iterables import partitions
def A366130(n):
    a = tuple(set(p.keys()) for p in partitions(n+1,k=n) if max(p.values(),default=0)==1)
    return sum(1 for k in range(2,n+1) for w in (set(d) for d in combinations(range(1,n+1),k)) if any(s<=w for s in a)) # Chai Wah Wu, Nov 24 2023

Formula

Diagonal k = n + 1 of A365381.

Extensions

a(20)-a(32) from Chai Wah Wu, Nov 24 2023