A088809 Number of subsets of {1, ..., n} that are not sum-free.

0, 0, 0, 1, 3, 10, 27, 67, 154, 350, 763, 1638, 3450, 7191, 14831, 30398, 61891, 125557, 253841, 511818, 1029863, 2069341, 4153060, 8327646, 16687483, 33422562, 66916342, 133936603, 268026776, 536277032, 1072886163, 2146245056, 4293187682, 8587371116

Offset

0,5

Comments

a(n) = 2^n - A085489(n); a non-sum-free subset contains at least one subset {u,v, w} with w=u+v.

A variation of binary sum-full sets where parts cannot be re-used, this sequence counts subsets of {1..n} with an element equal to the sum of two distinct others. The complement is counted by A085489. The non-binary version is A364534. For re-usable parts we have A093971. - Gus Wiseman, Aug 10 2023

Links

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..75

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

Reinhard Zumkeller, Illustration of initial terms

Example

From Gus Wiseman, Aug 10 2023: (Start)
The set S = {1,3,6,8} has pair-sums {4,7,9,11,14}, which are all missing from S, so it is not counted under a(8).
The set {1,4,6,7} has pair-sum 1 + 6 = 7, so is counted under a(7).
The a(1) = 0 through a(5) = 10 sets:
  .  .  {1,2,3}  {1,2,3}    {1,2,3}
                 {1,3,4}    {1,3,4}
                 {1,2,3,4}  {1,4,5}
                            {2,3,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}
(End)

Mathematica

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

Crossrefs

The complement is counted by A085489, differences A364755.

With re-usable parts we have A093971, for partitions A363225.

The complement for partitions is A236912:

non-binary A237667,

ranks A364461,

strict A364533.

The version for partitions is A237113:

non-binary A237668,

ranks A364462,

strict A364670.

The non-binary version is A364534, complement A151897.

First differences are A364756.

Cf. A000079, A007865, A050291, A051026, A103580, A288728, A326020, A326080, A326083, A364272, A364349.

Sequence in context: A192959 A100624 A320586 * A364534 A069229 A378623

Adjacent sequences: A088806 A088807 A088808 * A088810 A088811 A088812

Keyword

nonn

Author

Reinhard Zumkeller, Oct 19 2003

Extensions

Terms a(32) and beyond from Fausto A. C. Cariboni, Sep 28 2020

Status

approved