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

Author

T. D. Noe, Apr 20 2004

Keywords

• nonn

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

Examples

			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}
		

Links

• Fausto A. C. Cariboni, Table of n, a(n) for n = 1..88
• Eric Weisstein's World of Mathematics, Sum-Free Set

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.

Programs

Mathematica

Table[Length[Select[Subsets[Range[n]],Intersection[#,Total/@Tuples[#,2]]!={}&]],{n,0,10}] (* Gus Wiseman, Aug 14 2023 *)

Formula

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

Extensions

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