login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A007323 Number of bases for symmetric functions of n variables; also the number of numerical semigroups of "genus" n.
(Formerly M1064)
6

%I M1064

%S 1,1,2,4,7,12,23,39,67,118,204,343,592,1001,1693,2857,4806,8045,13467,

%T 22464,37396,62194,103246,170963,282828,467224,770832,1270267,2091030,

%U 3437839,5646773,9266788,15195070,24896206,40761087,66687201,109032500,178158289

%N Number of bases for symmetric functions of n variables; also the number of numerical semigroups of "genus" n.

%C From Don Zagier's email of Apr 11 1994: (Start)

%C 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.

%C 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} (0<j_1<...<j_n) also works.

%C For 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.

%C 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.

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

%C 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)

%C 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]

%C Occurs in Blanco, Justo Puerto, p. 6, Table 1: "Number of numerical semigroups with given gender" where by "gender" they may mean "Genus." [_Jonathan Vos Post_, Jan 11 2009]

%D 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.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Maria Bras-Amoros and J. Fromentin, <a href="/A007323/b007323.txt">Table of n, a(n) for n = 1..60</a>

%H Matheus Bernardini, and Fernando Torres, <a href="https://arxiv.org/abs/1612.01212">Counting numerical semigroups by genus and even gaps</a>, Discrete Mathematics 340.12 (2017): 2853-2863. Also arXiv:1612.01212 [math.CO], 2016-2017.

%H Victor Blanco, Justo Puerto, <a href="http://arxiv.org/abs/0901.1228">Computing the number of numerical semigroups using generating functions</a>, arXiv:0901.1228 [math.CO], 2009.

%H Maria Bras-Amoros, <a href="http://crises-deim.urv.cat/~mbras/">Home Page</a> [Has many of these references]

%H M. Bras-Amoros, <a href="http://dx.doi.org/10.1007/s00233-007-9014-8">Fibonacci-Like Behavior of the Number of Numerical Semigroups of a Given Genus</a>, Semigroup Forum, 76 (2008), 379-384. See <a href="https://arxiv.org/abs/1706.05230">also</a>, arXiv:1706.05230 [math.NT], 2017.

%H M. Bras-Amoros, <a href="http://dx.doi.org/10.1016/j.jpaa.2008.11.012">Bounds on the Number of Numerical Semigroups of a Given Genus</a>, Journal of Pure and Applied Algebra, vol. 213, n. 6 (2009), pp. 997-1001. arXiv:0802.2175.

%H M. Bras-Amoros and S. Bulygin, <a href="http://arxiv.org/abs/0810.1619">Towards a Better Understanding of the Semigroup Tree</a>, arXiv:0810.1619 [math.CO], 2008; <a href="http://dx.doi.org/10.1007/s00233-009-9175-8">Semigroup Forum 79 (2009) 561-574</a>.

%H M. Bras-Amoros and A. de Mier, <a href="http://arxiv.org/abs/math/0612634">Representation of Numerical Semigroups by Dyck Paths</a>, arXiv:math/0612634 [math.CO], 2006; <a href="http://dx.doi.org/10.1007/s00233-007-0717-7">Semigroup Forum 75 (2007) 676-681</a>.

%H Maria Bras-Amorós, J Fernández-González, <a href="https://arxiv.org/abs/1607.01545">Computation of numerical semigroups by means of seeds</a>, arXiv preprint arXiv:1607.01545 [math.CO], 2016.

%H Sergi Elizalde, <a href="http://arxiv.org/abs/0905.0489">Improved bounds on the number of numerical semigroups of a given genus</a>, arXiv:0905.0489 [math.CO], 2009. [Maria Bras-Amoros, Sep 01 2009]

%H G. Failla, C. Peterson, R. Utano, <a href="http://dx.doi.org/10.1007/s00233-015-9690-8">Algorithms and basic asymptotics for generalized numerical semigroups in N^d</a>, Semigroup Forum, Jan 31 2015, DOI 10.1007/s00233-015-9690-8.

%H S. R. Finch, <a href="http://www.people.fas.harvard.edu/~sfinch/">Monoids of natural numbers</a>

%H Jean Fromentin, <a href="http://arxiv.org/abs/1305.3831">Exploring the tree of numerical semigroups</a>, arXiv:1305.3831 [math.CO], 2013-2015. See <a href="https://hal.archives-ouvertes.fr/hal-00823339">also</a>, hal-00823339.

%H Nathan Kaplan, <a href="https://arxiv.org/abs/1707.02551">Counting Numerical Semigroups</a>, arXiv:1707.02551 [math.CO], 2017. Also Amer. Math. Monthly, 124 (2017), 862-875.

%H Jiryo Komeda, <a href="http://dx.doi.org/10.1007/PL00005972">Non-Weierstrass numerical semigroups</a>. Semigroup Forum 57 (1998), no. 2, 157-185. [Maria Bras-Amoros, Sep 01 2009]

%H Nivaldo Medeiros, <a href="http://www.impa.br/~nivaldo/algebra/semigroups/index.html">Numerical Semigroups</a>

%H Alex Zhai, <a href="http://arxiv.org/abs/1111.3142">Fibonacci-like growth of numerical semigroups of a given genus</a>, arXiv:1111.3142 [math.CO], 2011.

%H <a href="/index/Se#semigroups">Index entries for sequences related to semigroups</a>

%F 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. Conjectures B and C have been proved by Zhai (2011). - Maria Bras-Amoros (maria.bras(AT)gmail.com), Oct 24 2007, corrected Aug 31 2009

%e G.f. = x + 2*x^2 + 4*x^3 + 7*x^4 + 12*x^5 + 23*x^6 + 39*x^7 + 67*x^8 + ...

%e a(1)=1 because the unique numerical semigroup with genus 1 is N \ {1}

%Y Row sums of A199711. [corrected by _Jonathan Sondow_, Nov 05 2017]

%K nonn,nice

%O 0,3

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

%E The terms from a(17) to a(52) were contributed (in the context of semigroups) by Maria Bras-Amoros (maria.bras(AT)gmail.com), Oct 24 2007. The computations were done with the help of Jordi Funollet and Josep M. Mondelo.

%E Terms a(53)-a(60) are taken from the Fromentin (2013) paper. - _N. J. A. Sloane_, Sep 05 2013

%E Entry revised by _N. J. A. Sloane_, Aug 31 2009, Sep 02 2009, Feb 07 2012

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified December 13 09:05 EST 2017. Contains 295957 sequences.