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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A007323 Number of bases for symmetric functions of n variables - see Comments lines for precise definition.
(Formerly M1064)
4
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, 178158289 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

Also the number of numerical semigroups of "genus" n.

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

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.

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]

Occurs in Blanco, Justo Puerto, p.6, with a(0) = 1 prepended, as Table 1: "Number of numerical semigroups with given gender" where by "gender" they may mean "Genus." [Jonathan Vos Post, Jan 11 2009]

REFERENCES

M. Bras-Amoros, Fibonacci-Like Behavior of the Number of Numerical Semigroups of a Given Genus, Semigroup Forum, 76 (2008), 379-384.

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.

G. Failla, C. Peterson, 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

Jiryo Komeda, Non-Weierstrass numerical semigroups. Semigroup Forum 57 (1998), no. 2, 157-185. [From Maria Bras-Amoros, Sep 01 2009]

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

LINKS

Maria Bras-Amoros and J. Fromentin, Table of n, a(n) for n = 1..60

Maria Bras-Amoros, Home Page [Has many of these references]

M. Bras-Amoros, 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.

M. Bras-Amoros and A. de Mier, Representation of Numerical Semigroups by Dyck Paths, arXiv:math/0612634, Semigroup Forum 75 (2007) 676-681.

M. Bras-Amoros and S. Bulygin, Towards a Better Understanding of the Semigroup Tree, arXiv:0810.1619, Semigroup Forum 79 (2009) 561-574.

Victor Blanco, Justo Puerto, Computing the number of numerical semigroups using generating functions, Jan 9, 2009. [From Jonathan Vos Post, Jan 11 2009]

Sergi Elizalde, Improved bounds on the number of numerical semigroups of a given genus, arXiv:0905.0489 [From Maria Bras-Amoros, Sep 01 2009]

S. R. Finch, Monoids of natural numbers

Jean Fromentin, Exploring the tree of numerical semigroups, arXiv:1305.3831 [math.CO] Also http://hal.archives-ouvertes.fr/docs/00/82/33/39/PDF/article.pdf.

Nivaldo Medeiros, Numerical Semigroups

Alex Zhai, Fibonacci-like growth of numerical semigroups of a given genus, arXiv:1111.3142, 2011

Index entries for sequences related to semigroups

FORMULA

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

EXAMPLE

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}

CROSSREFS

Sequence in context: A135360 A082548 A270995 * A099604 A026790 A054165

Adjacent sequences:  A007320 A007321 A007322 * A007324 A007325 A007326

KEYWORD

nonn,nice

AUTHOR

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

EXTENSIONS

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.

Terms a(53)-a(60) are taken from the Fromentin (2013) paper. - N. J. A. Sloane, Sep 05 2013

Entry revised by N. J. A. Sloane, Aug 31 2009, Sep 02 2009, Feb 07 2012

STATUS

approved

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 March 24 21:42 EDT 2017. Contains 283996 sequences.