A308546 -id:A308546 - cp's OEIS frontend

A007865 Number of sum-free subsets of {1, ..., n}.

1, 2, 3, 6, 9, 16, 24, 42, 61, 108, 151, 253, 369, 607, 847, 1400, 1954, 3139, 4398, 6976, 9583, 15456, 20982, 32816, 45417, 70109, 94499, 148234, 200768, 308213, 415543, 634270, 849877, 1311244, 1739022, 2630061, 3540355, 5344961, 7051789, 10747207, 14158720, 21295570, 28188520

Offset: 0

Peter J. Cameron

More precisely, subsets of {1,...,n} containing no solutions of x+y=z.
There are two proofs that a(n) is 2^{n/2}(1+o(1)), as Paul Erdős and I conjectured.
In sumset notation, number of subsets A of {1,...,n} such that the intersection of A and 2A is empty. Using the Mathematica program, all such subsets can be printed. - T. D. Noe, Apr 20 2004
The Sapozhenko paper has many additional references.
If this sequence counts sum-free sets, then A326083 counts sum-closed sets, which is different from sum-full sets (A093971). - Gus Wiseman, Jul 08 2019

			{} has one sum-free subset, the empty set, so a(0)=1.
{1} has two sum-free subsets, {} and {1}, so a(1)=2.
a(2) = 3: 0,1,2.
a(3) = 6: 0,1,2,3,13,23.
a(4) = 9: 0,1,2,3,4,13,14,23,34.

S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 180-183.

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..88, (terms up to a(70) from Per Hakan Lundow)
József Balogh, Hong Liu, Maryam Sharifzadeh, and Andrew Treglown, Sharp bound on the number of maximal sum-free subsets of integers, J. Eur. Math. Soc. 20 (2018), no. 8, pp. 1885-1911, also arXiv:1502.07605, Feb. 2015.
P. J. Cameron and P. Erdős, On the number of integers with various properties, in R. A. Mullin, ed., Number Theory: Proc. First Conf. of Canad. Number Theory Assoc. Conf., Banff, De Gruyter, Berlin, 1990, pp. 61-79.
Steven R. Finch, Several Problems Concerning Sum-Free Sets [Broken link]
Steven R. Finch, Several Problems Concerning Sum-Free Sets [From the Wayback machine]
Ben Green and Imre Z. Ruzsa, Sum-free sets in abelian groups, arXiv:math/0307142 [math.CO], 2004.
A. A. Sapozhenko, The Cameron-Erdős conjecture, Discrete Math., 308 (2008), 4361-4369.
Eric Weisstein's World of Mathematics, Sum-Free Set

See A085489 for another version.
Cf. A211316, A211317, A093970, A093971 (number of sum-full subsets of 1..n).
Cf. A050291, A103580, A151897, A308546, A326020, A326080, A326083.

S3S:= {{}}: a[0]:= 1: for n from 1 to 35 do S3S:= S3S union map(t -> t union {n}, select(t -> (t intersect map(q -> n-q,t)={}),S3S)); a[n]:= nops(S3S) od: seq(a[n],n=0..35); # Code for computing (the number of) sum-free subsets of {1, ..., n} - Robert Israel

SumFreeSet[ 0 ] = {{}}; SumFreeSet[ n_ ] := SumFreeSet[ n ] = Union[ SumFreeSet[ n - 1 ], Union[ #, {n} ] & /@ Select[ SumFreeSet[ n - 1 ], Intersection[ #, n - # ] == {} & ] ] As a check, enter Length /@ SumFreeSet /@ Range[ 0, 30 ] Alternatively, use NestList. n = 0; Length /@ NestList[ (++n; Union[ #, Union[ #, {n} ] & /@ Select[ #, Intersection[ #, n - # ] == {} & ] ]) &, {{}}, 30 ] (* from Paul Abbott, based on Robert Israel's Maple code *)
Timing[ n = 0; Last[ Reap[ Nest[ (++n; Sow[ Length[ # ] ]; Union[ #, Union[ #, {n} ]& /@ Select[ #, Intersection[ #, n - # ] == {} & ] ]) &, {{}}, 36 ] ] ] ] (* improved code from Paul Abbott, Nov 24 2005 *)
Table[Length[Select[Subsets[Range[n]],Intersection[#,Total/@Tuples[#,2]]=={}&]],{n,1,10}] (* Gus Wiseman, Jul 08 2019 *)

\\ good only for n <= 25:
sumfree(v) = {for(i=1, #v, for (j=1, i, if (setsearch(v, v[i]+v[j]), return (0)););); return (1);}
a(n) = {my(nb = 0); forsubset(n, s, if (sumfree(Set(s)), nb++);); nb;} \\ Michel Marcus, Nov 08 2020

a(n) = A050291(n)-A088810(n) = A085489(n)-A088811(n) = A050291(n)+A085489(n)-A088813(n). - Reinhard Zumkeller, Oct 19 2003

More terms from John W. Layman, Oct 21 2000
Extended through a(35) by Robert Israel, Nov 16 2005
a(36)-a(37) from Alec Mihailovs (alec(AT)mihailovs.com) (using Robert Israel's procedure), Nov 16 2005
a(38) from Eric W. Weisstein, Nov 17 2005
a(39)-a(42) from Eric W. Weisstein, Nov 28 2005, using Paul Abbott's Mathematica code

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.

Original entry on oeis.org

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

T. D. Noe, Apr 20 2004

nonn

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

			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}

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

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.

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

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

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

A151897 Number of subsets of {1, 2, ..., n} such that no member is a sum of distinct other members.

Original entry on oeis.org

1, 2, 4, 7, 13, 22, 37, 60, 100, 155, 249, 381, 591, 889, 1365, 2009, 3047, 4453, 6602, 9567, 14151, 20228, 29654, 42302, 61369, 87108, 126066, 177580, 256039, 360304, 515740, 724069, 1036860, 1448746, 2069526, 2893311, 4117725, 5749540, 8186555

Offset: 0

David Wasserman, Apr 16 2008

nonn

This sequence and A085489 first differ at n = 7. a(7) = 60, A085489(7) = 61. A085489(7) includes {1, 2, 4, 7}, which is excluded from a(7) because 1+2+4 = 7.

If this sequence counts sum-free sets, A326080 counts sum-closed sets, which are different from sum-full sets (A093971). - Gus Wiseman, Jun 07 2019

			a(4) = 13, including all subsets of {1, 2, 3, 4} except {1, 2, 3} (excluded
because 1+2 = 3), {1, 3, 4} (excluded because 1+3 = 4), and {1, 2, 3, 4} (excluded for both reasons.)
From _Gus Wiseman_, Jun 07 2019: (Start)
The a(0) = 1 through a(4) = 13 subsets:
  {}  {}   {}     {}     {}
      {1}  {1}    {1}    {1}
           {2}    {2}    {2}
           {1,2}  {3}    {3}
                  {1,2}  {4}
                  {1,3}  {1,2}
                  {2,3}  {1,3}
                         {1,4}
                         {2,3}
                         {2,4}
                         {3,4}
                         {1,2,4}
                         {2,3,4}
(End)

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

Cf. A007865, A050291, A085489, A103580, A308546, A326080, A326083, A326117.

Table[Length[Select[Subsets[Range[n]],Intersection[#,Plus@@@Subsets[#,{2,Length[#]}]]=={}&]],{n,0,10}] (* Gus Wiseman, Jun 07 2019 *)

a(0) = 1 prepended by Gus Wiseman, Jun 07 2019

A085489 a(n) is the number of subsets of {1,...,n} containing no solutions to x+y=z with x and y distinct (one version of "sum-free subsets").

Original entry on oeis.org

1, 2, 4, 7, 13, 22, 37, 61, 102, 162, 261, 410, 646, 1001, 1553, 2370, 3645, 5515, 8303, 12470, 18713, 27811, 41244, 60962, 89733, 131870, 192522, 281125, 408680, 593880, 855661, 1238592, 1779614, 2563476, 3660084, 5255913, 7473380, 10696444, 15137517

Offset: 0

Eric W. Weisstein, Jul 02 2003

First differs from A151897 at a(7) = 61, A151897(7) = 60. The one subset counted under a(7) but not under A151897(7) is {1,2,4,7}. - Gus Wiseman, Jun 07 2019

			From _Gus Wiseman_, Jun 07 2019: (Start)
The a(0) = 1 through a(4) = 13 subsets:
  {}  {}   {}     {}     {}
      {1}  {1}    {1}    {1}
           {2}    {2}    {2}
           {1,2}  {3}    {3}
                  {1,2}  {4}
                  {1,3}  {1,2}
                  {2,3}  {1,3}
                         {1,4}
                         {2,3}
                         {2,4}
                         {3,4}
                         {1,2,4}
                         {2,3,4}
The a(5) = 22 subsets:
  {}  {1}  {1,2}  {1,2,4}
      {2}  {1,3}  {1,2,5}
      {3}  {1,4}  {1,3,5}
      {4}  {1,5}  {2,3,4}
      {5}  {2,3}  {2,4,5}
           {2,4}  {3,4,5}
           {2,5}
           {3,4}
           {3,5}
           {4,5}
(End)

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..75, (terms up to a(57) from Ben Burns)
Eric Weisstein's World of Mathematics, Sum-Free Set [Strictly speaking this link is not relevant, since it uses a different definition of "sum-free".]

See A007865 for another version.

Cf. A050291, A051026, A103580, A151897, A308546, A326080, A326083, A326117.

Table[Length[Select[Subsets[Range[n]],Intersection[ #,Select[ Plus@@@ Subsets[ #,{2}],#<=n&]]=={}&]],{n,0,10}] (* Gus Wiseman, Jun 07 2019 *)

a(n) = 2^n - A088809(n). - Reinhard Zumkeller, Oct 19 2003

More terms from Reinhard Zumkeller, Jul 13 2003
Edited by David Wasserman, Apr 16 2008
a(0) = 1 prepended by Gus Wiseman, Jun 07 2019

A364914 Number of subsets of {1..n} such that some element can be written as a nonnegative linear combination of the others.

Original entry on oeis.org

0, 0, 1, 3, 9, 20, 48, 101, 219, 454, 944, 1917, 3925, 7915, 16004, 32188, 64751, 129822, 260489, 521672, 1045060, 2091808, 4187047, 8377255, 16762285, 33531228, 67077485, 134170217, 268371678, 536772231, 1073611321, 2147282291, 4294697258, 8589527163, 17179321094

Offset: 0

Gus Wiseman, Aug 17 2023

nonn

A variation of non-binary combination-full sets where parts can be re-used. The complement is counted by A326083. The binary version is A093971. For non-re-usable parts we have A364534. First differences are A365046.

			The set {3,4,5,17} has 17 = 1*3 + 1*4 + 2*5, so is counted under a(17).
The a(0) = 0 through a(5) = 20 subsets:
  .  .  {1,2}  {1,2}    {1,2}      {1,2}
               {1,3}    {1,3}      {1,3}
               {1,2,3}  {1,4}      {1,4}
                        {2,4}      {1,5}
                        {1,2,3}    {2,4}
                        {1,2,4}    {1,2,3}
                        {1,3,4}    {1,2,4}
                        {2,3,4}    {1,2,5}
                        {1,2,3,4}  {1,3,4}
                                   {1,3,5}
                                   {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}

Steven R. Finch, Monoids of natural numbers, March 17, 2009.

The binary complement is A007865.
The binary version without re-usable parts is A088809.
The binary version is A093971.
The complement without re-usable parts is A151897.
The complement is counted by A326083.
The version without re-usable parts is A364534.
The version for strict partitions is A364839, complement A364350.
The version for partitions is A364913.
The version for positive combinations is A365043, complement A365044.
First differences are A365046.
Cf. A011782, A085489, A103580, A116861, A124506, A237113, A237668, A308546, A324736, A326020, A326080, A364272, A364349, A364756.

combs[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,0,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
Table[Length[Select[Subsets[Range[n]],Or@@Table[combs[#[[k]],Delete[#,k]]!={},{k,Length[#]}]&]],{n,0,10}]

from itertools import combinations
from sympy.utilities.iterables import partitions
def A364914(n):
    c, mlist = 0, []
    for m in range(1,n+1):
        t = set()
        for p in partitions(m,k=m-1):
            t.add(tuple(sorted(p.keys())))
        mlist.append([set(d) for d in t])
    for k in range(2,n+1):
        for w in combinations(range(1,n+1),k):
            ws = set(w)
            for d in w:
                for s in mlist[d-1]:
                    if s <= ws:
                        c += 1
                        break
                else:
                    continue
                break
    return c # Chai Wah Wu, Nov 17 2023

a(12)-a(34) from Chai Wah Wu, Nov 17 2023

A124506 Number of numerical semigroups with Frobenius number n; that is, numerical semigroups for which the largest integer not belonging to them is n.

Original entry on oeis.org

1, 1, 2, 2, 5, 4, 11, 10, 21, 22, 51, 40, 106, 103, 200, 205, 465, 405, 961, 900, 1828, 1913, 4096, 3578, 8273, 8175, 16132, 16267, 34903, 31822, 70854, 68681, 137391, 140661, 292081, 270258, 591443, 582453, 1156012

Offset: 1

P. A. Garcia-Sanchez (pedro(AT)ugr.es), Dec 18 2006

From Gus Wiseman, Aug 28 2023: (Start)
Appears to be the number of subsets of {1..n} containing n such that no element can be written as a nonnegative linear combination of the others, first differences of A326083. For example, the a(1) = 1 through a(8) = 10 subsets are:
  {1}  {2}  {3}    {4}    {5}      {6}      {7}        {8}
            {2,3}  {3,4}  {2,5}    {4,6}    {2,7}      {3,8}
                          {3,5}    {5,6}    {3,7}      {5,8}
                          {4,5}    {4,5,6}  {4,7}      {6,8}
                          {3,4,5}           {5,7}      {7,8}
                                            {6,7}      {3,7,8}
                                            {3,5,7}    {5,6,8}
                                            {4,5,7}    {5,7,8}
                                            {4,6,7}    {6,7,8}
                                            {5,6,7}    {5,6,7,8}
                                            {4,5,6,7}
Note that these subsets do not all generate numerical semigroups, as their GCD is unrestricted, cf. A358392. The complement is counted by A365046, first differences of A364914.
(End)

			a(1) = 1 via <2,3> = {0,2,3,4,...}; the largest missing number is 1.
a(2) = 1 via <3,4,5> = {0,3,4,5,...}; the largest missing number is 2.
a(3) = 2 via <2,5> = {0,2,4,5,...}; and <4,5,6,7> = {0,4,5,6,7,...} where in both the largest missing number is 3.
a(4) = 2 via <3,5,7> = {0,3,5,6,7,...} and <5,6,7,8,9> = {5,6,7,8,9,...} where in both the largest missing number is 4.

S. R. Finch, Monoids of natural numbers
Manuel Delgado, Neeraj Kumar, and Claude Marion, On counting numerical semigroups by maximum primitive and Wilf's conjecture, arXiv:2501.04417 [math.CO], 2025. See p. 22.
S. R. Finch, Monoids of natural numbers, March 17, 2009. [Cached copy, with permission of the author]
J. C. Rosales, P. A. Garcia-Sanchez, J. I. Garcia-Garcia, and J. A. Jimenez-Madrid, Fundamental gaps in numerical semigroups, Journal of Pure and Applied Algebra 189 (2004) 301-313.
Clayton Cristiano Silva, Irreducible Numerical Semigroups, University of Campinas, São Paulo, Brazil (2019).

Cf. A158206. [From Steven Finch, Mar 13 2009]
A288728 counts sum-free sets, first differences of A007865.
A364350 counts combination-free partitions, complement A364839.
Cf. A085489, A088809, A093971, A103580, A116861, A151897, A237668, A308546, A326020, A326083, A364349, A365069.

The sequence was originally generated by a C program and a Haskell script. The sequence can be obtained by using the function NumericalSemigroupsWithFrobeniusNumber included in the numericalsgps GAP package.

A103580 Number of nonempty subsets S of {1,2,3,...,n} that have the property that no element x of S is a nonnegative integer linear combination of elements of S-{x}.

Original entry on oeis.org

1, 2, 4, 6, 11, 15, 26, 36, 57, 79, 130, 170, 276, 379, 579, 784, 1249, 1654, 2615, 3515, 5343, 7256, 11352, 14930, 23203, 31378, 47510, 63777, 98680, 130502, 201356, 270037, 407428, 548089, 840170, 1110428, 1701871, 2284324, 3440336, 4601655

Offset: 1

Jeffrey Shallit, Mar 23 2005

nonn

			a(4) = 6 because the only permissible subsets are {1}, {2}, {3}, {4}, {2,3}, {3,4}.
From _Gus Wiseman_, Jun 07 2019: (Start)
The a(1) = 1 through a(6) = 15 nonempty subsets of {1..n} containing none of their own non-singleton nonzero nonnegative linear combinations are:
  {1}  {1}  {1}    {1}    {1}      {1}
       {2}  {2}    {2}    {2}      {2}
            {3}    {3}    {3}      {3}
            {2,3}  {4}    {4}      {4}
                   {2,3}  {5}      {5}
                   {3,4}  {2,3}    {6}
                          {2,5}    {2,3}
                          {3,4}    {2,5}
                          {3,5}    {3,4}
                          {4,5}    {3,5}
                          {3,4,5}  {4,5}
                                   {4,6}
                                   {5,6}
                                   {3,4,5}
                                   {4,5,6}
a(n) is also the number of nonempty subsets of {1..n} containing all of their own nonzero nonnegative linear combinations <= n. For example the a(1) = 1 through a(6) = 15 subsets are:
  {1}  {2}    {2}      {3}        {3}          {4}
       {1,2}  {3}      {4}        {4}          {5}
              {2,3}    {2,4}      {5}          {6}
              {1,2,3}  {3,4}      {2,4}        {3,6}
                       {2,3,4}    {3,4}        {4,5}
                       {1,2,3,4}  {3,5}        {4,6}
                                  {4,5}        {5,6}
                                  {2,4,5}      {2,4,6}
                                  {3,4,5}      {3,4,6}
                                  {2,3,4,5}    {3,5,6}
                                  {1,2,3,4,5}  {4,5,6}
                                               {2,4,5,6}
                                               {3,4,5,6}
                                               {2,3,4,5,6}
                                               {1,2,3,4,5,6}
(End)

Fausto A. C. Cariboni, Table of n, a(n) for n = 1..100
Sergey Kitaev, Independent Sets on Path-Schemes, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.2.
Sean Li, Counting numerical semigroups by Frobenius number, multiplicity, and depth, arXiv:2208.14587 [math.CO], 2022.

Cf. A007865, A050291, A051026, A085489, A139384, A151897, A308546.

Cf. A326020, A326076, A326080, A326083, A326114.

Table[Length[Select[Subsets[Range[n],{1,n}],SubsetQ[#,Select[Plus@@@Tuples[#,2],#<=n&]]&]],{n,10}] (* Gus Wiseman, Jun 07 2019 *)

a(n) = A326083(n) - 1. - Gus Wiseman, Jun 07 2019

More terms from David Wasserman, Apr 16 2008

A365046 Number of subsets of {1..n} containing n such that some element can be written as a nonnegative linear combination of the others.

Original entry on oeis.org

0, 0, 1, 2, 6, 11, 28, 53, 118, 235, 490, 973, 2008, 3990, 8089, 16184, 32563, 65071, 130667, 261183, 523388, 1046748, 2095239, 4190208, 8385030, 16768943, 33546257, 67092732, 134201461, 268400553, 536839090, 1073670970, 2147414967, 4294829905, 8589793931

Offset: 0

Gus Wiseman, Aug 24 2023

nonn

Includes all subsets containing both 1 and n.

			The subset {3,4,10} has 10 = 2*3 + 1*4 so is counted under a(10).
The a(0) = 0 through a(5) = 11 subsets:
  .  .  {1,2}  {1,3}    {1,4}      {1,5}
               {1,2,3}  {2,4}      {1,2,5}
                        {1,2,4}    {1,3,5}
                        {1,3,4}    {1,4,5}
                        {2,3,4}    {2,3,5}
                        {1,2,3,4}  {2,4,5}
                                   {1,2,3,5}
                                   {1,2,4,5}
                                   {1,3,4,5}
                                   {2,3,4,5}
                                   {1,2,3,4,5}

Steven R. Finch, Monoids of natural numbers, March 17, 2009.

The complement is A124506, first differences of A326083.
The binary complement is A288728, first differences of A007865.
First differences of A364914.
The positive version is A365042, first differences of A365043.
The positive complement is counted by A365045, first differences of A365044.
Without re-usable parts we have A365069, first differences of A364534.
The binary version is A365070, first differences of A093971.
A364350 counts combination-free strict partitions, complement A364839.
A085489 and A364755 count subsets without the sum of two distinct elements.
A088809 and A364756 count subsets with the sum of two distinct elements.
A364913 counts combination-full partitions.
Cf. A151897, A237113, A237668, A308546, A324736, A326020, A326080, A364272.

combs[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,0,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
Table[Length[Select[Subsets[Range[n]],MemberQ[#,n]&&Or@@Table[combs[#[[k]],Union[Delete[#,k]]]!={},{k,Length[#]}]&]],{n,0,10}]

a(n+1) = 2^n - A124506(n).

A050291 Number of double-free subsets of {1, 2, ..., n}.

Original entry on oeis.org

1, 2, 3, 6, 10, 20, 30, 60, 96, 192, 288, 576, 960, 1920, 2880, 5760, 9360, 18720, 28080, 56160, 93600, 187200, 280800, 561600, 898560, 1797120, 2695680, 5391360, 8985600, 17971200, 26956800, 53913600, 87091200, 174182400, 261273600, 522547200, 870912000

Offset: 0

Eric W. Weisstein

A set is double-free if it does not contain both x and 2x.

So these are equally "half-free" subsets. - Gus Wiseman, Jul 08 2019

			From _Gus Wiseman_, Jul 08 2019: (Start)
The a(0) = 1 through a(5) = 20 double-free subsets:
  {}  {}   {}   {}     {}       {}
      {1}  {1}  {1}    {1}      {1}
           {2}  {2}    {2}      {2}
                {3}    {3}      {3}
                {1,3}  {4}      {4}
                {2,3}  {1,3}    {5}
                       {1,4}    {1,3}
                       {2,3}    {1,4}
                       {3,4}    {1,5}
                       {1,3,4}  {2,3}
                                {2,5}
                                {3,4}
                                {3,5}
                                {4,5}
                                {1,3,4}
                                {1,3,5}
                                {1,4,5}
                                {2,3,5}
                                {3,4,5}
                                {1,3,4,5}
(End)

Wang, E. T. H. ``On Double-Free Sets of Integers.'' Ars Combin. 28, 97-100, 1989.

Alois P. Heinz, Table of n, a(n) for n = 0..4030 (terms n = 1..400 from T. D. Noe)
Steven R. Finch, Triple-Free Sets of Integers [From Steven Finch, Apr 20 2019]
Eric Weisstein's World of Mathematics, Double-Free Set.

Cf. A000045, A007814, A050292-A050296.

Cf. A007865, A103580, A120641, A308546, A320340, A323092, A326083, A326115.

a:= proc(n) option remember; `if`(n=0, 1, (F-> (p-> a(n-1)*F(p+3)
      /F(p+2))(padic[ordp](n, 2)))(j-> (<<0|1>, <1|1>>^j)[1, 2]))
    end:
seq(a(n), n=0..50);  # Alois P. Heinz, Jan 16 2019

a[n_] := a[n] = (b = IntegerExponent[2n, 2]; a[n-1]*Fibonacci[b+2]/Fibonacci[b+1]); a[1]=2; Table[a[n], {n, 1, 34}] (* Jean-François Alcover, Oct 10 2012, from first formula *)
Table[Length[Select[Subsets[Range[n]],Intersection[#,#/2]=={}&]],{n,0,10}] (* Gus Wiseman, Jul 08 2019 *)

first(n)=my(v=vector(n)); v[1]=2; for(k=2,n, v[k]=v[k-1]*fibonacci(valuation(k,2)+3)/fibonacci(valuation(k,2)+2)); v \\ Charles R Greathouse IV, Feb 07 2017

a(n) = a(n-1)*Fibonacci(b(2n)+2)/Fibonacci(b(2n)+1), Fibonacci = A000045, b = A007814.

a(n) = 2^n - A088808(n). - Reinhard Zumkeller, Oct 19 2003

Extended with formula by Christian G. Bower, Sep 15 1999

a(0)=1 prepended by Alois P. Heinz, Jan 16 2019

A365073 Number of subsets of {1..n} that can be linearly combined using nonnegative coefficients to obtain n.

Original entry on oeis.org

1, 1, 3, 6, 14, 26, 60, 112, 244, 480, 992, 1944, 4048, 7936, 16176, 32320, 65088, 129504, 261248, 520448, 1046208, 2090240, 4186624, 8365696, 16766464, 33503744, 67064064, 134113280, 268347392, 536546816, 1073575936, 2146703360, 4294425600, 8588476416, 17178349568

Offset: 0

Gus Wiseman, Sep 01 2023

nonn

			The subset {2,3,6} has 7 = 2*2 + 1*3 + 0*6 so is counted under a(7).
The a(1) = 1 through a(4) = 14 subsets:
  {1}  {1}    {1}      {1}
       {2}    {3}      {2}
       {1,2}  {1,2}    {4}
              {1,3}    {1,2}
              {2,3}    {1,3}
              {1,2,3}  {1,4}
                       {2,3}
                       {2,4}
                       {3,4}
                       {1,2,3}
                       {1,2,4}
                       {1,3,4}
                       {2,3,4}
                       {1,2,3,4}

Andrew Howroyd, Table of n, a(n) for n = 0..100
Steven R. Finch, Monoids of natural numbers, March 17, 2009.

The case of positive coefficients is A088314.
The case of subsets containing n is A131577.
The binary version is A365314, positive A365315.
The binary complement is A365320, positive A365321.
The positive complement is counted by A365322.
A version for partitions is A365379, strict A365311.
The complement is counted by A365380.
The case of subsets without n is A365542.
A326083 and A124506 appear to count combination-free subsets.
A179822 and A326080 count sum-closed subsets.
A364350 counts combination-free strict partitions.
A364914 and A365046 count combination-full subsets.
Cf. A007865, A088809, A093971, A151897, A237668, A308546, A326020, A364534, A364839, A365043, A365381.

combs[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,0,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
Table[Length[Select[Subsets[Range[n]],combs[n,#]!={}&]],{n,0,5}]

a(n)={
  my(comb(k,b)=while(b>>k, b=bitor(b, b>>k); k*=2); b);
  my(recurse(k,b)=
    if(bittest(b,0), 2^(n+1-k),
    if(2*k>n, 2^(n+1-k) - 2^sum(j=k, n, !bittest(b,j)),
    self()(k+1, b) + self()(k+1, comb(k,b)) )));
  recurse(1, 1<Andrew Howroyd, Sep 04 2023

Terms a(12) and beyond from Andrew Howroyd, Sep 04 2023

cp's OEIS Frontend

A007865 Number of sum-free subsets of {1, ..., n}.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A151897 Number of subsets of {1, 2, ..., n} such that no member is a sum of distinct other members.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A085489 a(n) is the number of subsets of {1,...,n} containing no solutions to x+y=z with x and y distinct (one version of "sum-free subsets").

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A364914 Number of subsets of {1..n} such that some element can be written as a nonnegative linear combination of the others.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Extensions

A124506 Number of numerical semigroups with Frobenius number n; that is, numerical semigroups for which the largest integer not belonging to them is n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

A103580 Number of nonempty subsets S of {1,2,3,...,n} that have the property that no element x of S is a nonnegative integer linear combination of elements of S-{x}.

Views

Author

Keywords

Examples

Links

Crossrefs