A124506 -id:A124506 - cp's OEIS frontend

A365070 Number of subsets of {1..n} containing n and some element equal to the sum of two other (possibly equal) elements.

0, 0, 1, 1, 5, 9, 24, 46, 109, 209, 469, 922, 1932, 3858, 7952, 15831, 32214, 64351, 129813, 259566, 521681, 1042703, 2091626, 4182470, 8376007, 16752524, 33530042, 67055129, 134165194, 268328011, 536763582, 1073523097, 2147268041, 4294505929, 8589506814, 17178978145

Offset: 0

Gus Wiseman, Aug 24 2023

nonn

These are binary sum-full sets where elements can be re-used. The complement is counted by A288728. The non-binary version is A365046, complement A124506. For non-re-usable parts we have A364756, complement A085489.

			The subset {1,3} has no element equal to the sum of two others, so is not counted under a(3).
The subset {3,4,5} has no element equal to the sum of two others, so is not counted under a(5).
The subset {1,3,4} has 4 = 1 + 3, so is counted under a(4).
The subset {2,4,5} has 4 = 2 + 2, so is counted under a(5).
The a(0) = 0 through a(5) = 9 subsets:
  .  .  {1,2}  {1,2,3}  {2,4}      {1,2,5}
                        {1,2,4}    {1,4,5}
                        {1,3,4}    {2,3,5}
                        {2,3,4}    {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}

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

The complement w/o re-usable parts is A085489, first differences of A364755.
First differences of A093971.
The non-binary complement is A124506, first differences of A326083.
The complement is counted by A288728, first differences of A007865.
For partitions (not requiring n) we have A363225, strict A363226.
The case without re-usable parts is A364756, firsts differences of A088809.
The non-binary version is A365046, first differences of A364914.
A116861 and A364916 count linear combinations of strict partitions.
A364350 counts combination-free strict partitions, complement A364839.
A364913 counts combination-full partitions.
A365006 counts no positive combination-full strict ptns.
Cf. A050291, A051026, A151897, A236912, A237113, A237668, A326080, A364349, A364533, A364670.

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

First differences of A093971.

a(21) onwards added (using A093971) by Andrew Howroyd, Jan 13 2024

A365069 Number of subsets of {1..n} containing n and some element equal to the sum of two or more distinct other elements. A variation of non-binary sum-full subsets without re-usable elements.

Original entry on oeis.org

0, 0, 0, 1, 2, 7, 17, 41, 88, 201, 418, 892, 1838, 3798, 7716, 15740

Offset: 0

Gus Wiseman, Aug 26 2023

nonn

The complement is counted by A365071. The binary case is A364756. Allowing elements to be re-used gives A365070. A version for partitions (but not requiring n) is A237668.

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

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

The complement w/ re-usable parts is A288728, first differences of A007865.
First differences of A364534.
The binary complement is A364755, first differences of A085489.
The binary version is A364756, first differences of A088809.
The version with re-usable parts is A365070, first differences of A093971.
The complement is counted by A365071, first differences of A151897.
A124506 counts nonnegative combination-free subsets, differences of A326083.
A365046 counts nonnegative combination-full subsets, differences of A364914.
For partitions: A108917, A236912, A237113, A237668, A364532, A364913.
Strict partitions: A116861, A364272, A364349, A364350, A364839, A364916.
Cf. A050291, A326080, A363226, A364346, A364348, A364670.

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

a(n) = 2^(n-1) - A365070(n).

First differences of A364534.

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.

Original entry on oeis.org

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

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

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 3, 2, 3, 3, 6, 2, 8, 6, 7, 7, 15, 7, 20, 11, 18, 20, 36, 14, 44, 35, 45, 37, 83, 36, 109, 70, 101, 106, 174, 77, 246, 182, 227

Offset: 1

Steven Finch, Mar 13 2009

			a(5)=2: the 2 irreducible semigroups generated by {3, 4} and {2, 7} have Frobenius number 5.

S. R. Finch, Monoids of natural numbers
S. R. Finch, Monoids of natural numbers, March 17, 2009. [Cached copy, with permission of the author]
Calvin Leng, Christopher O'Neill, A sequence of quasipolynomials arising from random numerical semigroups, arXiv:1809.09915 [math.CO], 2018.
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).
Eric Weisstein's World of Mathematics, Frobenius number
Index entries for sequences related to semigroups

Cf. A124506.

A094367 a(n) = the number of numerical semigroups with three generators and Frobenius number n.

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 5, 2, 4, 4, 7, 1, 11, 7, 5, 7, 14, 5, 17, 6, 9, 16, 21, 2, 19, 15, 19, 10, 28, 6, 32, 12, 30, 23, 27, 5, 48, 29, 28, 12, 46, 11, 56, 19, 35, 40, 58, 10, 58, 24, 44, 30, 76, 16, 49, 23, 56, 46, 76, 7, 98, 46, 53, 34, 67, 21, 111, 43, 82, 40, 94, 11, 119, 49

Offset: 1

Talia Harrell (zeta_lady01(AT)yahoo.com), Apr 27 2004

nonn

A numerical semigroup is a set of natural numbers closed under addition. Its Frobenius number is the largest number not in it.

			a(10)=4 because there are four such semigroups with Frobenius number 10. Their complements (and a generating triple) are: {1,2,3,5,6,10} (4,7,9); {1,2,3,5,6,9,10} (4,7,13); {1,2,4,5,7,10} (3,8,13); {1,2,4,5,7,8,10} (3,11,13).

P. A. Garcia-Sanchez and J. C. Rosales, Numerical semigroups generated by intervals, Pacific J. Math. 191 (1999), no. 1, 75-83.
J. C. Rosales and M. B. Branco, Irreducible numerical semigroups, Pacific J. Math. 209 (2003), no. 1, 131-143.
J. C. Rosales, P. A. Garcia-Sanchez and J. I. Garcia-Garcia, Every positive integer is the Frobenius number of a numerical semigroup with three generators, Math. Scand. 94 (2004), no. 1, 5-12.

Cf. A094365, A094366, A124506.

Edited by Don Reble, Apr 26 2007

A386243 a(n) is the smallest possible g(k) in a set of increasing numbers g(1) < g(2) < ... < g(k) having Frobenius number n.

Original entry on oeis.org

3, 5, 5, 7, 4, 7, 5, 9, 7, 9, 5, 9, 8, 11, 10, 11, 7, 13, 6, 9, 11, 10, 7, 13, 11, 11, 8, 13, 7, 13, 9, 13, 14, 13, 11, 13, 12, 13, 11, 17, 8, 17, 12, 17, 14, 16, 9, 19, 11, 17, 14, 17, 10, 13, 9, 17, 15, 17, 11, 18, 15, 19, 16, 15, 12, 16, 16, 18, 11, 17, 10, 19, 17, 17, 18, 18, 15

Offset: 1

Gordon Hamilton, Jul 16 2025

			a(15) = 10 because the set {6,7,10} has the Frobenius number of 15. No set of the form {..., 9} or {..., 8}, etc. has a Frobenius number of 15.

David A. Corneth, Table of n, a(n) for n = 1..415
David A. Corneth, All solutions for n = 1..415 where no number is a divisor of another number
Shunichi Matsubara, The Computational Complexity of the Frobenius Problem, arXiv:1602.05657, 2016. [Background information]
Wikipedia, Coin problem

Cf. A028387, A079326, A124506, A138984, A138985.

More terms from David A. Corneth, Jul 16 2025

A158278 Number of symmetric numerical semigroups with Frobenius number 2n-1; that is, symmetric numerical semigroups for which the largest integer not belonging to them is 2n-1.

Original entry on oeis.org

1, 1, 2, 3, 3, 6, 8, 7, 15, 20, 18, 36, 44, 45, 83, 109, 101, 174, 246, 227

Offset: 1

Steven Finch, Mar 15 2009

			a(3)=2: the only 2 symmetric semigroups with Frobenius number 5=2*3-1 are generated by {3, 4} and {2, 7}.

CombOS - Combinatorial Object Server, Generate numerical semigroups
S. R. Finch, Monoids of natural numbers
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. A124506, A158206.

a(n) = A158206(2*n-1).

A158279 Number of pseudo-symmetric numerical semigroups with Frobenius number 2n; that is, pseudo-symmetric numerical semigroups for which the largest integer not belonging to them is 2n.

Original entry on oeis.org

1, 1, 1, 2, 3, 2, 6, 7, 7, 11, 20, 14, 35, 37, 36, 70, 106, 77, 182

Offset: 1

Steven Finch, Mar 15 2009

			a(3)=1: the unique pseudo-symmetric semigroup with Frobenius number 6=2*3 is generated by {4, 5, 7}.

S. R. Finch, Monoids of natural numbers
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. A124506, A158206.

a(n) = A158206(2*n).

A210581 Bras-Amorós number f_n for numerical semigroups of genus n.

Original entry on oeis.org

1, 2, 7, 23, 68, 200, 615, 1764, 5060, 14626, 41785, 117573, 332475, 933891, 2609832, 7278512

Offset: 0

Jonathan Vos Post, Mar 22 2012

M. Bernardini, Fernando Torres, Counting numerical semigroups by genus and even gaps, arXiv:1612.01212 [math.CO], 2016-2017; Discrete Mathematics 340.12 (2017): 2853-2863.
Maria Bras-Amorós, Ordinarization Transform of a Numerical Semigroup and Semigroups with a Large Number of Intervals, arXiv:1203.5000 [math.NT], 2012. See Table on p. 11.

Cf. A007323, A124506.

a(15) from Maria Bras-Amorós, Mar 23 2021

cp's OEIS Frontend

A365070 Number of subsets of {1..n} containing n and some element equal to the sum of two other (possibly equal) elements.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A365069 Number of subsets of {1..n} containing n and some element equal to the sum of two or more distinct other elements. A variation of non-binary sum-full subsets without re-usable elements.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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

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

Views

Author

Keywords

Examples

Links

Crossrefs

A094367 a(n) = the number of numerical semigroups with three generators and Frobenius number n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A386243 a(n) is the smallest possible g(k) in a set of increasing numbers g(1) < g(2) < ... < g(k) having Frobenius number n.

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions

A158278 Number of symmetric numerical semigroups with Frobenius number 2*n-1; that is, symmetric numerical semigroups for which the largest integer not belonging to them is 2*n-1.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A158279 Number of pseudo-symmetric numerical semigroups with Frobenius number 2*n; that is, pseudo-symmetric numerical semigroups for which the largest integer not belonging to them is 2*n.

Views

A158278 Number of symmetric numerical semigroups with Frobenius number 2n-1; that is, symmetric numerical semigroups for which the largest integer not belonging to them is 2n-1.

A158279 Number of pseudo-symmetric numerical semigroups with Frobenius number 2n; that is, pseudo-symmetric numerical semigroups for which the largest integer not belonging to them is 2n.