A093971 Number of sum-full subsets of {1,...,n}; subsets A such that there is a solution to x+y=z for x,y,z in A.

0, 1, 2, 7, 16, 40, 86, 195, 404, 873, 1795, 3727, 7585, 15537, 31368, 63582, 127933, 257746, 517312, 1038993, 2081696, 4173322, 8355792, 16731799, 33484323, 67014365, 134069494, 268234688, 536562699, 1073326281, 2146849378, 4294117419, 8588623348, 17178130162

Offset

1,3

Comments

In sumset notation, number of subsets A of {1,...,n} such that the intersection of A and 2A is nonempty.

A variation of binary sum-full sets where parts can be re-used, this sequence counts subsets of {1..n} containing a part equal to the sum of two other (possibly equal) parts. The complement is counted by A007865. The non-binary version is A364914. For non-re-usable parts we have A088809. - Gus Wiseman, Aug 14 2023

Links

Fausto A. C. Cariboni, Table of n, a(n) for n = 1..88

Eric Weisstein's World of Mathematics, Sum-Free Set

Formula

a(n) = 2^n - A007865(n).

Example

The a(1) = 0 through a(5) = 16 subsets:
  .  {1,2}  {1,2}    {1,2}      {1,2}
            {1,2,3}  {2,4}      {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,4}
                     {1,2,3,4}  {1,4,5}
                                {2,3,4}
                                {2,3,5}
                                {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]], Intersection[#, Total/@Tuples[#, 2]]!={}&]], {n, 0, 10}] (* Gus Wiseman, Aug 14 2023 *)

Crossrefs

The complement is counted by A007865.

The version without re-usable parts is A088809 (differences A364756), complement A085489 (differences A364755).

The non-binary version is A364914, complement A326083.

The non-binary version w/o re-usable parts is A364534, complement A151897.

The version for partitions is A363225:

- ranks A364348,

- strict A363226,

- non-binary A364839,

- without re-usable parts A237113,

- non-binary without re-usable parts A237668.

The complement for partitions is A364345:

- ranks A364347,

- strict A364346,

- non-binary A364350,

- without re-usable parts A236912,

- non-binary without re-usable parts A237667.

Cf. A000079, A050291, A051026, A103580, A308546, A326080, A364349, A364461, A364533, A364670.

Sequence in context: A293378 A041887 A129441 * A065497 A131727 A320236

Adjacent sequences: A093968 A093969 A093970 * A093972 A093973 A093974

Keyword

nonn

Author

T. D. Noe, Apr 20 2004

Extensions

Terms a(31) and beyond from Fausto A. C. Cariboni, Oct 01 2020

Status

approved