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

%I #23 Aug 12 2023 18:25:34

%S 0,0,0,1,3,10,27,67,154,350,763,1638,3450,7191,14831,30398,61891,

%T 125557,253841,511818,1029863,2069341,4153060,8327646,16687483,

%U 33422562,66916342,133936603,268026776,536277032,1072886163,2146245056,4293187682,8587371116

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

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

%C 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

%H Fausto A. C. Cariboni, <a href="/A088809/b088809.txt">Table of n, a(n) for n = 0..75</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Sum-FreeSet.html">Sum-Free Set</a>

%H Reinhard Zumkeller, <a href="/A088808/a088808.txt">Illustration of initial terms</a>

%e From _Gus Wiseman_, Aug 10 2023: (Start)

%e 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).

%e The set {1,4,6,7} has pair-sum 1 + 6 = 7, so is counted under a(7).

%e The a(1) = 0 through a(5) = 10 sets:

%e . . {1,2,3} {1,2,3} {1,2,3}

%e {1,3,4} {1,3,4}

%e {1,2,3,4} {1,4,5}

%e {2,3,5}

%e {1,2,3,4}

%e {1,2,3,5}

%e {1,2,4,5}

%e {1,3,4,5}

%e {2,3,4,5}

%e {1,2,3,4,5}

%e (End)

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

%Y The complement is counted by A085489, differences A364755.

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

%Y The complement for partitions is A236912:

%Y non-binary A237667,

%Y ranks A364461,

%Y strict A364533.

%Y The version for partitions is A237113:

%Y non-binary A237668,

%Y ranks A364462,

%Y strict A364670.

%Y The non-binary version is A364534, complement A151897.

%Y First differences are A364756.

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

%K nonn

%O 0,5

%A _Reinhard Zumkeller_, Oct 19 2003

%E Terms a(32) and beyond from _Fausto A. C. Cariboni_, Sep 28 2020