A326080 Number of subsets of {1..n} containing the sum of every subset whose sum is <= n.

1, 2, 4, 7, 12, 19, 31, 47, 73, 110, 168, 247, 375, 546, 817, 1193, 1769, 2552, 3791, 5445, 8012, 11517, 16899, 24144, 35391, 50427, 73614, 104984, 152656, 216802, 315689, 447473, 648813, 920163, 1332991, 1884735, 2728020, 3853437, 5568644, 7868096, 11347437

Offset

0,2

Comments

Equivalently, a(n) is the number of subsets of {1..n} containing the sum of any two distinct elements whose sum is <= n.

The summands must be distinct. The case where they are allowed to be equal is A326083.

If A151897 counts sum-free sets, this sequence counts sum-closed sets. This is different from sum-full sets (A093971).

Links

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

Example

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

Mathematica

Table[Length[Select[Subsets[Range[n]], SubsetQ[#, Select[Plus@@@Subsets[#, {2}], #<=n&]]&]], {n, 0, 10}]

Prog

(PARI)
a(n)={
   my(recurse(k, b)=
      if( k > n, 1,
          my(t=self()(k + 1, b + (1<<k)));
          for(i=1, (k-1)\2, if(bittest(b, i) && bittest(b, k-i), return(t)));
          t + self()(k + 1, b) )
   );
   recurse(1, 0);
} \\ Andrew Howroyd, Aug 30 2019

Crossrefs

Cf. A007865, A050291, A051026, A054519, A085489, A093971, A103580, A120641, A151897, A326020, A326023, A326076, A326083.

Sequence in context: A333148 A343661 A342229 * A287525 A244472 A279890

Adjacent sequences: A326077 A326078 A326079 * A326081 A326082 A326083

Keyword

nonn

Author

Gus Wiseman, Jun 05 2019

Extensions

Terms a(21) and beyond from Andrew Howroyd, Aug 30 2019

Status

approved