This site is supported by donations to The OEIS Foundation.



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

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

%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 = 0..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>, arXiv:1612.01212 [math.CO], 2016-2017.

%H Matheus Bernardini, and Fernando Torres, <a href="https://doi.org/10.1016/j.disc.2017.08.001">Counting numerical semigroups by genus and even gaps</a>, Discrete Mathematics 340.12 (2017): 2853-2863.

%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 Shalom Eliahou, Jean Fromentin, <a href="http://images.math.cnrs.fr/Semigroupes-numeriques-et-nombre-d-or-I.html">Semigroupes Numériques et Nombre d’or</a>, Images des Mathématiques, CNRS, 2018. In French.

%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 Jean Fromentin, Shalom Eliahou, <a href="http://images.math.cnrs.fr/Semigroupes-numeriques-et-nombre-d-or-II.html">Semigroupes numériques et nombre d’or (II)</a>, (in French), Images des Mathématiques, CNRS, 2018.

%H Florent Hivert, <a href="https://dx.doi.org/10.1145/3115936.3115938">High Performance Computing Experiments in Enumerative and Algebraic Combinatorics</a>, PASCO 2017 Proceedings of the International Workshop on Parallel Symbolic Computation, Article No. 2.

%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 Y. Zhao, <a href="http://dx.doi.org/10.1007/s00233-009-9190-9">Constructing numerical semigroups of a given genus</a>, Semigroup Forum 80 (2010) 242-254

%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,changed

%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 June 22 09:22 EDT 2018. Contains 305669 sequences. (Running on oeis4.)