login
A366130
Number of subsets of {1..n} with a subset summing to n + 1.
4
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,4
FORMULA
Diagonal k = n + 1 of A365381.
EXAMPLE
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}
MATHEMATICA
Table[Length[Select[Subsets[Range[n]], MemberQ[Total/@Subsets[#], n+1]&]], {n, 0, 10}]
PROG
(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
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.
Sequence in context: A151998 A308631 A052130 * A368675 A065506 A330454
KEYWORD
nonn,more
AUTHOR
Gus Wiseman, Oct 07 2023
EXTENSIONS
a(20)-a(32) from Chai Wah Wu, Nov 24 2023
STATUS
approved