A066062 -id:A066062 - cp's OEIS frontend

A365045 Number of subsets of {1..n} containing n such that no element can be written as a positive linear combination of the others.

0, 1, 1, 2, 4, 11, 23, 53, 111, 235, 483, 988, 1998, 4036, 8114, 16289, 32645, 65389, 130887, 261923, 524014, 1048251, 2096753, 4193832, 8388034, 16776544, 33553622, 67107919, 134216597, 268434140, 536869355, 1073740012, 2147481511, 4294964834, 8589931700

Offset: 0

Gus Wiseman, Aug 24 2023

nonn

Also subsets of {1..n} containing n whose greatest element cannot be written as a positive linear combination of the others.

			The subset {3,4,10} has 10 = 2*3 + 1*4 so is not counted under a(10).
The a(0) = 0 through a(5) = 11 subsets:
  .  {1}  {2}  {3}    {4}        {5}
               {2,3}  {3,4}      {2,5}
                      {2,3,4}    {3,5}
                      {1,2,3,4}  {4,5}
                                 {2,4,5}
                                 {3,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 nonempty case is A070880.
The nonnegative version is A124506, first differences of A326083.
The binary version is A288728, first differences of A007865.
A subclass is A341507.
The complement is counted by A365042, first differences of A365043.
First differences of A365044.
The nonnegative complement is A365046, first differences of A364914.
The binary complement is A365070, first differences of A093971.
Without re-usable parts we have A365071, first differences of A151897.
A085489 and A364755 count subsets w/o the sum of two distinct elements.
A088809 and A364756 count subsets with the sum of two distinct elements.
A364350 counts combination-free strict partitions, complement A364839.
A364913 counts combination-full partitions.
Cf. A237113, A237668, A308546, A324736, A326020, A326080, A364272, A364349, A364534, A365069.

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

a(n) = A070880(n) + 1 for n > 0.

A365920 Greatest non-subset-sum of the prime indices of n, or 0 if there is none.

Original entry on oeis.org

0, 0, 1, 0, 2, 0, 3, 0, 3, 2, 4, 0, 5, 3, 4, 0, 6, 0, 7, 0, 5, 4, 8, 0, 5, 5, 5, 3, 9, 0, 10, 0, 6, 6, 6, 0, 11, 7, 7, 0, 12, 0, 13, 4, 6, 8, 14, 0, 7, 5, 8, 5, 15, 0, 7, 0, 9, 9, 16, 0, 17, 10, 7, 0, 8, 4, 18, 6, 10, 6, 19, 0, 20, 11, 7, 7, 8, 5, 21, 0, 7, 12

Offset: 1

Gus Wiseman, Sep 30 2023

nonn

This is the greatest element of {0,...,A056239(n)} that is not equal to A056239(d) for any divisor d|n, d>1. This definition is analogous to the Frobenius number of a numerical semigroup (see link), but it looks only at submultisets of a finite multiset, not all multisets of elements of a set.

A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.

			The prime indices of 156 are {1,1,2,6}, with subset-sums 0, 1, 2, 3, 4, 6, 7, 8, 9, 10, so a(156) = 5.

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

For binary indices instead of sums we have A063250.
Positions of first appearances > 2 are A065091.
Zeros are A325781, nonzeros A325798.
For prime indices instead of sums we have A339662, minimum A257993.
For least instead of greatest non-subset-sum we have A366128.
A055932 lists numbers whose prime indices cover an initial interval.
A056239 adds up prime indices, row sums of A112798.
A073491 lists numbers with gap-free prime indices.
A238709/A238710 count partitions by least/greatest difference.
A342050/A342051 have prime indices with odd/even least gap.
Cf. A001223, A001522, A005117, A079068, A098743, A264401, A286469 or A286470, A339737, A339886.

prix[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
nmz[y_]:=Complement[Range[Total[y]],Total/@Subsets[y]];
Table[Max@@Prepend[nmz[prix[n]],0],{n,100}]

A365044 Number of subsets of {1..n} whose greatest element cannot be written as a (strictly) positive linear combination of the others.

Original entry on oeis.org

1, 2, 3, 5, 9, 20, 43, 96, 207, 442, 925, 1913, 3911, 7947, 16061, 32350, 64995, 130384, 261271, 523194, 1047208, 2095459, 4192212, 8386044, 16774078, 33550622, 67104244, 134212163, 268428760, 536862900, 1073732255, 2147472267, 4294953778, 8589918612, 17179850312

Offset: 0

Gus Wiseman, Aug 26 2023

nonn

Sets of this type may be called "positive combination-free".

Also subsets of {1..n} such that no element can be written as a (strictly) positive linear combination of the others.

			The subset S = {3,5,6,8} has 6 = 2*3 + 0*5 + 0*8 and 8 = 1*3 + 1*5 + 0*6 but neither of these is strictly positive, so S is counted under a(8).
The a(0) = 1 through a(5) = 20 subsets:
  {}  {}   {}   {}     {}         {}
      {1}  {1}  {1}    {1}        {1}
           {2}  {2}    {2}        {2}
                {3}    {3}        {3}
                {2,3}  {4}        {4}
                       {2,3}      {5}
                       {3,4}      {2,3}
                       {2,3,4}    {2,5}
                       {1,2,3,4}  {3,4}
                                  {3,5}
                                  {4,5}
                                  {2,3,4}
                                  {2,4,5}
                                  {3,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 version is A007865, first differences A288728.
The binary complement is A093971, first differences A365070.
Without re-usable parts we have A151897, first differences A365071.
The nonnegative version is A326083, first differences A124506.
A subclass is A341507.
The nonnegative complement is A364914, first differences A365046.
The complement is counted by A365043, first differences A365042.
First differences are A365045.
A085489 and A364755 count subsets w/o the sum of two distinct elements.
A088809 and A364756 count subsets with the sum of two distinct elements.
A364350 counts combination-free strict partitions, complement A364839.
A364913 counts combination-full partitions.
Cf. A006951, A237113, A237668, A308546, A324736, A326020, A326080, A364272, A364349, A364534, A365069.

combp[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,1,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
Table[Length[Select[Subsets[Range[n]],And@@Table[combp[Last[#],Union[Most[#]]]=={},{k,Length[#]}]&]],{n,0,10}]

from itertools import combinations
from sympy.utilities.iterables import partitions
def A365044(n):
    mlist = tuple({tuple(sorted(p.keys())) for p in partitions(m,k=m-1)} for m in range(1,n+1))
    return n+1+sum(1 for k in range(2,n+1) for w in combinations(range(1,n+1),k) if w[:-1] not in mlist[w[-1]-1]) # Chai Wah Wu, Nov 20 2023

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

a(15)-a(34) from Chai Wah Wu, Nov 20 2023

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

Original entry on oeis.org

0, 0, 1, 2, 4, 5, 9, 11, 17, 21, 29, 36, 50, 60, 78, 95, 123, 147, 185, 221, 274, 325, 399, 472, 574, 672, 810, 945, 1131, 1316, 1557, 1812, 2137, 2462, 2892, 3322, 3881, 4460, 5176, 5916, 6846, 7817, 8993, 10250, 11765, 13333, 15280, 17308, 19731, 22306

Offset: 0

Gus Wiseman, Aug 23 2023

nonn

Sets of this type may be called "positive combination-full".

Also subsets of {1..n} containing n whose greatest element can be written as a positive linear combination of the others.

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

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

The nonnegative complement is A124506, first differences of A326083.
The binary complement is A288728, first differences of A007865.
First differences of A365043.
The complement is counted by A365045, first differences of A365044.
The nonnegative version is A365046, first differences of A364914.
Without re-usable parts we have A365069, first differences of A364534.
The binary version is A365070, first differences of A093971.
A085489 and A364755 count subsets with no sum of two distinct elements.
A088314 counts sets that can be linearly combined to obtain n.
A088809 and A364756 count subsets with some sum of two distinct elements.
A364350 counts combination-free strict partitions, complement A364839.
A364913 counts combination-full partitions.
Cf. A151897, A237113, A237668, A308546, A324736, A326020, A326080, A364272.

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

a(n) = A088314(n) - 1.

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

Original entry on oeis.org

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.

A007323 Number of numerical semigroups of genus n; conjecturally also the number of power sum bases for symmetric functions in n variables.

Original entry on oeis.org

1, 1, 2, 4, 7, 12, 23, 39, 67, 118, 204, 343, 592, 1001, 1693, 2857, 4806, 8045, 13467, 22464, 37396, 62194, 103246, 170963, 282828, 467224, 770832, 1270267, 2091030, 3437839, 5646773, 9266788, 15195070, 24896206, 40761087, 66687201, 109032500

Offset: 0

Don Zagier (don.zagier(AT)mpim-bonn.mpg.de), Apr 11 1994

From Don Zagier's email of Apr 11 1994: (Start)
Given n, one knows that the field of symmetric functions in n variables a_1,...,a_n is the field Q(sigma_1,...,sigma_n), where sigma_i is the i-th elementary symmetric polynomial. Here one has no choice, because sigma_i=0 for i>n and fewer than n sigma's would not suffice.
But, by Newton's formulas, the field is also given as Q(s_1,...,s_n) where s_i is the i-th power sum, and now one can ask whether some other sequence s_{j_1},...,s_{j_n} (0For n=1 the only possibility is clearly s_1, since Q(s_i) = Q(a^i) does not coincide with Q(a) for i>1, but for n=2 one has two possibilities Q(s_1,s_2) or Q(s_1,s_3), since from s_1=a+b and s_3=a^3+b^3 one can reconstruct s_2 = (s_1^3+2s_3)/3s_1.
Similarly, for n=3 one has the possibilities (123), (124), (125), and (135) (the formula in the last case is s_2 = (s_1^5+5s_1^2s_3-6s_5)/5(s_1^3-s_3); one can find the corresponding formulas in the other cases easily) and for n=4 there are 7: 1234, 1235, 1236, 1237, 1245, 1247, and 1357.
A theorem of Kakutani (I do not know a reference) says that the sequences which occur are exactly the finite subsets of N whose complements are additive semigroups (for instance, the complement of {1,2,4,7} is 3,5,6,8,9,..., which is closed under addition).
This is a really beautiful theorem. I wrote a simple program to count the sets of cardinality n which have the property in question for n = 1, ..., 16. (End)
This sequence relates to numerical semigroups, which are basic fundamental objects but little known: A numerical semigroup S < N is defined by being: closed under addition, contains zero and N \ S is finite. [John McKay, Jun 09 2011]
The theorem alluded to in the email by Zagier is due to Kakeya, not Kakutani (see references.) The theorem states that if a sequence of n positive integers k1, k2,..., kn forms the complement of a numerical semigroup, then the power sums p_k1, p_k2,..., p_kn forms a basis for the rational function field of symmetric functions in n variables. Kakeya conjectures that every power sum basis of the symmetric functions has this property, but this is still an open problem. Thanks to user Gjergji Zaimi on Math Overflow for the references. [Trevor Hyde, Oct 18 2018]

			G.f. = x + 2*x^2 + 4*x^3 + 7*x^4 + 12*x^5 + 23*x^6 + 39*x^7 + 67*x^8 + ...
a(1) = 1 because the unique numerical semigroup with genus 1 is N \ {1}
a(3) = 4 because the four numerical semigroups with genus 3 are N \ {1,2,3}, N \ {1,2,4}, N \ {1,2,5}, and N \ {1,3,5}

Sean Clark, Anton Preslicka, Josh Schwartz and Radoslav Zlatev, Some combinatorial conjectures on a family of toric ideals: A report from the MSRI 2011 Commutative Algebra graduate workshop.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Maria Bras-Amorós, Table of n, a(n) for n = 0..77
Matheus Bernardini, Counting numerical semigroups by genus and even gaps via Kunz-coordinate vectors, arXiv:1906.07310 [math.CO], 2019.
Matheus Bernardini and Gilberto Brito, On Pure k-sparse gapsets, arXiv:2106.13296 [math.CO], 2021.
Matheus Bernardini and Fernando Torres, Counting numerical semigroups by genus and even gaps, arXiv:1612.01212 [math.CO], 2016-2017.
Matheus Bernardini and Fernando Torres, Counting numerical semigroups by genus and even gaps, Discrete Mathematics 340.12 (2017): 2853-2863.
Matheus Bernardini and Patrick Melo, A short note on a theorem by Eliahou and Fromentin, arXiv:2202.07694 [math.CO], 2022.
Victor Blanco and Justo Puerto, Computing the number of numerical semigroups using generating functions, arXiv:0901.1228 [math.CO], 2009.
Maria Bras-Amorós, Home Page [Has many of these references]
Maria Bras-Amorós, Algebraic Geometry, Coding and Computing, Segovia, Spain, 2007.
Maria Bras-Amorós, IMNS 2018, Granada, Spain, 2008.
Maria Bras-Amorós, Fibonacci-Like Behavior of the Number of Numerical Semigroups of a Given Genus, Semigroup Forum, 76 (2008), 379-384. See also, arXiv:1706.05230 [math.NT], 2017.
Maria Bras-Amorós, Bounds on the Number of Numerical Semigroups of a Given Genus, Journal of Pure and Applied Algebra, vol. 213, n. 6 (2009), pp. 997-1001. arXiv:0802.2175.
Maria Bras-Amorós, Exploring the unleaved tree of numerical semigroups up to a given genus, arXiv:2503.14664 [math.CO], 2025. See pp. 1, 15.
Maria Bras-Amorós, Exploring the unleaved tree of numerical semigroups up to a given genus, arXiv:2503.14664 [math.CO], 2025.
Maria Bras-Amorós and S. Bulygin, Towards a Better Understanding of the Semigroup Tree, arXiv:0810.1619 [math.CO], 2008; Semigroup Forum 79 (2009) 561-574.
Maria Bras-Amorós and A. de Mier, Representation of Numerical Semigroups by Dyck Paths, arXiv:math/0612634 [math.CO], 2006; Semigroup Forum 75 (2007) 676-681.
Maria Bras-Amorós and J. Fernández-González, arXiv version, arXiv:1607.01545 [math.CO], 2016-2017; Computation of numerical semigroups by means of seeds, Mathematics of Computation 87 (313), American Mathematical Society, 2539-2550, September 2018.
Maria Bras-Amorós and J. Fernández-González, The right-generators descendant of a numerical semigroup, Math. Comp. 89 (2020), 2017-2030. arXiv:1911.03173 [math.CO].
Gilberto Brito and Stéfani Vieira, A certain sequence on pure kappa-sparse gapsets, arXiv:2407.21563 [math.CO], 2024. See p. 2.
CombOS - Combinatorial Object Server, Generate numerical semigroups
Manuel Delgado, Shalom Eliahou, and Jean Fromentin, A verification of Wilf's conjecture up to genus 100, arXiv:2310.07742, 2023.
Shalom Eliahou and Jean Fromentin, Semigroupes Numériques et Nombre d’or, Images des Mathématiques, CNRS, 2018. In French.
Sergi Elizalde, Improved bounds on the number of numerical semigroups of a given genus, arXiv:0905.0489 [math.CO], 2009. [Maria Bras-Amorós, Sep 01 2009]
G. Failla, C. Peterson, and R. Utano, Algorithms and basic asymptotics for generalized numerical semigroups in N^d, Semigroup Forum, Jan 31 2015, DOI 10.1007/s00233-015-9690-8.
Gilberto B. Almeida Filho and Matheus Bernardini, Gapsets and the k-generalized Fibonacci sequences, arXiv:2208.07692 [math.CO], 2022.
Steven R. Finch, Monoids of natural numbers [broken link]
Steven R. Finch, Monoids of natural numbers, March 17, 2009. [Cached copy, with permission of the author]
Jean Fromentin, Exploring the tree of numerical semigroups, arXiv:1305.3831 [math.CO], 2013-2015. See also, hal-00823339.
Jean Fromentin and Shalom Eliahou, Semigroupes numériques et nombre d’or (II), (in French), Images des Mathématiques, CNRS, 2018.
Jean Fromentin and Florent Hivert, Exploring the tree of numerical semigroups, Math. Comp. 85 (2016), 2553-2568.
Florent Hivert, High Performance Computing Experiments in Enumerative and Algebraic Combinatorics, PASCO 2017 Proceedings of the International Workshop on Parallel Symbolic Computation, Article No. 2.
Trevor Hyde, Math Overflow post on reference for result mentioned in Zagier's email.
S. Kakeya, On fundamental systems of symmetric functions, Jap. J. Math., 2, (1925), 69-80.
S. Kakeya, On fundamental systems of symmetric functions II, Jap. J. Math., 4, (1927), 77-85.
Nathan Kaplan, Counting Numerical Semigroups, arXiv:1707.02551 [math.CO], 2017. Also Amer. Math. Monthly, 124 (2017), 862-875.
Jiryo Komeda, Non-Weierstrass numerical semigroups. Semigroup Forum 57 (1998), no. 2, 157-185. [Maria Bras-Amorós, Sep 01 2009]
Nivaldo Medeiros, Numerical Semigroups
Alex Zhai, Fibonacci-like growth of numerical semigroups of a given genus, Semigroup Forum, 86 (2013), 634-662. See also, arXiv:1111.3142 [math.CO], 2011.
Y. Zhao, Constructing numerical semigroups of a given genus, Semigroup Forum 80 (2010) 242-254.
Daniel G. Zhu, Sub-Fibonacci behavior in numerical semigroup enumeration, Comb. Theory 3(2) (2023), #10. arXiv:2202.05755 [math.CO], 2022-2023.
Index entries for sequences related to semigroups

Row sums of A199711.

Conjectures: A) a(n) >= a(n-1)+a(n-2); B) a(n)/(a(n-1)+a(n-2)) approaches 1; C) a(n)/a(n-1) approaches the golden ratio; D) a(n) >= a(n-1). Conjectures A, B, C, D were presented by M. Bras-Amorós in the seminar Algebraic Geometry, Coding and Computing, in Segovia, Spain, in 2007, and at IMNS 2018 in Granada, Spain, in 2008. Conjectures A, B, C were then published in the Semigroup Forum, 76 (2008), 379-384. Conjectures B and C are proved in the paper by Zhai, 2011. - Maria Bras-Amorós, Oct 24 2007, corrected Aug 31 2009

The terms a(17)-a(52) were contributed (in the context of semigroups) by Maria Bras-Amorós, Oct 24 2007. The computations were done with the help of Jordi Funollet and Josep M. Mondelo.
Terms a(53)-a(60) were taken from the Fromentin (2013) paper. - N. J. A. Sloane, Sep 05 2013
Terms a(61)-a(70) were taken from https://github.com/hivert/NumericMonoid.
Terms a(71)-a(72) were computed by J. Fernández-González and Maria Bras-Amorós.
Terms a(73)-a(75) were taken from the Delgado et al. (2023) paper. - Daniel Zhu, Feb 16 2024
Terms a(76)-a(77) were taken from Maria Bras-Amorós 2025 paper. - Maria Bras-Amorós, Mar 20 2025

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

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.

A164047 The number of symmetric numerical sets with odd Frobenius number and no small atoms.

Original entry on oeis.org

1, 1, 2, 3, 6, 10, 20, 37, 73, 139, 275, 533, 1059, 2075, 4126, 8134, 16194, 32058, 63910, 126932, 253252, 503933, 1006056, 2004838, 4004124, 7987149, 15957964, 31854676, 63660327, 127141415, 254136782, 507750109, 1015059238, 2028564292, 4055812657, 8107052520

Offset: 1

Jeremy L. Marzuola (marzuola(AT)math.uni-bonn.de), Aug 08 2009

nonn

Definition using terminology of [MM]: Asigma(k)' is the number of symmetric numerical sets S with Frobenius number 2k-1. This is denoted A^\sigma_{2k-1}^\prime in [MM]. Asigma(k)' equals the number of sigma-admissible subsets L of {1,2,...,2k-2} such that if x is an element of M then 2k-1-x is not an element of M. It also equals the number of vertices at height k in the rooted tree shown in figure 5 of [MM]. For large k, Asigma(k)' is approximately equal to .23065 x 2^(k-1) [MM]. The number of symmetric numerical sets with Frobenius number 2k and no small atoms equals Asigma(k)' by theorem 19 of [MM].

Martin Fuller, Table of n, a(n) for n = 1..66
J. Marzuola and A. Miller, Counting Numerical Sets with No Small Atoms, arXiv:0805.3493 [math.CO], 2008.
J. Marzuola and A. Miller, Counting numerical sets with no small atoms, J. Combin. Theory A 117 (6) (2010) 650-667.

Asigma(k)' is the same as the number of additive 2-bases for k-1 as described in A008929 and A066062. Related to Asigma(k) in A158449.

program good
! This program calculates the cardinality of the number of symmetric numerical monoids without a small atom (or symmetric "good sets") for Frobenius number, $g$, as represented by $A_g^\sigma'$ defined in "Counting numerical sets with no small atoms" ([MM]) by Jeremy L. Marzuola and Andy Miller (to appear in Journal of Combinatorial Theory: A).
! Here we set the parameters of computation. We represent a numerical set by binary representations of the elements below the Frobenius number. Namely, a $0$ means an element is not in a set and a $1$ means an element is in the set. The symmetric numerical sets will be stored in an array called $Gin$, which will be redefined for each $g$ for the purposes of iterating the algorithm. Each row of Gin corresponds to a numerical set, e.g. the row $Gin(3,-)=(1,1,0,1,0,0)$ would determine the numerical set ${1,2,4} \cup N_5$. This is a slight variation of the notation presented in Figure 5 of [MM], where only the initial half segment is presented since the remainder is clear by symmetry.
!The dimension here is limited only by the memory of the author's computers. With greater computational ability, you would be able to larger values of $g$.
!Generically we need only take the dimension of $z$ to be $Mit+3$.
      INTEGER*1, DIMENSION(21290000,50) :: G1, Gin
      INTEGER, DIMENSION(40) :: z
      INTEGER j, Mit, N1, N2, k, n, flag1
!Initialize z to be zero in every component.
      do j = 1,40 z(j) = 0 enddo
! $Mit$ is the number of times we iterate our algorithm. Since we begin with $g=3$, the resulting output will print out $A_g^\sigma'$ as $g$ ranges from $1$ to $Mit+3$. At each stage of the iteration, we have $g=j+3$.
      Mit = 24
! We begin with the symmetric good sets for $g=3$ given by only $(1,0)$. We need these sets in order to run the algorithm suggested in the paper from the rooted tree in Figure 5 of [MM]. After each iteration of the code, $Gin$ will be redefined as the collection of symmetric good sets for $g = n+2$. If one wants to see the symmetric "good" sets for a specific $g$, one must print $Gin$ after the iteration leading to that $g$.
      Gin(1,1) = 1
      Gin(1,2) = 0
! We determine the number, $z(g)$, of symmetric good sets for $g = 1,2,3$ for the implementation of the algorithm. In the notation of [MM], $z(g) = A_g^\sigma'$.
      z(1) = 1
      z(2) = 1
      z(3) = 1
! $N1$ will represent the number of symmetric good sets $A_g^\sigma'$ for Frobenius number $g$ and $N2$ is the size of the numerical sets themselves for the given $g$. Here we begin with $g = 3$, so $N1 = A_3^\sigma' = 1$. For $g=n$, we have $N2 = |{1,...,n-1}|=n-1$.
      N1 = 1
      N2 = 2
! Here we implement the algorithm by building the good sets for $g=2n+1$ based on those that exist for $g=2n-1$.
      do j = 1,Mit
        flag1 = 0
! If $g=2n$, we know from Theorem 19 of the paper that $z(2n)=z(2n-1)$.
        if (mod(j,2) == 1) then
          z(j+3) = z(j+2)
        endif
! If $g=2n+1$, we implement the algorithm discussed in [MM]. Mainly, we need to count $A_g^\sigma'$. See Figure 5 for a pictoral reference to this algorithm.
        if (mod(j,2) == 0) then
          do k = 1,N1
! Let $G$ be a symmetric good set for $g=2n-1$. If $G$ is bivalent, we can build good sets of size of size $2n+1$ by adding $01$, $10$ to the middle of the set as described in Figure 5 of [MM].
            if (maxval(Gin(k,1:N2/2)-Gin(k,N2/2+1:N2)) > 0) then
              do n = 1,N2/2
                G1(flag1+1,n) = Gin(k,n)
                G1(flag1+2,n) = Gin(k,n)
                G1(flag1+1,N2/2+n+2) = Gin(k,N2/2+n)
                G1(flag1+2,N2/2+n+2) = Gin(k,N2/2+n)
              enddo
              G1(flag1+1,N2/2+1) = 1
              G1(flag1+2,N2/2+1) = 0
              G1(flag1+1,N2/2+2) = 0
              G1(flag1+2,N2/2+2) = 1
              flag1 = flag1+2
!erroneous? endif
            else
              do n = 1,N2/2
! If $G$ is not bivalent, we can build further good sets for $g=2n+1$ by adding $10$ to the middle of the set as described in Figure 5 of [MM].
                G1(flag1+1,n) = Gin(k,n)
                G1(flag1+1,N2/2+n+2) = Gin(k,N2/2+n)
              enddo
              G1(flag1+1,N2/2+1) = 1
              G1(flag1+1,N2/2+2) = 0
              flag1 = flag1+1
            endif
          enddo
          N1 = flag1
          N2 = 2+j
! Here we record the good sets, $Gin$, for the larger Frobenius number in order to move to the next stage of our algorithm.
          Gin(1:flag1,1:N2) = G1(1:flag1,1:N2)
! Here we record the number of good sets for $g=j+3$.
          z(j+3) = flag1
        endif
      enddo
! Here we print the total number of good symmetric numerical sets as output of the code for each of our computed Frobenius numbers.
      write(*,*) z
      end program
! Edited by M. F. Hasler, Jan 31 2020

This theorem also provides a recursive connection with Asigma(k) from A158449: Asigma(2k+1)' = 2*Asigma(2k)' - Asigma(k).

a(33) onwards from Martin Fuller, Sep 13 2023

Previous Showing 11-20 of 28 results. Next

cp's OEIS Frontend

A365045 Number of subsets of {1..n} containing n such that no element can be written as a positive linear combination of the others.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A365920 Greatest non-subset-sum of the prime indices of n, or 0 if there is none.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A365044 Number of subsets of {1..n} whose greatest element cannot be written as a (strictly) positive linear combination of the others.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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

A007323 Number of numerical semigroups of genus n; conjecturally also the number of power sum bases for symmetric functions in n variables.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions