cp's OEIS Frontend

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

%I A366130 #17 Nov 24 2023 12:38:05
%S A366130 0,0,1,2,7,15,38,79,184,378,823,1682,3552,7208,14948,30154,61698,
%T A366130 124302,252125,506521,1022768,2051555,4127633,8272147,16607469,
%U A366130 33258510,66680774,133467385,267349211,535007304,1071020315,2142778192,4288207796
%N A366130 Number of subsets of {1..n} with a subset summing to n + 1.
%F A366130 Diagonal k = n + 1 of A365381.
%e A366130 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).
%e A366130 The a(0) = 0 through a(5) = 15 subsets:
%e A366130   .  .  {1,2}  {1,3}    {1,4}      {1,5}
%e A366130                {1,2,3}  {2,3}      {2,4}
%e A366130                         {1,2,3}    {1,2,3}
%e A366130                         {1,2,4}    {1,2,4}
%e A366130                         {1,3,4}    {1,2,5}
%e A366130                         {2,3,4}    {1,3,5}
%e A366130                         {1,2,3,4}  {1,4,5}
%e A366130                                    {2,3,4}
%e A366130                                    {2,4,5}
%e A366130                                    {1,2,3,4}
%e A366130                                    {1,2,3,5}
%e A366130                                    {1,2,4,5}
%e A366130                                    {1,3,4,5}
%e A366130                                    {2,3,4,5}
%e A366130                                    {1,2,3,4,5}
%t A366130 Table[Length[Select[Subsets[Range[n]],MemberQ[Total/@Subsets[#],n+1]&]],{n,0,10}]
%o A366130 (Python)
%o A366130 from itertools import combinations
%o A366130 from sympy.utilities.iterables import partitions
%o A366130 def A366130(n):
%o A366130     a = tuple(set(p.keys()) for p in partitions(n+1,k=n) if max(p.values(),default=0)==1)
%o A366130     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
%Y A366130 For pairs summing to n + 1 we have A167762, complement A038754.
%Y A366130 For n instead of n + 1 we have A365376, for pairs summing to n A365544.
%Y A366130 The complement is counted by A365377 shifted.
%Y A366130 The complement for pairs summing to n is counted by A365377.
%Y A366130 A068911 counts subsets of {1..n} w/o two distinct elements summing to n.
%Y A366130 A093971/A088809/A364534 count certain types of sum-full subsets.
%Y A366130 Cf. A004526, A004737, A008967, A046663, A238628, A365381, A365541.
%K A366130 nonn,more
%O A366130 0,4
%A A366130 _Gus Wiseman_, Oct 07 2023
%E A366130 a(20)-a(32) from _Chai Wah Wu_, Nov 24 2023