A151897 -id:A151897 - cp's OEIS frontend

A365071 Number of subsets of {1..n} containing n such that no element is a sum of distinct other elements. A variation of non-binary sum-free subsets without re-usable elements.

0, 1, 2, 3, 6, 9, 15, 23, 40, 55, 94, 132, 210, 298, 476, 644, 1038, 1406, 2149, 2965, 4584, 6077, 9426, 12648, 19067, 25739, 38958, 51514, 78459, 104265, 155436, 208329, 312791, 411886, 620780, 823785, 1224414, 1631815, 2437015, 3217077, 4822991

Offset: 0

Gus Wiseman, Aug 26 2023

nonn

The complement is counted by A365069. The binary version is A364755, complement A364756. For re-usable parts we have A288728, complement A365070.

			The subset {1,3,4,6} has 4 = 1 + 3 so is not counted under a(6).
The subset {2,3,4,5,6} has 6 = 2 + 4 and 4 = 1 + 3 so is not counted under a(6).
The a(0) = 0 through a(6) = 15 subsets:
  .  {1}  {2}    {3}    {4}      {5}      {6}
          {1,2}  {1,3}  {1,4}    {1,5}    {1,6}
                 {2,3}  {2,4}    {2,5}    {2,6}
                        {3,4}    {3,5}    {3,6}
                        {1,2,4}  {4,5}    {4,6}
                        {2,3,4}  {1,2,5}  {5,6}
                                 {1,3,5}  {1,2,6}
                                 {2,4,5}  {1,3,6}
                                 {3,4,5}  {1,4,6}
                                          {2,3,6}
                                          {2,5,6}
                                          {3,4,6}
                                          {3,5,6}
                                          {4,5,6}
                                          {3,4,5,6}

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

First differences of A151897.
The version with re-usable parts is A288728 first differences of A007865.
The binary version is A364755, first differences of A085489.
The binary complement is A364756, first differences of A088809.
The complement is counted by A365069, first differences of A364534.
The complement w/ re-usable parts is A365070, first differences of A093971.
A108917 counts knapsack partitions, strict A275972.
A124506 counts combination-free subsets, differences of A326083.
A364350 counts combination-free strict partitions, complement A364839.
A365046 counts combination-full subsets, differences of A364914.
Partitions: A236912, A237113, A237668, A364532, A364272, A364349, A364913.
Cf. A050291, A095944, A103580, A324741, A326080, A326117, A341507, A364533.

Table[Length[Select[Subsets[Range[n]], MemberQ[#,n]&&Intersection[#, Total/@Subsets[#,{2,Length[#]}]]=={}&]], {n,0,10}]

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

First differences of A151897.

a(14) onwards added (using A151897) by Andrew Howroyd, Jan 13 2024

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

Original entry on oeis.org

0, 1, 2, 6, 10, 28, 48, 116, 224, 480, 920, 2000, 3840, 7984, 15936, 32320, 63968, 130176, 258304, 521920, 1041664, 2089472, 4171392, 8377856, 16726528, 33509632, 67004416, 134129664, 268111360, 536705024, 1072961536, 2146941952, 4293509120, 8588414976

Offset: 1

Gus Wiseman, Sep 09 2023

nonn

			The a(2) = 1 through a(5) = 10 partitions:
  {1}  {1}    {1}      {1}
       {1,2}  {2}      {1,2}
              {1,2}    {1,3}
              {1,3}    {1,4}
              {2,3}    {2,3}
              {1,2,3}  {1,2,3}
                       {1,2,4}
                       {1,3,4}
                       {2,3,4}
                       {1,2,3,4}

The case of positive coefficients is A365042, complement A365045.
For subsets of {1..n} instead of {1..n-1} we have A365073.
The binary complement is A365315.
The complement is counted by A365380.
A124506 and A326083 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, A088314, A088809, A151897, A364534, A364839, A365314, A365322.

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-1]],combs[n,#]!={}&]],{n,5}]

from itertools import combinations
from sympy.utilities.iterables import partitions
def A365542(n):
    a = {tuple(sorted(set(p))) for p in partitions(n)}
    return sum(1 for m in range(1,n) for b in combinations(range(1,n),m) if any(set(d).issubset(set(b)) for d in a)) # Chai Wah Wu, Sep 12 2023

More terms from Alois P. Heinz, Sep 13 2023

A326025 Number of maximal subsets of {1..n} containing no sums or products of distinct elements.

Original entry on oeis.org

1, 1, 2, 2, 2, 4, 5, 10, 13, 20, 28, 40, 54, 82, 120, 172, 244, 347, 471, 651, 874, 1198, 1635, 2210, 2867, 3895, 5234, 6889, 9019, 11919, 15629, 20460, 26254, 33827, 43881, 56367, 71841, 91834, 117695, 148503, 188039, 311442, 390859, 488327, 610685, 759665

Offset: 0

Gus Wiseman, Jul 09 2019

nonn

			The a(1) = 1 through a(8) = 13 maximal subsets:
  {1}  {1}  {1}    {1}      {1}      {1}        {1}        {1}
       {2}  {2,3}  {2,3,4}  {2,3,4}  {2,3,4}    {2,3,4}    {2,3,4}
                            {2,4,5}  {2,4,5}    {2,3,7}    {2,4,5}
                            {3,4,5}  {2,5,6}    {2,4,5}    {2,4,7}
                                     {3,4,5,6}  {2,4,7}    {2,5,6}
                                                {2,5,6}    {2,5,8}
                                                {2,6,7}    {2,6,7}
                                                {3,4,5,6}  {2,3,7,8}
                                                {3,5,6,7}  {3,4,5,6}
                                                {4,5,6,7}  {3,4,6,8}
                                                           {3,5,6,7}
                                                           {3,6,7,8}
                                                           {4,5,6,7,8}

Andrew Howroyd, PARI Program

Maximal subsets without sums of distinct elements are A326498.
Maximal subsets without products of distinct elements are A325710.
Subsets without sums or products of distinct elements are A326024.
Subsets with sums (and products) are A326083.
Maximal sum-free and product-free subsets are A326497.
Cf. A007865, A051026, A121269, A151897, A326116, A326117, A326491, A326495, A326496.

fasmax[y_]:=Complement[y,Union@@(Most[Subsets[#]]&/@y)];
Table[Length[fasmax[Select[Subsets[Range[n]],Intersection[#,Union[Plus@@@Subsets[#,{2,n}],Times@@@Subsets[#,{2,n}]]]=={}&]]],{n,0,10}]

\\ See link for program file.
for(n=0, 25, print1(A326025(n), ", ")) \\ Andrew Howroyd, Aug 29 2019

a(16)-a(40) from Andrew Howroyd, Aug 29 2019

a(41)-a(45) from Jinyuan Wang, Oct 03 2020

A364752 Number of subsets of {1..n} containing n and all first differences.

Original entry on oeis.org

1, 1, 2, 2, 4, 4, 9, 11, 24, 38, 75, 131, 263, 476, 928, 1750, 3386, 6439, 12455, 23853, 46097, 88709, 171471, 330939, 640472, 1238755, 2400154, 4650857, 9022792, 17510820, 34015138, 66106492, 128571563, 250191929, 487175381, 949133736, 1850223956, 3608650389

Offset: 0

Gus Wiseman, Aug 06 2023

nonn

			The a(1) = 1 through a(6) = 9 subsets:
  {1}  {2}    {3}      {4}        {5}          {6}
       {1,2}  {1,2,3}  {2,4}      {1,2,3,5}    {3,6}
                       {1,2,4}    {1,2,4,5}    {2,4,6}
                       {1,2,3,4}  {1,2,3,4,5}  {1,2,3,6}
                                               {1,2,4,6}
                                               {1,2,3,4,6}
                                               {1,2,3,5,6}
                                               {1,2,4,5,6}
                                               {1,2,3,4,5,6}

Rémy Sigrist, C++ program

Partial sums are A364671, complement A364672.
The complement is counted by A364753.
A054519 counts subsets containing differences, A326083 containing sums.
A364463 counts subsets disjoint from differences, complement A364466.
A364673 counts partitions containing differences, A364674, A364675.
Cf. A151897, A196723, A237668, A325325, A363225, A364345, A364464, A364537.

Table[If[n==0,1,Length[Select[Subsets[Range[n]], MemberQ[#,n]&&SubsetQ[#,Differences[#]]&]]],{n,0,10}]

More terms from Rémy Sigrist, Aug 06 2023

A326024 Number of subsets of {1..n} containing no sums or products of distinct elements.

Original entry on oeis.org

1, 2, 3, 5, 9, 15, 25, 41, 68, 109, 179, 284, 443, 681, 1062, 1587, 2440, 3638, 5443, 8021, 11953, 17273, 25578, 37001, 53953, 77429, 113063, 160636, 232928, 330775, 475380, 672056, 967831, 1359743, 1952235, 2743363, 3918401, 5495993, 7856134, 10984547, 15669741

Offset: 0

Gus Wiseman, Jul 09 2019

nonn

			The a(0) = 1 through a(5) = 15 subsets:
  {}  {}   {}   {}     {}       {}
      {1}  {1}  {1}    {1}      {1}
           {2}  {2}    {2}      {2}
                {3}    {3}      {3}
                {2,3}  {4}      {4}
                       {2,3}    {5}
                       {2,4}    {2,3}
                       {3,4}    {2,4}
                       {2,3,4}  {2,5}
                                {3,4}
                                {3,5}
                                {4,5}
                                {2,3,4}
                                {2,4,5}
                                {3,4,5}

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

Subsets without sums of distinct elements are A151897.
Subsets without products of distinct elements are A326117.
Maximal subsets without sums or products of distinct elements are A326025.
Subsets with sums (and products) are A326083.
Sum-free and product-free subsets are A326495.
Cf. A007865, A051026, A121269, A325710, A326076, A326489, A326497, A326498.

Table[Length[Select[Subsets[Range[n]],Intersection[#,Union[Plus@@@Subsets[#,{2,n}],Times@@@Subsets[#,{2,n}]]]=={}&]],{n,0,10}]

a(n)={
   my(recurse(k, es, ep)=
    if(k > n, 1,
      my(t = self()(k + 1, es, ep));
      if(!bittest(es,k) && !bittest(ep,k),
         es = bitor(es, bitand((2<Andrew Howroyd, Aug 25 2019

Terms a(16)-a(40) from Andrew Howroyd, Aug 25 2019

A364753 Number of subsets of {1..n} containing n but not containing all first differences.

Original entry on oeis.org

0, 0, 0, 2, 4, 12, 23, 53, 104, 218, 437, 893, 1785, 3620, 7264, 14634, 29382, 59097, 118617, 238291, 478191, 959867, 1925681, 3863365, 7748136, 15538461, 31154278, 62458007, 125194936, 250924636, 502855774, 1007635332, 2018912085, 4044775367, 8102759211, 16230735448, 32509514412, 65110826347

Offset: 0

Gus Wiseman, Aug 06 2023

nonn

In other words, subsets containing both n and some element that is not the difference of two consecutive elements.

			The a(1) = 0 through a(6) = 23 subsets:
  .  .  {1,3}  {1,4}    {1,5}      {1,6}
        {2,3}  {3,4}    {2,5}      {2,6}
               {1,3,4}  {3,5}      {4,6}
               {2,3,4}  {4,5}      {5,6}
                        {1,2,5}    {1,2,6}
                        {1,3,5}    {1,3,6}
                        {1,4,5}    {1,4,6}
                        {2,3,5}    {1,5,6}
                        {2,4,5}    {2,3,6}
                        {3,4,5}    {2,5,6}
                        {1,3,4,5}  {3,4,6}
                        {2,3,4,5}  {3,5,6}
                                   {4,5,6}
                                   {1,2,5,6}
                                   {1,3,4,6}
                                   {1,3,5,6}
                                   {1,4,5,6}
                                   {2,3,4,6}
                                   {2,3,5,6}
                                   {2,4,5,6}
                                   {3,4,5,6}
                                   {1,3,4,5,6}
                                   {2,3,4,5,6}

Partial sums are A364672, complement A364671.
The complement is counted by A364752.
A054519 counts subsets containing differences, A326083 containing sums.
A364463 counts subsets disjoint from differences, complement A364466.
A364673, A364674, A364675 count partitions containing differences.
Cf. A151897, A196723, A237668, A325325, A364345, A364464, A364537.

Table[Length[Select[Subsets[Range[n]],MemberQ[#,n]&&!SubsetQ[#,Differences[#]]&]],{n,0,10}]

More terms from Giorgos Kalogeropoulos, Aug 07 2023

A365072 Number of integer partitions of n such that no distinct part can be written as a (strictly) positive linear combination of the other distinct parts.

Original entry on oeis.org

1, 1, 2, 2, 3, 3, 4, 5, 6, 8, 9, 17, 15, 31, 34, 53, 65, 109, 117, 196, 224, 328, 405, 586, 673, 968, 1163, 1555, 1889, 2531, 2986, 3969, 4744, 6073, 7333, 9317, 11053, 14011, 16710, 20702, 24714, 30549, 36127, 44413, 52561, 63786, 75583, 91377, 107436, 129463

Offset: 0

Gus Wiseman, Aug 31 2023

nonn

We consider (for example) that 2x + y + 3z is a positive linear combination of (x,y,z), but 2x + y is not, as the coefficient of z is 0.

			The a(1) = 1 through a(8) = 6 partitions:
  (1)  (2)   (3)    (4)     (5)      (6)       (7)        (8)
       (11)  (111)  (22)    (32)     (33)      (43)       (44)
                    (1111)  (11111)  (222)     (52)       (53)
                                     (111111)  (322)      (332)
                                               (1111111)  (2222)
                                                          (11111111)
The a(11) = 17 partitions:
  (11)  (9,2)  (7,2,2)  (5,3,2,1)  (4,3,2,1,1)  (1,1,1,1,1,1,1,1,1,1,1)
        (8,3)  (6,3,2)  (5,2,2,2)  (3,2,2,2,2)
        (7,4)  (5,4,2)  (4,3,2,2)
        (6,5)  (5,3,3)  (3,3,3,2)
               (4,4,3)

The nonnegative version is A364915, strict A364350.
The strict case is A365006.
For subsets instead of partitions we have A365044, complement A365043.
A000041 counts integer partitions, strict A000009.
A008284 counts partitions by length, strict A008289.
A116861 and A364916 count linear combinations of strict partitions.
A237667 counts sum-free partitions, binary A236912.
A364912 counts positive linear combinations of partitions.
A365068 counts combination-full partitions, strict A364839.
Cf. A085489, A108917, A151897, A325862, A364272, A364910, A364911, A364913.

combp[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,1,Floor[n/k]}]}, Select[Tuples[s],Total[Times@@@#]==n&]];
Table[Length[Select[Union/@IntegerPartitions[n], Function[ptn,!Or@@Table[combp[ptn[[k]],Delete[ptn,k]]!={}, {k,Length[ptn]}]]@*Union]],{n,0,15}]

from sympy.utilities.iterables import partitions
def A365072(n):
    if n <= 1: return 1
    alist = [set(tuple(sorted(set(p))) for p in partitions(i)) for i in range(n)]
    c = 1
    for p in partitions(n,k=n-1):
        s = set(p)
        for q in s:
            if tuple(sorted(s-{q})) in alist[q]:
                break
        else:
            c += 1
    return c # Chai Wah Wu, Sep 20 2023

a(31)-a(49) from Chai Wah Wu, Sep 20 2023

A358392 Number of nonempty subsets of {1, 2, ..., n} with GCD equal to 1 and containing the sum of any two elements whenever it is at most n.

Original entry on oeis.org

1, 1, 2, 3, 7, 9, 19, 27, 46, 63, 113, 148, 253, 345, 539, 734, 1198, 1580, 2540, 3417, 5233, 7095, 11190, 14720, 22988, 31057, 47168, 63331, 98233, 129836, 200689, 269165, 406504, 546700, 838766, 1108583, 1700025, 2281517, 3437422, 4597833, 7023543, 9308824, 14198257, 18982014, 28556962

Offset: 1

Max Alekseyev, Nov 13 2022

nonn

Also, the number of distinct numerical semigroups that are generated by some subset of {1, 2, ..., n} and have a finite complement in the positive integers.

Max Alekseyev, Table of n, a(n) for n = 1..100
Marcel K. Goh et al., Counting numerical semigroups by largest element of minimal generating set, MathOverflow, 2022.

Inverse Moebius transform of A103580.

Cf. A007865, A050291, A051026, A085489, A139384, A151897, A308546, A326020, A326076, A326080, A326083, A326114.

a(n) = Sum_{k=1..n} moebius(k) * A103580(floor(n/k)).

A364841 Number of subsets S of {1..n} containing no element equal to the sum of a k-multiset of elements of S, for any 2 <= k <= |S|.

Original entry on oeis.org

1, 2, 3, 6, 9, 15, 21, 34, 49, 75, 105

Offset: 0

Gus Wiseman, Aug 15 2023

			The a(0) = 1 through a(5) = 15 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}
                              {2,3}
                              {2,5}
                              {3,4}
                              {3,5}
                              {4,5}
                              {3,4,5}

Cf. A007865, A085489, A103580, A151897, A236912, A326020, A326080, A326083, A364349, A364534.

Table[Length[Select[Subsets[Range[n]], Intersection[#,Join@@Table[Total/@Tuples[#,k], {k,2,Length[#]}]]=={}&]],{n,0,10}]

cp's OEIS Frontend

A365071 Number of subsets of {1..n} containing n such that no element is a sum of distinct other elements. A variation of non-binary sum-free subsets without re-usable elements.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Python

Extensions

A326025 Number of maximal subsets of {1..n} containing no sums or products of distinct elements.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A364752 Number of subsets of {1..n} containing n and all first differences.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A326024 Number of subsets of {1..n} containing no sums or products of distinct elements.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A364753 Number of subsets of {1..n} containing n but not containing all first differences.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A365072 Number of integer partitions of n such that no distinct part can be written as a (strictly) positive linear combination of the other distinct parts.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Python

Extensions

A358392 Number of nonempty subsets of {1, 2, ..., n} with GCD equal to 1 and containing the sum of any two elements whenever it is at most n.

Views

Author

Keywords