/^creative ^commor
ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 15 (2018) 323-336
https://doi.org/10.26493/1855-3974.989.d15
(Also available at http://amc-journal.eu)
A combinatorial problem and numerical semigroups*
Aureliano M. Robles Perez
Departamento de Matemática Aplicada, Universidad de Granada, 18071-Granada, Spain
Jose Carlos Rosales
Departamento de Algebra, Universidad de Granada, 18071-Granada, Spain
Received 3 December 2015, accepted 2 March 2018, published online 25 June 2018 Abstract
Let a = (ai,... ,an) and b = (bi,... ,bn) be two n-tuples of positive integers, let X be a set of positive integers, and let g be a positive integer. In this work we show an algorithmic process in order to compute all the sets C of positive integers that fulfill the following conditions:
1.	The cardinality of C is equal to g;
2.	If x,y e N \ {0} and x + y e C, then C n {x, y} = 0;
3.	If x e C and ^ e N \ {0} for some i e {1,..., n}, then ^ e C;
4.	X n C = 0.
Keywords: Combinatorial problems, numerical semigroups, Frobenius varieties, Frobenius pseudo-varieties.
Math. Subj. Class.: 11B75, 05A99, 20M14
*Both authors are supported by the project MTM2014-55367-P, which is funded by Ministerio de Economía y Competitividad and Fondo Europeo de Desarrollo Regional FEDER, and by the Junta de Andalucía Grant Number FQM-343. The second author is also partially supported by Junta de Andalucía/Feder Grant Number FQM-5849. The authors would like to thank the referee for several comments and suggestions that led to the improvement of this paper.
E-mail ¡addresses: arobles@ugr.es (Aureliano M. Robles Perez), jrosales@ugr.es (Jose Carlos Rosales)
©® This work is licensed under https://creativecommons.org/licenses/by/3.0/
324
Ars Math. Contemp. 15 (2018) 441-466
1 Introduction
Let Z and N be the sets of integers and non-negative integers, respectively. Let us suppose that we want to compute a set C c N of six elements such that the following conditions are fulfilled.
(C1) If x, y are positive integers such that x + y G C, then C n {x, y} = 0. (C2) If x G C and x - 4 is a positive integer, then x - 4 G C. (C3) If x G C and X-1 is a positive integer, then X-1 G C. (C4) 5 G C.
The purpose of this work will be to give an answer to this type of combinatorial problems.
Let a = (ai,..., an) and b = (6i,...,bn) be two n-tuples (with n > 1) of positive integers, let X be a non-empty subset of N \ {0}, and let g be a positive integer. Let us denote by P(a, b, X, g) the problem of computing all the subsets C of N \ {0} that fulfill the following conditions.
(P1) The cardinality of C is equal to g.
(P2) If x, y G N \ {0} and x + y G C, then C n {x, y} = 0.
(P3) If x G C and ^ G N \ {0} for some i G {1,..., n}, then ^ G C.
(P4) X n C = 0.
With the previous notation, we observe that the problem proposed at the beginning is just P((1, 2), (4,1), {5}, 6).
A numerical semigroup (see [6]) is a submonoid S of (N, +) such that N \ S is finite. The cardinality of N \ S is the so-called genus of S and is denoted by g(S).
It is easy to see that C is a solution of P(a, b, X, g) if and only if S = N \ C is a numerical semigroup that fulfills the following conditions.
(51)	g(S) = g.
(52)	If s G S \ {0}, then as + b G Sn (where as + b = (ais + bi,..., ans + bn)).
(53)	X C S.
Let us denote by N(a, b, X) the set
{S | S is a numerical semigroup, X C S, and as + b G Sn for all s G S \ {0} }. With this notation, the solutions of P(a, b, X, g) are the elements of the set
{N \ S | S G N(a, b, X) and g(S) = g}.
Let S be a numerical semigroup. The Frobenius number of S (see [2]), denoted by F(S), is the maximum integer that does not belong to S.
A Frobenius variety (see [5]) is a non-empty family of numerical semigroups V that fulfills the following conditions.
A. M. Robles Pérez and J. C. Rosales: A combinatorial problem and numerical semigroups 325
(V1) If S, T e V, then S n T e V.
(V2) If S e V and S = N, then S U {F(S)} e V.
Before to show the structure of this paper, let us see some remarks in order to delimit the problem P(a, b, X, g) inside the theory of numerical semigroups.
Remark 1.1. If we only impose condition (C1) (equivalently, condition (P2)), then we are considering the family S of all numerical semigroups that, obviously, is a Frobenius variety. Moreover, in [6] it is shown how to arrange the elements of S in a tree with root N.
Remark 1.2. Keeping in mind only conditions (C1) and (C4) (equivalently, conditions (P2) and (P4) or condition (S3)), we have the family S(X) of all numerical semigroups containing X. Once again, it is not difficult to check that S(X) is a Frobenius variety. In addition, following the ideas of this paper, it will be clear how we can arrange the elements of S(X) in a tree with root N.
Remark 1.3. Now let us consider only conditions (C1), (C2) and (C3) (equivalently, conditions (P2) and (P3) or condition (S2)). In this case we get families of numerical semigroups satisfying a set non-homogeneous patterns (see [1]). This case is related to the results of [1], where the concept of m-variety makes possible to arrange the elements of certain families in trees with root Sm = {0, m, = {0} U {n e N | n > m}. Precisely, m-varieties are examples of Frobenius pseudo-varieties (see [4]).
In Section 2 we will see that N(a, b, X) is a Frobenius variety. In addition, we will show that such a variety is finite if and only if gcd(X U {bi,..., bn}) = 1 (where, as usual, gcd(A) is the greatest common divisor of the elements in A).
Let us denote by M(a, b, X) the intersection of all the elements in N(a, b, X). Observe that M(a, b, X) is always a submonoid of (N, +). In addition, we will prove that M(a, b, X) is a numerical semigroup if and only if N(a, b, X) has finitely many elements.
In Section 2 we will show that P(a, b, X, g) has a solution if and only if the cardinality of N \ M(a, b, X) is greater than or equal to g. Moreover, we will give an algorithm in order to compute M(a, b, X). Therefore, we will have an algorithmic process to decide whether P(a, b, X, g) has a solution.
In Section 3, with the help of some results from [5], we will arrange the elements of N(a, b, X) in a tree with root N. Moreover, we will characterize the children of a vertex in such a tree and, consequently, will have a recursive procedure in order to build N(a, b, X). Accordingly, we will have an algorithmic process to compute all the elements of N(a, b, X) with a fixed genus and, in particular, an algorithm to compute all the solutions of P(a, b, X, g).
Finally, using the concept of Frobenius pseudo-variety, we will state and solve a generalization of P(a, b, X, g) in Section 4.
2 (a, b)-monoids
In this work, unless stated otherwise, a = (a1,..., an) and b = (b1,..., bn) denote two n-tuples of positive integers. If X C N, then N(a, b, X) is the set
{S | S is a numerical semigroup, X C S, and as + b e Sn for all s e S \ {0} },
with as + b = (ais + bi,. .., ans + bn).
326
Ars Math. Contemp. 15 (2018) 441-466
Proposition 2.1. N(a, b, X) is a Frobenius variety.
Proof. It is clear that N G N(a, b, X) and, therefore, N(a, b, X) = 0. It is also clear that, if S,T G N(a, b, X), then S n T G N(a,b,X). Now, let S G N(a,b,X) such that S = N. In order to show that S U {F(s)} G N(a, b, X), it is enough to see that
aF(S) + b G (S U {F(S)})n. Observe that, if i G {1,..., n}, then a,F(S) + b > F(S) and, therefore, a,F(S) + b, G SU{F(S)}. Consequently, aF(S) + b G (Su{f(S)})". □
We will say that M is an (a, b)-monoid if M is a submonoid of (N, +) fulfilling that
am + b G Mn for all m G M \ {0}.
Proposition 2.2. Let X be a non-empty subset of N. Then M is an (a, b)-monoid that contains X if and only if there exists J C N (a, b, X) such that M = p| Se j S.
Proof. The sufficient condition is trivial. For the necessary one, let Mk = M U {k,
for all k G N (nhere {k, = {n G N | n > k}). Then it is clear that Mk G N(a, b, X) and that M = f|fceN Mk.	□
Let us observe that, if we denote by M(a, b, X) = p|s£n(a b X) S, then M(a, b, X) is the smallest (a, b)-monoid containing X.
Theorem 2.3. Let X be a non-empty subset of N \ {0} and let g be a positive integer. Then the problem P(a, b, X, g) has a solution if and only if the cardinality of N \ M (a, b, X) is greater than or equal to g.
Proof. (Necessity.) If C is a solution of P(a, b, X, g) and we take S = N \ C, then S G N(a, b, X) and g(S) = g. Since M(a, b, X) C S, we have that N \ S C N \ M(a, b, X) and, thereby, the cardinality of N \ M(a, b, X) is greater than or equal to g.
(Sufficiency.) Let us suppose that N \ M(a, b, X) = {ci < • • • < cg < • • • }. If we take S = M(a, b, X) U {cg + 1, then it is clear that S G N(a, b, X) and g(S) = g. Therefore, C = N \ S is a solution of P(a, b, X, g).	□
Let us observe that, if P(a, b, X, g) has a solution and, in addition, we have computed M(a, b, X), then the proof of the sufficient condition in the previous theorem gives us a method to compute a solution of P(a, b, X, g).
If X is a non-empty subset of N, then we denote by (X} the submomoid of (N, +) generated by X, that is,
(X} = {Aixi +-----+ Afcxfc | k G N \ {0}, xi,..., xk G X, and Ai,..., Afc G N}.
If M = (X}, then we will say that M is generated by X or, equivalently, that X is a system of generators of M. The next result is well known (see, for instance, [6]).
Lemma 2.4. If X C N, then (X} is a numerical semigroup if and only if gcd(X) = 1.
We know that M(a, b, X) is a submonoid of (N, +). From the following proposition we will get that, if X C N \ {0}, then M(a, b, X) is a numerical semigroup if and only if
gcd(X U {b i,..., bn }) = 1.
Proposition 2.5. If X C N \ {0}, then gcd(M(a, b, X)) = gcd(X U {bi,..., bn}).
A. M. Robles Pérez and J. C. Rosales: A combinatorial problem and numerical semigroups 327
Proof. Let d = gcd(M(a, b, X)) and d' = gcd(X U {61,..., bn}). In order to prove the proposition, we will show that d' | d and d | d'. (As usual, if p, q are positive integers, then p | q means that p divides q.)
First of all, it is clear that ({d'}} is an (a, b)-monoid containing X. Thus, M(a, 6, X) C ({d'}} and, consequently, d' | d.
Now, let us take x G X. Then {x, a1x + 61,..., anx + bn} C M(a, b, X) and gcd{x, a1x + 61,..., anx + bn} = gcd{x, 61,..., bn}. Therefore, we have that X U (UUtex + bi | x G X}) C M(a, b, X) and gcd (X U (UIUKx + 6< | x G X})) = gcd(X U {b1,..., bn}) = d'. Accordingly, d | d'.	□
In the next result we show when the Frobenius variety N(a, b, X) is finite.
Theorem 2.6. Lei X be a subset of N \ {0}. Then the following conditions are equivalent.
1.	N (a, b, X) is finite.
2.	M(a, b, X) is a numerical semigroup.
3.	gcd(X U{b1,...,b„}) = 1.
Proof. The equivalence between conditions 2 and 3 is a consequence of Lemma 2.4 and Proposition 2.5. Now, let us see the equivalence between conditions 1 and 2.
(1. ^ 2.) It is enough to observe that the finite intersection of numerical semigroups is another numerical semigroup.
(2. ^ 1.) If S G N(a, b, X), then M(a,b,X) C S. Thus, S = M(a,b,X) U Y with Y C N \ M(a, b, X). Since N \ M(a, b, X) is finite, we conclude that N(a, b, X) is finite.	□
Our next aim in this section will be to give an algorithm in order to compute M(a, b, X). For this is fundamental the following result.
Proposition 2.7. Let M be a submonoid of (N, +) generated by X C N \ {0}. Then M is an (a, b)-monoid if and only if ax + b G Mn for all x G X.
Proof. The necessary condition is trivial. For the sufficiency, let m G M \ {0}. Then there exist x1,..., xt G X such that m = x1 + • • • + xt. If t = 1, then m = x1 and am + b = ax1 + b G Mn. If t > 2, then
am + b = a(x1 + • • • + xt) + b = a(x1 + • • • + xt-1) + axt + b.
Since a(x1 + • • • + xt-1), axt + b G Mn, we finish the proof.	□
The above proposition will be useful in order to determine whether a submonoid M of (N, +) is or is not an (a, b)-monoid. Let us see an example.
Example 2.8. S = ({4, 5,11}} is an ((1, 2), (4,1))-monoid because (1,2)4 + (4,1) = (8,9) G S2, (1,2)5 + (4,1) = (9,11) G S2, and (1, 2)11 + (4,1) = (15,23) G S2. Nevertheless, T = ({5,7, 9}} is not an )(1, 2), (4,1))-monoid because (1,2)5 + (4,1) = (9,11) G T2 (observe that 11 G T).
328
Ars Math. Contemp. 15 (2018) 441-466
With the help of Proposition 2.7, it would be possible to give an algorithm in order to compute M(a, b, X). However, we are going to postpone such an algorithm because, as we will see now, we can focus on case in which gcd(X U {^,... ,bn}) = 1, and thus simplify the computations.
We say that an integer d divides an n-tupla of integers c = (c-1,... ,cn) if d | q for all
i e {1,..., n}. In such a case, we denote by d = (cd",..., Cf). If A C Z and k e Z, then kA = {ka | a e A}. Finally, if A C Z, d e Z, and d | a for all a e A, then A = {d I a € A}.
Lemma 2.9. Let M be an (a, b)-monoid such that M = {0}. If gcd(M) = d, then
1.	d divides b;
2.	if dd e N \ {0} and dd | d, then M is an (a, Jj) -monoid;
3.	if k e N \ {0}, then kM is an (a, kb)-monoid.
Proof. 1. If we take X = M \ {0}, and having in mind that M(a, b, X) is the smallest (a, b)-monoid containing X, then this item is a consequence of Proposition 2.5.
2.	It is clear that M is a submonoid of (N, +). In addition, if x e M \ {0}, then d'x e M \ {0} and, therefore, ad'x + b e Mn. Consequently, ax + jj e Mf = (M)n.
3.	It is clear that kM is a submonoid of (N, +). Now, arguing as in the previous item, if x e kM \ {0}, then f e M \ {0} and, therefore, af + b e Mn. Consequently, ax + kb e k ■ Mn = (kM)n.	□
The next result says us that, in order to compute M (a,b,X), (t is sufficient to ca}culate
d = gcd (X U{b1,...,bn}) and M (a, j, f). Observe that gcd (X U { ^,..., ^f)) = 1 and, therefore, M(a, j, is a numerical semigroup.
d'd/	& \ d I
_ 1 i c o r> i lm
d
Proposition 2.10. Let X be a subset of N \ {0}. If gcd(X U {b1,..., bn}) = d, then
b X • d7 d .
M(a, b, X) = d ■ M(a, d, .
Proof. From item 3 of Lemma 2.9, we have that d ■ M(a, d, X) is an (a, b)-monoid containing X. Therefore, M(a, b,X) C d ■ M(a, d, X).
On the other hand, from Proposition 2.5 and item 2 of Lemma 2.9, we deduce that
M(adb'X} is an (a, d)-monoid containing ^. Consequently, M (a, d, =X) C M(°db'X), that is, d- M(a, d, xX)c M(a,b,X).	□
We are now ready to show the announced algorithm. Algorithm 2.11.
INPUT: A non(-empty finite set of) positive integers X such that gcd (X U{bi,...,bn}) = 1.
Output: M(a,b,X).
(1)	A = 0 and G = X.
(2)	If G \ A = 0, then return (G) and stop the algorithm.
(3)	m = min(G \ A).
(4)	H = {ajm + bj | i e {1,..., n} and a4m + bj e (G^.
(5)	If H = 0, then go to (7).
(6)	G = G U H.
(7)	A = A U {m} and go to (2).
A. M. Robles Pérez and J. C. Rosales: A combinatorial problem and numerical semigroups 329
In order to justify the performance of this algorithm, let us observe that, if the algorithm stops, then it returns (G) such that ag + b e (G)n for all g e G. Therefore, by applying Proposition 2.7, we have that (G) is an (a, b)-monoid. In addition, by construction, it is clear that G must be a subset of every (a, b)-monoid which contains X. Thus, (G) is the smallest (a, b)-monoid containing X. Consequently, in order to justify the algorithm, it will be enough to see that the algorithm stops. In fact, when we arrive to step (7) at the first time, we have that gcd(G) = 1 and, thereby, (G) is a numerical semigroup. Therefore, N \ (G) is finite and we can go to the step (6) only in a finite number of times.
Let us illustrate the performance of Algorithm 2.11 with two examples. In the first one M(a, b, X) is a numerical semigroup.
Example 2.12. We are going to compute M = M((1, 2), (4,1), {5}).
•	A = 0 and G = {5}.
•	m = 5, H = {9,11}, G = {5,9,11}, and A = {5}.
•	m = 9, H = {13}, G = {5, 9,11,13}, and A = {5, 9}.
•	m = 11, H = 0, G = {5,9,11,13}, and A = {5,9,11}.
•	m = 13, H = {17}, G = {5, 9,11,13,17}, and A = {5, 9,11,13}.
•	m = 17, H = 0, G = {5,9,11,13,17}, and A = {5,9,11,13,17}.
Therefore, M = ({5,9,11,13,17}).
Going back to the problem P((1,2), (4,1), {5}, 6) of the introduction, we have that, since N \ M = {1,2, 3,4,6,7,8,12} has cardinality equal to 8, then Theorem 2.3 asserts that the proposed problem has a solution. Moreover, the solutions will be some subsets, with cardinality equal to 6, of {1,2,3,4, 6,7,8,12}. In addition, by the proof of the sufficiency of Theorem 2.3, we know that {1, 2, 3,4,6, 7} is a solution of such a problem.
Let us see now an example in which M(a, b, X) is not a numerical semigroup.
Example 2.13. Let us see that P((2, 3), (4,2), {6, 8}, 9) has a solution. For that, we begin with the computation of M((2,3), (4,2), {6,8}). By applying Paoposition 2.10, since
gcd({6,8,4, 2}) = 2, we get that M((2, 3), (4, 2), {6, 8}) =2 • M((2, 3), (2,1), {3,4}). Now, from Algorithm 2.11, M((2, 3), (2,1), {3,4}) = ({3,4}). Therefore,
M((2, 3), (4, 2), {6, 8}) = ({6, 8}) = {0, 6, 8,12,14,16,...}.
Since N\M((2, 3), (4,2), {6, 8}) has infinitely many elements, its cardinality is greater than or equal to 9 and, consequently, Theorem 2.3 assures that P((2,3), (4, 2), {6,8}, 9) has a solution. Moreover, by the proof of the sufficiency of Theorem 2.3, we have that
{1, 2,3,4,5, 7, 9,10,11} is a solution.
Remark 2.14. If we suppose, for a moment, that X = 0 (in a sense, we are removing condition (P4) in P(a, b, X, g) such as is observed in Remark 1.2), then it is obvious that Sk = {0, k, for all k e N, are numerical semigroups that belong to N(a, b, X) independently of the chosen n-tuples a, b. Thus M(a, b, X) = {0}, that is, the submonoid of (N, +) generated by X = 0.
Remark 2.15. Now, let us suppose that a, b are 0-tuples, that is, we remove condition (P3) in P(a, b, X, g) (see Remark 1.3). In this case, it is straightforward to show that M(a, b, X) is just the monoid generated by X.
330
Ars Math. Contemp. 15 (2018) 441-466
3 The tree associated to N(a, b, X)
A graph G is a pair (V, E), where
•	V is a non-empty set whose elements are called vertices of G,
•	E is a subset of {(v, w) G V x V | v = w} whose elements are called edges of G.
A path (of length n) connecting the vertices x and y of G is a sequence of different edges of the form (v0, vi), (vi, v2),..., (vn_i, vn) such that v0 = x and vn = y.
We say that a graph G is a tree if there exists a vertex r (known as the root of G) such that, for every other vertex x of G, there exists a unique path connecting x and r. If (x, y) is an edge of the tree, then we say that x is a child of y.
We define the graph G(N(a, b, X)) in the following way.
•	N(a, b, X) is the set of vertices of G(N(a, b, X));
•	(S,S') G N (a, b, X) xN (a, b, X) isanedgeof G(N(a,b,X)) if S' = S U{F(S)}.
By Proposition 2.1 and [5, Theorem 27], we have that G(N(a, b, X)) is a tree with root N. Our first purpose in this section will be to establish what are the children of a vertex in such a tree. For this we need to introduce some concepts.
Let S be a numerical semigroup and let G be a system of generators of S. We say that G is a minimal system of generators of S if S = (Y} for all Y C G. It is well known (see [6]) that every numerical semigroup admits a unique minimal system of generators and that, in addition, such a system is finite. Observe that, if we denote by msg(S) the minimal system of generators of S, then msg(S) = (S \ {0}) \ ((S \ {0}) + (S \ {0})). On the other hand, we have (see [6]) that, if S is a numerical semigroup and s G S, then S \ {s} is another numerical semigroup if and only if s G msg(S).
An immediate consequence of [5, Proposition 24, Theorem 27] is the next result.
Theorem 3.1. The graph G (N (a, b, X)) is a tree with root N. Moreover, the set of children of a vertex S G N (a, b, X) is
{S \ {m} | m G msg(S), m > F(S), and S \ {m} G N(a, b, X)}.
In the next result we will show the conditions that must satisfy m G msg(S) in order to have S \ {m} G N(a, b, X).
Proposition 3.2. Let S G N(a, b, X) and let m G msg(S). Then S \ {m} G N(a, b, X) if and only if G S \ {0} for all i G {1,... , n} and m G X.
Proof. (Necessity.) Since X C S \ {m}, we have that m G X. Let us suppose that there exists i G {1,..., n} such that G S \ {0}. Since = m, we have that G S \ {0, m} and that aj (m__bi) + a = m G S \ {m}. Therefore, S \ {m} G N(a, b, X).
(Sufficiency.) If S \ {m} G N(a, b, X), then there exists s G S \ {0, m} and there exists i G {1,..., n} such that a4s + bj G S \ {m}. Since S G N(a, b, X), we know that a4s + bj G S. Therefore, ajs + bj = m and, consequently, m_bi = s G S \ {0}.	□
Our next purpose will be to build recurrently G(N(a, b, X)) from its root and joining each vertex with its children by means of edges. In order to make easy that construction, we
A. M. Robles Pérez and J. C. Rosales: A combinatorial problem and numerical semigroups 331
will study the relation between the minimal system of generators of a numerical semigroup S and the minimal system of generators of S \ {m}, where m is a minimal generator of S greater than F(S). First of all, it is clear to observe that, if S is minimally generated by {m, m + 1,..., 2m - 1} (that is, S = {0, m, ^}), then S \ {m} = {0, m + 1, is minimally generated by {m + 1, m + 2,..., 2m + 1}. In other case we can apply the following result, which is [3, Corollary 18].
Proposition 3.3. Let S be a numerical semigroup with minimal system of generators msg(S) = {ni < n2 < • • • < np}. If i € {2,... ,p} and nj > F(S), then
{{ni,..., np} \ {nj}, if there exists j € {2,..., i — 1} such that nj + n1 — nj € S;
({n1,..., np} \ {nj}) U {nj + n1}, in other case.
Let us illustrate the previous results with an example.
Example 3.4. By Proposition 2.7, it is easy to see that S = ({5,7,8, 9,11}} belongs to N((1,2), (4,1), {5}). On the other hand, from Theorem 3.1, we know that the set of children of S in the tree G(N((1,2), (4,1), {5})) is
{S \ {m} | m € msg(S), m > F(S), and S \ {m} € N((1, 2), (4,1), {5})}.
Since F(S) = 6, we have that {m € msg(S) | m > F(S)} = {7,8, 9,11}. Furthermore, by Proposition 3.2, we know that S \ {m} € N((1,2), (4,1), {5}) if and on(y if m € {5} mid {m — 4, } n (S \ {0}) = 0. Thus, since that {7 — 4, 7-1} n (S \ {0}) = {8 — 4, } n (S \ {0}) = 0, {9 — 4, } n (S \ {0}) = 0, and {11 — 4, ^ } n (S \ {0}) = 0, we conclude that S = ({5, 7,8,9,11}} has two children. Namely, they are ({5, 7, 8, 9,11}}\{7} = ({5, 8, 9,11,12}} and ({5, 7, 8, 9,11}}\{8} = ({5, 7, 9,11,13}}, where we have applied Proposition 3.3.
Following the idea of the previous example, we can build G(N((1, 2), (4,1), {5})) in a recurrent way starting from its root, that is, from N = ({1}} (see Figure 1).
Let us observe that, since gcd({5} U {4,1}) = 1 and by Theorem 2.6, then we know that N((1,2), (4,1), {5}) is a finite Frobenius variety and, thereby, we have been able of building it completely in a finite number of steps.
Let us also observe that, if S € N(a, b, X), then g(S) is equal to the length of the path connecting S with N in the tree G((N(a, b, X)). Therefore, in order to build the elements of N(a, b, X) with a fixed genus g, we only need to build the elements of N(a, b, X) which are connected to N through a path of length less than or equal to g. Consequently, we have an algorithmic process to compute all the solutions of )he problem P(a, b, X, g).
For instance, in the tree G(N((1, 2), (4,1), {5})), the numerical semigroups which are connected to N through apath of length 6 are ({5,8,9,11,12}}, ({5,7,9,11,13}}, and ({5, 6,9,13}}. Therefore, the problem proposed in the introduction has three solutions. Namely, N\({5, 8, 9,11,12}} = {1, 2, 3,4,6, 7}, N\({5,7,9,11,13}} = {1,2,3,4, 6,8}, and N \ ({5,6, 9,11,13}} = {1, 2, 3,4,7,8}.
We finish with an example in which N(a, b, X) is an infinite Frobenius variety.
Example 3.5. Let us compute all the solutions of P((2,3), (4,2), {6,8}, 4). First of all, from Example 2.13, we know that M((2, 3), (4, 2), {6, 8}) = ({6, 8}} and, by Theorem 2.3, that the problem has a solution. Moreover, since gcd({6,8} U {4,2}) = 2 = 1,
332
Ars Math. Contemp. 15 (2018) 441-466
({1})
({2, 3})
({3,4, 5}) ({2, 5})
({3, 5, 7})
({5, 6, 7, 8, 9})
({4, 5, 7}) ({4, 5, 6})
({5, 7, 8, 9, 11}) ({5, 6, 8, 9}) ({5, 6, 7, 9})
({4, 5,11})
({5, 8, 9, 11, 12}) ({5, 7, 9, 11, 13}) ({5, 6, 9, 13}) ({5, 9, 11, 12, 13}) ({5, 9, 11, 13, 17})
Figure 1: Tree associated to the finite Frobenius variety N((1, 2), (4,1), {5}).
we have that N((2,3), (4,2), {6,8}) is a infinite Frobenius variety. However, in a finite number of steps, we can compute the elements of G(N((2,3), (4, 2), {6,8})) which are connected to N through a path of length 4, such as we show in Figure 2.
({1}) = N ({2, 3})
({4, 5, 6, 7}) ({3, 5, 7}) ({3,4}) ({2, 7})
({5, 6, 7, 8, 9}) ({4, 6, 7, 9}) ({4, 5, 6}) ({3, 7, 8}) ({3, 5}) ({2, 9})
Figure 2: Five first levels of the tree associated to the infinite Frobenius variety
N((2, 3), (4, 2), {6, 8}).
Therefore, the sets N \ ({5,6, 7, 8,9}) = {1,2, 3,4}, N \ ({4, 6,7,9}) = {1, 2, 3,5}, N \ ({4, 5, 6}) = {1, 2, 3, 7}, N \ ({3, 7, 8}) = {1, 2,4, 5}, N \ ({3, 5}) = {1, 2,4, 7}, and N \ ({2,9}) = {1,3,5, 7} are the (six) solutions of P((2,3), (4, 2), {6,8}, 4).
A. M. Robles Pérez and J. C. Rosales: A combinatorial problem and numerical semigroups 333
Remark 3.6. Let us observe that, in the construction of the trees, we can assume that X = 0 or that a, b are 0-tuples (see Remarks 2.14 and 2.15). Then, we obtain all the possible solutions in each case. In particular, if we consider jointly such assumptions, then we get the tree associated to the full family of numerical semigroups (see Remark 1.1).
4 A generalization of the problem
Along this section r and g are non-negative integers, a = (ai,..., an) and b = (bi,..., bn) are n-tuples of positive integers, and X is a non-empty subset of {r+1, We will denote by Pr (a, b, X, g) the (generalised) problem of computing all the subsets C of {r + 1, that fulfill the following conditions.
(GP1) The cardinality of C is equal to g.
(GP2) If x, y G {r + 1, and x + y G C, then C n {x, y} = 0.
(GP3) If x G C and ^ G {r + 1, for some i G {1,..., n}, then ^ G C.
(GP4) X n C = 0.
Let us observe that Po(a, b, X, g) = P(a, b, X, g).
It is clear that a set C is a solution of Pr (a, b, X, g) if and only if S = {0, r + 1, \ C is a numerical semigroup that fulfills the following conditions.
(GS1) g(S) = r + g.
(GS2) If s G S \ {0}, then as + b G Sn.
(GS3) X Ç S.
Let us denote by Nr (a, b, X) the set of all numerical semigroups which are subsets of {0, r + 1, and satisfy the conditions (GS2) and (GS3). Let us observe that, with this notation, the solutions of Pr (a, b, X, g) are the elements of the set
{{0, r+, 1 \ S | S G N(a, b, X) and g(S) = r + g}.
Moreover, Nr (a,b,X) = {S G N(a,b,X) | S Ç {0,r + 1, The following proposition is analogous to Theorem 2.3.
Proposition 4.1. Let us take Mr (a, b, X) = p|seN(a b x) S. Then Pr (a, b, X, g) has a solution if and only if the cardinality of N \ Mr (a, b, X ) is greater than or equal to g + r.
Proof. (Necessity.) If C is a solution of Pr (a, b, X, g), then S = {0, r + 1, \ C belongs to Nr (a, b, X) and g(S) = g + r. Since Mr (a, b, X) Ç S, then we conclude that the cardinality of N \ Mr (a, b, X) is greater than or equal to g + r.
(Sufficiency.) If {0, r + 1, \ Mr (a, b, X) = {ci < • • • < cs < • • • } and S = Mr(a, b, X) U {cg + 1, then it is easy to see that S G Nr (a, b, X) and g(S) = g + r. Therefore, C = {0, r +1, \ S is a solution of Pr(a, b, X, g).	□
Observe that the cardinality of N \ Mr (a, b, X) is greater than or equal to g + r if and only if the cardinality of {0, r + 1, \ Mr (a, b, X) is greater than or equal to g.
Proposition 4.2. Mr (a, b, X ) = M (a, b, X ).
334
Ars Math. Contemp. 15 (2018) 441-466
Proof. Since Nr (a, b, X) C N(a, b, X), then we have that
M K b, X ) = fl SeN (a,b,X) S C fl SeN (a,b,X) S = Mr (a b, X ).
Let us now see the other inclusion. Since {0, r + 1, —} G N(a, b, X) and N(a, b, X) is a Frobenius variety, we have that, if S G N(a, b, X), then S n {0, r +1, —} G N(a, b, X). In addition, S n{0,r + 1, —} C {0,r +1, —} and, thus, S n{0,r + 1, —} G Nr (a, b,X). In this way, R = {S n {0, r +1, —} | S G N"(a, b, X)} C Nr(a, b, X). Consequently, Mr K b, X) = DseNr(a,b,x) S CDseR S = flseN(a,b,x) S = M(a, b, X).	□
As an immediate consequence of Proposition 4.2 and Proposition 2.10, we have the next result.
Corollary 4.3. If gcd (X U {bi,..., b„}) = d, then Mr(a, b, X) = d ■ M(a, f, X).
Let us observe that, as a consequence fo the previous corollary, we can use Algorithm 2.11 in order to compute Mr (a, b, X).
The following result is the analogous to Theorem 2.6 for the current problem.
Corollary 4.4. The following conditions are equivalent.
1.	Nr (a, b, X) is finite.
2.	Mr (a, b, X) is a numerical semigroup.
3.	gcd(X U{bi,...,bn}) = 1.
Proof. The equivalence between conditions 2 and 3 is a consequence of Proposition 4.2 and Theorem 2.6. Now, let us see the equivalence between conditions 1 and 2.
(1. ^ 2.) It is enough to observe that the finite intersection of numerical semigroups is another numerical semigroup.
(2. ^ 1.) If S G Nr (a, b, X), then Mr (a, b, X) C S. Thus, S = Mr (a, b, X) U Y for some Y C N \ Mr (a, b, X). Since N \ Mr(a, b, X) is finite, then we can conclude that Nr (a, b,X) is finite.	□
Let us illustrate the previous results with several examples.
Example 4.5. Let us see that Pr((1, 2), (4,1), {5}, 6) has a solution if and only if r G {0,1,2}. Since {5} C {r + 1, -}, then r G {0,1, 2, 3,4}. By Proposition 4.2 and Example 2.12, we have that M = Mr ((1, 2), (4,1), {5}, 6) = ({5,9,11,13,17}). Since N \ M = {1, 2,3,4,6, 7, 8,12} has cardinality equal to 8, by applying Proposition 4.1, we easily deduce that Pr ((1, 2), (4,1), {5}, 6) has a solution if and only if r G {0,1,2}.
Example 4.6. If r G {0,1,2,3,4, 5}, then Nr ((2, 3), (4, 2), {6, 8}) is an infinite set. In fact, this is an immediate consequence of Corollary 4.4 and that gcd({4,2, 6, 8}) = 2 = 1.
Example 4.7. Let us compute Ps((2, 3), (4,2), {6, 8}, 9). By Proposition 4.2 and Example 2.13, we have that M3((2, 3), (4, 2), {6, 8}) = ({6, 8}). Now, if we apply the construction given in the sufficiency of Proposition 4.1, we have that {4,5,7, 9,10,11,13,15,17} is a solution.
If G is a tree and u, v are two vertices of G such that there exists a path between them, then we will say that u is a descendant of v. The next result has an easy proof.
A. M. Robles Pérez and J. C. Rosales: A combinatorial problem and numerical semigroups 335
Proposition 4.8. Nr (a, b, X) is the set of all descendants of {0, r + 1, in the tree G(N(a, b,X)).
A Frobenius pseudo-variety (see [4]) is anon-empty family P of numerical semigroups that fulfills the following conditions.
(PV1) P has a maximum element max(P) (with respect to the inclusion order).
(PV2) If S, T G P, then S n T G P.
(PV3) If S G P and S = max(P), then S U F(S) G P.
As an immediate consequence of Proposition 4.8 and the comment above to Example 7 in [4], we have the following result.
Proposition 4.9. Nr (a, b, X ) is a Frobenius pseudo-variety.
Let us observe that, if r > 1, then max(Nr (a, b, X)) = {0, r +1, = N. Therefore, by applying [4, Proposition 1], we have that Nr (a, b, X) is not a Frobenius variety.
Now, let us notice that the subgraph, of a t(ree, which is) formed by a vert(ex and all it)s descendants is also a tree. We will denote by G(Nr (a, b, X)) the subtree of G(N(a, b, X)) formed by {0, r +1, and all its descendants.
Example 4.10. The root of G(N3((1, 2), (4,1), {5})) is {0,4, = ({4,5, 6, 7}). Thus, from Example 3.4, we have that such a tree is given by Figure 3.
({4, 5, 6, 7})
({5, 6, 7, 8, 9})	({4, 5, 7}) ({4, 5, 6})
({5, 7, 8, 9,11}) ({5, 6, 8, 9}) ({5, 6, 7, 9})	({4, 5,11})
({5, 8, 9,11,12}) ({5, 7, 9,11,13}) ({5, 6, 9,13}) ({5, 9,11,12,13}) ({5, 9,11,13,17})
Figure 3: Tree associated to the Frobenius pseudo-variety N3((1, 2), (4,1), {5}).
Let us observe that Nr (a, 6, X) is the set of vertices in G(Nr (a, 6, X)), and that (S, S') G Nr (a, 6, X) x Nr (a, 6, X) is an edge of G(Nr (a, 6, X)) if and only if S' = S U {F(S)}. It is also clear that, if S g Nr (a, 6, X), then the set formed by the children of S in Nr (a, 6, X) is the same that the set formed by the children of S in N(a, 6, X). In this way, by applying Theorem 3.1, we have the next result.
Proposition 4.11. The graph G(Nr (a, 6, X)) is a tree with root {0, r +1, Moreover, the set of children of a vertex S in G(Nr (a, 6, X)) is
{S \ {m} | m G msg(S), m > F(S), and S \ {m} G N(a, 6, X)}.
336
Ars Math. Contemp. 15 (2018) 441-466
Now, let us notice that, by using Propositions 3.2 and 3.3, we can compute the children of any vertex S in G(Nr (a, b, X)) and, consequently, we have an algorithmic process to recurrently build the elements of Nr (a, b, X).
We finish this section with an illustrative example about the above comment.
Example 4.12. Let us compute all the solutions of P3 ((2,3), (4,2), {6,8}, 4). In order to do this, we have to determine the vertices of G(Ni((2,3), (4, 2), {6,8})) which are connected to {0,4, = ({4,5,6, 7}} through a path of length 4.
Let us observe that, if A is the set of vertices (of a tree) which are connected to the root through a path of length k, then the set formed by all vertices that are children of some vertex of A is just the set of vertices which are connected to the root through a path of length k + 1. Thus, if we denote by Aj the set formed by the vertices of G(N3((2, 3), (4,2), {6, 8})) which are connected to ({4, 5,6,7}} through a path of length i, then (by applying Propositions 4.11, 3.2, and 3.3) we obtain recurrently the following sets.
•	Ao = {({4, 5, 6, 7}}}
•	A1 = {({5, 6, 7, 8, 9}}, ({4, 6, 7, 9}}, ({4, 5, 6}}}
•	A2 = {({6, 7, 8, 9,10,11}}, ({5, 6, 8, 9}}, ({5, 6, 7, 8}}, ({4, 6, 9,11}}, ({4, 6, 7}}}
•	A3 = {({6, 8, 9,10,11,13}}, ({6, 7, 8,10,11}}, ({6, 7, 8, 9,11}}, ({6, 7, 8, 9,10}},
({5, 6, 8}}, ({4, 6,11,13}}, ({4, 6, 9}}}
•	A4 = {({6, 8,10,11,13,15}}, ({6, 8, 9,11,13}}, ({6, 8, 9,10,13}},
({6, 8, 9,10,11}}, ({6, 7, 8,11}}, ({6, 7, 8,10}}, ({6, 7, 8, 9}}, ({4, 6,13,15}}, ({4, 6,11}}}
Therefore, the set of solutions of P3 ((2,3), (4,2), {6,8}, 4) is
{({4, 5, 6, 7}} \ S | S e A4} = {{4, 5, 7, 9}, {4, 5, 7,10}, {4, 5, 7,11}, {4, 5, 7,13}, {4, 5, 9,10}, {4, 5, 9,11}, {4, 5,10,11}, {5, 7, 9,11}, {5, 7, 9,13}}.
References
[1]	M. Bras Amor6s, P. A. Garcia Sanchez and A. Vico Oton, Nonhomogeneous patterns on numerical semigroups, Internat. J. Algebra Comput. 23 (2013), 1469-1483, doi:10.1142/ s0218196713500306.
[2]	J. L. Ramirez Alfonsin, The Diophantine Frobenius Problem, volume 30 of Oxford Lecture Series in Mathematics and its Applications, Oxford University Press, Oxford, 2005, doi:10. 1093/acprof:oso/9780198568209.001.0001.
[3]	A. M. Robles Perez and J. C. Rosales, The numerical semigroup of phrases' lengths in a simple alphabet, Sci. World J. 2013 (2013), 459024 (9 pages), doi:10.1155/2013/459024.
[4]	A. M. Robles Peirez and J. C. Rosales, Frobenius pseudo-varieties in numerical semigroups, Ann. Mat. PuraAppl. 194 (2015), 275-287, doi:10.1007/s10231-013-0375-1.
[5]	J. C. Rosales, Families of numerical semigroups closed under finite intersections and for the Frobenius number, Houston J. Math. 34 (2008), 339-348.
[6]	J. C. Rosales and P. A. Garcia Sanchez, Numerical Semigroups, volume 20 of Developments in Mathematics, Springer, New York, 2009, doi:10.1007/978-1-4419-0160-6.