×

Bounds on the number of numerical semigroups of a given genus. (English) Zbl 1169.05300

Summary: Lower and upper bounds are given for the number \(n_g\) of numerical semigroups of genus \(g\). The lower bound is the first known lower bound while the upper bound significantly improves the only known bound given by the Catalan numbers. In a previous work the sequence \(n_g\) is conjectured to behave asymptotically as the Fibonacci numbers. The lower bound proved in this work is related to the Fibonacci numbers and so the result seems to be in the direction to prove the conjecture. The method used is based on an accurate analysis of the tree of numerical semigroups and of the number of descendants of the descendants of each node depending on the number of descendants of the node itself.

MSC:

05A15 Exact enumeration problems, generating functions
05A16 Asymptotic enumeration
20M14 Commutative semigroups
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Backelin, Jörgen, On the number of semigroups of natural numbers, Math. Scand., 66, 2, 197-215 (1990) · Zbl 0741.11006
[2] Fröberg, Ralf; Gottlieb, Christian; Häggkvist, Roland, On numerical semigroups, Semigroup Forum, 35, 1, 63-83 (1987) · Zbl 0614.10046
[3] Carlos Rosales, José; García-Sánchez, Pedro A.; Ignacio García-García, Juan; Jiménez Madrid, José A., Fundamental gaps in numerical semigroups, J. Pure Appl. Algebra, 189, 1-3, 301-313 (2004) · Zbl 1070.20072
[4] Bras-Amorós, Maria, Fibonacci-like behavior of the number of numerical semigroups of a given genus, Semigroup Forum, 76, 2, 379-384 (2008) · Zbl 1142.20039
[5] Bras-Amorós, Maria; de Mier, Anna, Representation of numerical semigroups by Dyck paths, Semigroup Forum, 75, 3, 677-682 (2007) · Zbl 1128.20046
[6] Elena Barcucci, Alberto Del Lungo, Elisa Pergola, Renzo Pinzani, A methodology for plane tree enumeration, in: Proc. of the 7th Conference on Formal Power Series and Algebraic Combinatorics (Noisy-le-Grand, 1995), vol. 180, 1998, pp. 45-64; Elena Barcucci, Alberto Del Lungo, Elisa Pergola, Renzo Pinzani, A methodology for plane tree enumeration, in: Proc. of the 7th Conference on Formal Power Series and Algebraic Combinatorics (Noisy-le-Grand, 1995), vol. 180, 1998, pp. 45-64 · Zbl 0904.05004
[7] Barcucci, Elena; Del Lungo, Alberto; Pergola, Elisa; Pinzani, Renzo, ECO: A methodology for the enumeration of combinatorial objects, J. Difference Equ. Appl., 5, 4-5, 435-490 (1999) · Zbl 0944.05005
[8] Banderier, Cyril; Bousquet-Mélou, Mireille; Denise, Alain; Flajolet, Philippe; Gardy, Danièle; Gouyou-Beauchamps, Dominique, Generating functions for generating trees, Discrete Math., 246, 1-3, 29-55 (2002), Formal power series and algebraic combinatorics (Barcelona, 1999) · Zbl 0997.05007
[9] Carlos Rosales, José, Families of numerical semigroups closed under finite intersections and for the Frobenius number, Houston J. Math, 34, 339-348 (2008) · Zbl 1198.20051
[10] Carlos Rosales, José; García-Sánchez, Pedro A.; Ignacio García-García, Juan; Jiménez Madrid, José A., The oversemigroups of a numerical semigroup, Semigroup Forum, 67, 1, 145-158 (2003) · Zbl 1043.20034
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.