A326173 Number of maximal subsets of {1..n} whose sum is less than or equal to the sum of their complement.

1, 1, 1, 2, 4, 5, 8, 16, 24, 44, 77, 133, 240, 429, 772, 1414, 2588, 4742, 8761, 16273, 30255, 56392, 105581, 198352, 373228, 703409, 1329633, 2519927, 4781637, 9084813, 17298255, 33001380, 63023204, 120480659, 230702421, 442423139, 849161669, 1631219288, 3137595779, 6042247855, 11644198080, 22455871375, 43351354727

Offset

0,4

Comments

Also the number of minimal subsets of {1..n} whose sum is greater than or equal to the sum of their complement. For example, the a(0) = 1 through a(7) = 16 subsets are:

{} {1} {2} {3} {1,4} {3,5} {5,6} {1,6,7}

{1,2} {2,3} {4,5} {1,4,6} {2,5,7}

{2,4} {1,2,5} {2,3,6} {2,6,7}

{3,4} {1,3,4} {2,4,5} {3,4,7}

{2,3,4} {2,4,6} {3,5,6}

{3,4,5} {3,5,7}

{3,4,6} {3,6,7}

{1,2,3,5} {4,5,6}

{4,5,7}

{4,6,7}

{5,6,7}

{1,2,4,7}

{1,2,5,6}

{1,3,4,6}

{2,3,4,5}

{2,3,4,6}

Links

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

Example

The a(0) = 1 through a(7) = 16 subsets:
  {}  {}  {1}  {3}    {1,2}  {1,5}    {4,6}      {1,5,7}
               {1,2}  {1,3}  {2,5}    {1,2,5}    {1,6,7}
                      {1,4}  {3,4}    {1,2,6}    {2,5,7}
                      {2,3}  {1,2,3}  {1,3,5}    {3,4,7}
                             {1,2,4}  {1,3,6}    {3,5,6}
                                      {1,4,5}    {1,2,3,4}
                                      {2,3,5}    {1,2,3,5}
                                      {1,2,3,4}  {1,2,3,6}
                                                 {1,2,3,7}
                                                 {1,2,4,5}
                                                 {1,2,4,6}
                                                 {1,2,4,7}
                                                 {1,2,5,6}
                                                 {1,3,4,5}
                                                 {1,3,4,6}
                                                 {2,3,4,5}

Mathematica

fasmax[y_]:=Complement[y, Union@@(Most[Subsets[#]]&/@y)];
Table[Length[fasmax[Select[Subsets[Range[n]], Plus@@Complement[Range[n], #]>=Plus@@#&]]], {n, 0, 10}]

Crossrefs

The non-maximal case is A059529.

Cf. A053632, A057567, A057568, A063865, A326174, A326175.

Sequence in context: A293536 A274796 A160967 * A045591 A045581 A253426

Adjacent sequences: A326170 A326171 A326172 * A326174 A326175 A326176

Keyword

nonn

Author

Gus Wiseman, Jun 11 2019

Extensions

a(16)-a(42) from Bert Dobbelaere, Jun 22 2019

Status

approved