A326080 -id:A326080 - 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

A326083 Number of subsets of {1..n} containing all of their pairwise sums <= n.

Original entry on oeis.org

1, 2, 3, 5, 7, 12, 16, 27, 37, 58, 80, 131, 171, 277, 380, 580, 785, 1250, 1655, 2616, 3516, 5344, 7257, 11353, 14931, 23204, 31379, 47511, 63778, 98681, 130503, 201357, 270038, 407429, 548090, 840171, 1110429, 1701872, 2284325, 3440337, 4601656

Offset: 0

Gus Wiseman, Jun 05 2019

nonn

The summands are allowed to be equal. The case where they must be distinct is A326080. If A007865 counts sum-free sets, this sequence counts sum-closed sets. This is different from sum-full sets (A093971).
From Gus Wiseman, Jul 08 2019: (Start)
Also the number of subsets of {1..n} containing no sum of any multiset of the elements. For example, the a(0) = 1 through a(6) = 16 subsets 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}
(End)

			The a(0) = 1 through a(6) = 16 subsets:
  {}  {}   {}     {}       {}         {}           {}
      {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}
The a(7) = 27 subsets:
  {}  {4}  {36}  {246}  {2467}  {24567}  {234567}  {1234567}
      {5}  {45}  {356}  {3467}  {34567}
      {6}  {46}  {367}  {3567}
      {7}  {47}  {456}  {4567}
           {56}  {457}
           {57}  {467}
           {67}  {567}

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

Cf. A007865, A050291, A051026, A054519, A085489, A093971, A103580, A120641, A151897, A326020, A326023, A326076, A326080.

Table[Length[Select[Subsets[Range[n]],SubsetQ[#,Select[Plus@@@Tuples[#,2],#<=n&]]&]],{n,0,10}]

For n > 0, a(n) = A103580(n) + 1.

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

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

Original entry on oeis.org

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

Reinhard Zumkeller, Oct 19 2003

nonn

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

			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)

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

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.

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

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

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

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

A088314 Cardinality of set of sets of parts of all partitions of n.

Original entry on oeis.org

1, 1, 2, 3, 5, 6, 10, 12, 18, 22, 30, 37, 51, 61, 79, 96, 124, 148, 186, 222, 275, 326, 400, 473, 575, 673, 811, 946, 1132, 1317, 1558, 1813, 2138, 2463, 2893, 3323, 3882, 4461, 5177, 5917, 6847, 7818, 8994, 10251, 11766, 13334, 15281, 17309, 19732, 22307

Offset: 0

Naohiro Nomoto, Nov 05 2003

Number of different values of A007947(m) when A056239(m) is equal to n.
From Gus Wiseman, Sep 11 2023: (Start)
Also the number of finite sets of positive integers that can be linearly combined using all positive coefficients to obtain n. For example, the a(1) = 1 through a(7) = 12 sets are:
  {1}  {1}  {1}    {1}    {1}    {1}      {1}
       {2}  {3}    {2}    {5}    {2}      {7}
            {1,2}  {4}    {1,2}  {3}      {1,2}
                   {1,2}  {1,3}  {6}      {1,3}
                   {1,3}  {1,4}  {1,2}    {1,4}
                          {2,3}  {1,3}    {1,5}
                                 {1,4}    {1,6}
                                 {1,5}    {2,3}
                                 {2,4}    {2,5}
                                 {1,2,3}  {3,4}
                                          {1,2,3}
                                          {1,2,4}
Cf. A365073, A365311, A365312, A365322, A365380.
(End)

			The 7 partitions of 5 and their sets of parts are
[ #]  partition      set of parts
[ 1]  [ 1 1 1 1 1 ]  {1}
[ 2]  [ 2 1 1 1 ]    {1, 2}
[ 3]  [ 2 2 1 ]      {1, 2}  (same as before)
[ 4]  [ 3 1 1 ]      {1, 3}
[ 5]  [ 3 2 ]        {2, 3}
[ 6]  [ 4 1 ]        {1, 4}
[ 7]  [ 5 ]          {5}
so we have a(5) = |{{1}, {1, 2}, {1, 3}, {2, 3}, {1, 4}, {5}}| = 6.

Alois P. Heinz, Table of n, a(n) for n = 0..100

Cf. A182410.
The complement in subsets of {1..n-1} is A070880(n) = A365045(n) - 1.
The case of pairs is A365315, see also A365314, A365320, A365321.
A116861 and A364916 count linear combinations of strict partitions.
A179822 and A326080 count sum-closed subsets.
A326083 and A124506 appear to count combination-free subsets.
A364914 and A365046 count combination-full subsets.
Cf. A000009, A007865, A088528, A088809, A093971, A326020, A364272, A364534, A365043, A364350.

a066186 = sum . concat . ps 1 where
   ps _ 0 = [[]]
   ps i j = [t:ts | t <- [i..j], ts <- ps t (j - t)]
-- Reinhard Zumkeller, Jul 13 2013

list2set := L -> {op(L)};
a:= N -> list2set(map( list2set, combinat[partition](N) ));
seq(nops(a(n)), n=0..30);
#  Yogy Namara (yogy.namara(AT)gmail.com), Jan 13 2010
b:= proc(n, i) option remember; `if`(n=0, {{}}, `if`(i<1, {},
      {b(n, i-1)[], seq(map(x->{x[],i}, b(n-i*j, i-1))[], j=1..n/i)}))
    end:
a:= n-> nops(b(n, n)):
seq(a(n), n=0..40);
# Alois P. Heinz, Aug 09 2012

Table[Length[Union[Map[Union,IntegerPartitions[n]]]],{n,1,30}] (* Geoffrey Critzer, Feb 19 2013 *)
(* Second program: *)
b[n_, i_] := b[n, i] = If[n == 0, {{}}, If[i < 1, {},
     Union@Flatten@{b[n, i - 1], Table[If[Head[#] == List,
     Append[#, i]]& /@ b[n - i*j, i - 1], {j, 1, n/i}]}]];
a[n_] := Length[b[n, n]];
a /@ Range[0, 40] (* Jean-François Alcover, Jun 04 2021, after Alois P. Heinz *)
combp[n_,y_]:=With[{s=Table[{k,i},{k,y}, {i,1,Floor[n/k]}]}, Select[Tuples[s], Total[Times@@@#]==n&]];
Table[Length[Select[Join@@Array[IntegerPartitions,n], UnsameQ@@#&&combp[n,#]!={}&]], {n,0,15}] (* Gus Wiseman, Sep 11 2023 *)

from sympy.utilities.iterables import partitions
def A088314(n): return len({tuple(sorted(set(p))) for p in partitions(n)}) # Chai Wah Wu, Sep 10 2023

a(n) = 2^(n-1) - A070880(n). - Alois P. Heinz, Feb 08 2019

a(n) = A365042(n) + 1. - Gus Wiseman, Sep 13 2023

More terms and clearer definition from Vladeta Jovovic, Apr 21 2005

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

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

A326083 Number of subsets of {1..n} containing all of their pairwise sums <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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

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

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