Cedric Chauve

A bijection between planar constellations and some colored Lagrangian trees

Keywords: planar maps, trees, enumeration, bijection, Lagrange formula

Constellations are colored planar maps that generalize different families of maps (planar maps, bipartite planar maps, bi-Eulerian planar maps, planar cacti, . . . ) and are strongly related to factorizations of permutations. They were recently studied by who describe a correspondence between these maps and a family of trees, called Eulerian trees. In this paper, we derive from their result a relationship between planar constellations and another family of trees, called stellar trees. This correspondence generalizes a well known result for planar cacti, and shows that planar constellations are colored Lagrangian objects (that is objects that can be enumerated by the Good-Lagrange formula). We then deduce from this result a new formula for the number of planar constellations having a given face color distribution, different from the formula one can derive from the results of Bousquet-Mélou and Schaeffer, along with systems of functional equations for the generating functions of bipartite and bi-Eulerian planar maps enumerated according to the number of vertices of each color and the number of faces.

The study of planar maps is a classical, but still very active, field in enumerative combinatorics, that started in the 60's with Tutte. Recently, Bousquet-Mélou and Schaeffer [START_REF] Bousquet-Mélou | Enumeration of planar constellations[END_REF] studied an interesting family of planar maps with colored vertices, called planar constellations, which generalizes several families of planar maps. For this study, they used a technique introduced by Schaeffer [START_REF] Schaeffer | Conjugaison d'arbres et cartes combinatoires aléatoires[END_REF][START_REF] Schaeffer | Random sampling of large planar maps and convex polyhedra[END_REF], the conjugation of plane trees. In this paper, we are interested in the exact enumeration of planar constellations and our main goal is to derive from the work of Bousquet-Mélou and Schaeffer a complete bijective proof of a correspondence between planar constellations and a family of colored Lagrangian trees, called stellar trees.

This paper is divided into five sections. In the first one, we define planar constellations, recall some combinatorial facts about this family of maps and we state our main result (Theorem 5). In the second section, we recall some facts from the paper of Bousquet-Mélou and Schaeffer [START_REF] Bousquet-Mélou | Enumeration of planar constellations[END_REF]. In particular, we introduce regular constellations and describe their relationship to Eulerian maps and Eulerian trees by the conjugation of trees method. In the third and fourth sections, we prove our main result and we apply it to obtain a new formula for the number of planar m-constellations having a given face color distribution and systems of functional equations for the enumeration of planar constellations, bipartite planar maps and

Introduction to constellations

Planar m-constellations. A planar map C is a proper embedding of a connected graph on the sphere. It satisfies

v(C) + f (C) -e(C) = 2, (1)
where v(C) (resp. f (C), e(C)) is the number of vertices (resp. faces, edges) of C. The degree of a vertex (resp. face) is the number of incident edges to this vertex (resp. face). Two maps are isomorphic if there exists an orientation preserving homeomorphism of the sphere that maps vertices (resp. edges, faces) of one of the maps onto vertices (resp. faces, edges) of the other map, and preserves incidences. Here we consider maps up to isomorphism (for more information about combinatorial maps, see for example the work of Cori and Machì [START_REF] Cori | Maps, hypermaps and their automorphisms: a survey[END_REF]).

Definition 1.1 Let m ≥ 2. A planar m-constellation is a planar map whose faces are colored black and white in such a way that

• adjacent faces to a given white face are black and vice versa,

• the degree of any black face is m,

• the degree of any white face is a multiple of m.

A planar m-constellation is rooted if one of its edges (the root edge) is distinguished.

In the rest of this paper, we use the expressions m-constellations or constellations for planar rooted m-constellation. We call polygons (or m-gons) the black faces of an m-constellation, and root polygon the polygon incident to the root edge.

Constellations are naturally well colored objects. Indeed one can associate with every vertex of an m-constellation a color chosen from a set {c 1 , . . . , c m } of m colors, in such a way that the vertices of any m-gon are colored with c 1 , . . . , c m in counterclockwise order and the vertices incident to the root edge are colored with c m-1 and c m ‡ (see Fig. 1, where the root edge is dashed).

color c 1 color c 2 color c 3 root edge Fig. 1: A 3-constellation † Most of this work is a part of the doctoral thesis of the author [START_REF] Chauve | Structures arborescentes : problèmes combinatoires et algorithmiques[END_REF], under the supervision of Serge Dulucq in LaBRI (Université Bordeaux I). A preliminary version appeared in the proceedings of the FPSAC'01 conference [START_REF] Chauve | Another enumeration of constellations[END_REF]. ‡ This convention differs slightly from the paper of Bousquet-Mélou and Schaeffer [START_REF] Bousquet-Mélou | Enumeration of planar constellations[END_REF].

Known results about constellations. Constellations are interesting for different reasons. First, they generalize different families of planar maps: 2-constellations such that every white face has degree 4 are in correspondence with rooted planar maps [START_REF] Schaeffer | Conjugaison d'arbres et cartes combinatoires aléatoires[END_REF], 2-constellations are in correspondence with bipartite rooted planar maps [START_REF] Schaeffer | Conjugaison d'arbres et cartes combinatoires aléatoires[END_REF], 3-constellations are in correspondence with Eulerian bipartite planar maps (also called bi-Eulerian maps) [START_REF] Liskovets | Enumeration of unicursal maps[END_REF][START_REF] Poulalhon | Problèmes énumératifs autour des cartes combinatoires et des factorisations dans le groupe symétrique[END_REF][START_REF] Poulalhon | A note on bipartite eulerian planar maps[END_REF]. We will make use of some of these correspondences in Section 4. Moreover, constellations are strongly related to factorizations in the symmetric group, especially minimal ordered transitive factorizations (see, for example, [START_REF] Hanusse | constellations et groupes : questions algorithmiques[END_REF][START_REF] Bousquet-Mélou | Enumeration of planar constellations[END_REF] for a precise exposition on this topic). In studying the enumeration of such factorizations, Bousquet-Mélou and Schaeffer established a correspondence between m-constellations and a family of plane trees called m-Eulerian trees, and deduced from this correspondence the following results.

Theorem 1 [9, Theorem 2.3] Let m ≥ 2.
The number of rooted m-constellations having d i white faces of degree mi

(for i ≥ 1), is m(m -1) f -1 × [(m -1)p]! [(m -1)p -f + 2]! × ∏ i≥1 1 d i ! mi -1 i -1 d i , ( 2
)
where p = ∑ id i and f = ∑ d i .

Corollary 1 [START_REF] Bousquet-Mélou | Enumeration of planar constellations[END_REF]Corollary 2.4] Let m ≥ 2 and p ≥ 1. The number of rooted m-constellations with exactly p polygons is

(m + 1)m p-1 [(m -1)p + 2][(m -1)p + 1] mp p . (3)
Moreover, for given m ≥ 2, p and f such that p ≥ f , summing (2) over all configurations (d 1 , d 2 , . . .) such that p = ∑ id i and f = ∑ d i leads easily to the following result.

Theorem 2 [START_REF] Bousquet-Mélou | [END_REF] Let m ≥ 2, f ≥ 1 and p ≥ f . The number of m-constellations having p polygons and f white faces is m

[(m -1)p -1]! ( f -1)![(m -1)p -f + 2]! p-f ∑ j=0 (m -1) j+ f mp p -f -j j + f f . (4)
They also deduced from this correspondence between constellations and Eulerian trees a system of algebraic equations defining the generating function of m-constellations having a given number of white faces and a given number of vertices of every color c 1 , . . . , c m .

Proposition 1 [9, Remark 1] Let (x 1 , . . . , x m+1 ) be a set of m + 1 formal variables, (n 1 , . . . , n m , f ) be a set of m + 1 positive integers, C (n 1 ,...,n m , f ) be the set of m-constellations having n i vertices of color c i (i ∈ [m]) and f white faces, and g(x 1 , . . . ,

x m+1 ) = ∑ (n 1 ,...,n m , f ) C (n 1 ,...,n m , f ) x n 1 1 • • • x n m m x f m+1 . Then g(x 1 , . . . , x m+1 ) = u 1 (x 1 , . . . , x m+1 )dx 1 ( 5
)
where, for k = 1, . . . , m + 1,

u k (x 1 , . . . , x m+1 ) = ∏ i∈[m+1],i =k x i + ∑ j =i u j (x 1 , . . . , x m+1 ) . (6)
Constellations with one white face: cacti. If the combinatorial study of constellations started recently, the particular class of constellations with one white face has been considered by several authors, under the name of planar m-cacti or planar m-ary cacti (here, following our convention for constellations we call them m-cacti or cacti). One can cite for example Goulden and Jackson [START_REF] Goulden | The combinatorial relationship between trees, cacti and certain connection coefficients for the symmetric group[END_REF], Zvonkin et al., [START_REF] Bouya | Topological classification of complex polynomials: new experimental results[END_REF][START_REF] Marraki | Cacti, braids and complex polynomials[END_REF], or Bousquet et al. [START_REF] Bóna | Enumeration of m-ary cacti[END_REF][START_REF] Bousquet | Théorie des espèces et applications au dénombrement de cartes et de cactus planaires[END_REF][START_REF] Bousquet | Quelques résultats sur les cactus planaires[END_REF][START_REF] Bousquet | Enumération et génération aléatoire de cactus m-aires[END_REF]. Among other results, these authors gave formulas for the number m-cacti having p polygons, or equivalently (thanks to Euler's formula (1)), ((m -1)p + 1) vertices and m-cacti

having n i vertices of color c i , for i ∈ [m].
Theorem 3 Let m ≥ 2 and p ≥ 1. The number of m-cacti having p polygons is

1 (m -1)p + 1 mp p . (7)
One can remark that this result also follows from Theorem 1, with d p = 1 and d i = 0 for i = p.

(∑ m i=1 n i ) -1 = (m -1)p). The number of m-cacti having n i vertices of color c i (i = 1, . . . , m) is 1 p m ∏ i=1 p n i . ( 8
)
The proofs of these two results are based on the Good-Lagrange formula for the inversion of multivariable formal power series [START_REF] Bergeron | Combinatorial species and tree-like structures, volume 67 of Encyclopedia of mathematics and its applications[END_REF][START_REF] Bousquet | A bijective proof of the arborescent form of the multivariable Lagrange inversion formula[END_REF][START_REF] Good | Generalizations to several variables of Lagrange's expansion, with applications to stochastic processes[END_REF][START_REF] Goulden | Combinatorial enumeration[END_REF][START_REF] Goulden | Multivariable Lagrange inversion, Gessel-Viennot cancellation, and the matrix tree theorem[END_REF] and to the notion of Lagrangian trees, defined below. Definition 1.2 A family of unlabelled rooted trees where every vertex has a color taken from a set of colors

(c 1 , • • • , c m ), such that a n 1 ,...,n m is the number of trees having n i vertices of color c i (i = 1, . . . , m) is called Lagrangian if its ordinary generating function, g(x 1 , . . . , x m ) = ∑ n 1 ,...,n m a n 1 ,...,n m x n 1 1 • • • x n m m
, satisfies a system of functional equations of the form g(x 1 , . . . , x m ) = f (g 1 (x 1 , . . . , x m ), . . . , g m (x 1 , . . . , x m )) and g i (x 1 , . . . , x m ) = x i r i (g 1 (x 1 , . . . , x m ), . . . , g m (x 1 , . . . , x m )) (g i is the generating function of the subset of the considered trees rooted at a vertex of color c i ), for some m-variable series r i and f such that r i (0, . . . , 0) = 0 (i = 1, . . . , m).

It follows that such family of trees can be enumerated, under various conditions, by the Good-Lagrange formula and related results (see [START_REF] Bergeron | Combinatorial species and tree-like structures, volume 67 of Encyclopedia of mathematics and its applications[END_REF] for example). For instance, Theorems 3 and 4 follow from a coding (described below) of cacti by a family of Lagrangian trees, m-cacti trees (Definition 1.3 and Fig. 2). Definition 1.3 Let m ≥ 2. An m-cacti tree is a rooted plane tree such that

• every vertex is colored with a color from (c 1 , • • • , c m ),
• the root is colored with c m ,

• for every vertex of color c i (i = 1, . . . , m), its children are organized as a totally ordered set of iblocks, where an i-block is a (unordered) set of (m -1) vertices such that no two vertices have the same color and no vertex is colored with c i .

There is an immediate coding of m-cacti having n i vertices of color c i (i = 1, . . . , m) by m-cacti trees having n i vertices of color c i (i = 1, . . . , m). Indeed, let T be an m-cacti tree: to obtain an m-cactus from T , it suffices to perform a preorder traversal § of T and replace every i-block, together with the parent vertex of the elements of this block, by a polygon. New results. In this paper, we are mainly interested in enumerating constellations under some constraints related to the color of vertices and the number of white faces. Our main result (Theorem 5 below) is a one-to-one correspondence between m-constellations and a family of (m + 1)-colored Lagrangian trees, called (m + 1)-stellar trees (see Definition 1.4).

Definition 1.4

Let m ≥ 3. An m-stellar tree is a plane m-colored tree such that

• the root is colored with c m-1 ,
• every vertex colored with c i (i ∈ [m]) has its children organized as a totally ordered set of (i, j)blocks (with j ∈ [m] and i = j), where an (i, j)-block is a (unordered) set of (m -2) vertices such that no two vertices have the same color and no vertex is colored with c i or c j ,

• the first (leftmost) child-block of the root is a (m -1, m)-block.

color c 1 color c 2 color c 3 color c 4

Fig. 3: A 4-stellar tree

Theorem 5 There is a one-to one correspondence between m-constellations having n i vertices of color c i (i = 1, . . . , m) and f white faces, one of them being distinguished, and (m + 1)-stellar trees having n i vertices of color c i (i = 1, . . . , m) and ( f -1) vertices of color c m+1 .

This result is a generalization of the coding of cacti by cacti trees (an (m + 1)-stellar tree with no vertex of color c m+1 is an m-cacti tree), and can be be deduced, by an easy computation, from Proposition 1 (see Remark 4.4). However, the proof we propose in Section 3 is fully bijective and, we believe, enlightens the combinatorics of planar constellations. This correspondence induces bijective proofs of the following results, stated precisely in Section 4:

• a new formula for the number of m-constellations having p polygons and f ( f ≥ 2) white faces (Theorem 6), which induces a new formula for the number of bipartite planar maps having a given number of edges and a given number of vertices (our bijective proof also induces a random generation algorithm for the considered objects) ;

• some system of functional equations for the enumeration of Eulerian and bi-Eulerian planar maps (Proposition 4 and Proposition 5).

Regular Eulerian maps and regular Eulerian trees

In this section, we describe the relationship between constellations and a family of planar trees called regular Eulerian trees, through the conjugation of trees. The material of this section is based on [9, Sections 2,4, and 5].

Regular m-Eulerian maps. We begin with the notion of regular constellation: an m-constellation is said to be regular if all its white faces have degree m.

Lemma 2.1

There is a one-to-one correspondence between m-constellations having n i vertices colored with c i (i = 1, . . . , m) and f white faces, and regular (m + 1)-constellations having n i vertices of color c i (i = 1, . . . , m) and f vertices colored with c m+1 .

Proof. [9, Proof of Corollary 2.4] Let C be an m-constellation. We obtain a regular (m + 1)-constellation in the following way. For every white face F of C, add a vertex x with color c m+1 . Next remove all the edges which are incident, in F, to a vertex of color c 1 and one of color c m . Then, for every vertex y of F colored by c 1 or c m , add an edge between x and y (see Fig. 4). ✷ We recall that the dual map C * of a map C describes the incidence relations between the faces of C: the vertices (resp. faces) of C * are the faces (resp. vertices) of C, and there is an edge of C * incident to the faces F and F ′ of C * if and only if there is an edge incident to the corresponding vertices in C (Fig. 5). We introduce now a family of planar maps, called regular m-Eulerian maps, which are dual of regular m-constellations. Definition 2.1 A bipartite map is a map whose vertices are of two types, say A-vertices and B-vertices, such that every edge is incident to an A-vertex and a B-vertex. Definition 2.2 A regular m-Eulerian map is a bipartite planar map such that the degree of any vertex is m.

The duality relation clearly induces a one-to-one correspondence between regular m-Eulerian maps and regular m-constellations. By convention, we associate the A-vertices (resp. B-vertices) of an m-Eulerian map to the polygons (resp. white faces) of its dual m-constellation and we represent them in the figures by squares (resp. triangles). This correspondence leads immediately to the following property.

Property 2.1 The coloring of the vertices of a regular m-constellation C induces a coloring of the faces of its dual map E such that:

1. the root edge of E is incident to a face F colored with c m-1 and a face F ′ colored with c m (when following the root edge from its A-vertex to its B-vertex one has F ′ on the left and F on the right) ;

for every edge e of E, if when following e from its A-vertex to its B-vertex one has on the left (resp.

right) a face F (resp. F ′ ) colored with c i (resp. c j ), then j = (i mod m) + 1.

If we call a coloring of the faces of a regular m-Eulerian map E satisfying the previous property a proper coloring of E, we can notice that there is exactly one proper coloring of E, determined by its root edge. Regular m-Eulerian trees. In this paragraph, we introduce a family of plane trees, called regular m-Eulerian trees (Definition 2.3 and Fig. 6) and the conjugation of trees algorithm, which allows us to reduce the problem of enumerating regular m-Eulerian maps to enumerating regular m-Eulerian trees [START_REF] Bousquet-Mélou | Enumeration of planar constellations[END_REF].

Definition 2.3

A regular m-Eulerian tree is a plane tree such that:

• the vertices are of two types (A-vertices and B-vertices) and every edge is incident to an A-vertex and a B-vertex,

• the root is an A-leaf (an A-vertex incident to exactly one edge),

• every internal vertex (a vertex incident to more than one edge) has exactly (m -1) children,

A-vertex B-vertex

Fig. 6: A regular 4-Eulerian tree

• every internal A-vertex has exactly one child which is an internal B-vertex.

The next algorithm is a specialization to regular m-Eulerian trees of a matching procedure defined in [START_REF] Bousquet-Mélou | Enumeration of planar constellations[END_REF]. It runs two successive preorder traversals of a regular m-eulerian tree T , computing a set of pairs (x, y) of vertices of T such that x is an A-leaf and y a B-leaf (we say that we match x and y, see Fig. 7):

1. let S = / 0 when the first traversal starts ;

2. when visiting a B-leaf x for the first time, add x to S ;

3. when visiting an unmatched A-leaf y, if S = / 0, then match y with the last visited B-leaf x of S and remove x from S.

We can immediately deduce from the definition of regular m-Eulerian trees that, after this matching, all the B-leaves are matched but there remain m unmatched A-leaves: we call such A-leaves the single leaves.

A regular m-Eulerian tree T is said to be balanced if its root is a single leaf. In the figures that follows, the matched leaves are indicated by a dashed edge and the single leaves are displayed inside a circle. Bousquet-Mélou and Schaeffer proved the following result, which can be seen as an analogue for trees and maps of the relationship between conjugation of words and plane trees (see [START_REF] Schaeffer | Conjugaison d'arbres et cartes combinatoires aléatoires[END_REF] for an explanation of this analogy).

Proposition 2 [START_REF] Bousquet-Mélou | Enumeration of planar constellations[END_REF] There is a one-to-one correspondence between balanced regular m-Eulerian trees having p internal A-vertices and f internal B-vertices and regular m-Eulerian maps having (p + 1) A-vertices and f B-vertices.

This result relies on the following construction (see [START_REF] Bousquet-Mélou | Enumeration of planar constellations[END_REF]Sections 5 and 6]). Let T be a balanced m-Eulerian tree: if, for every pair (x, y) of matched leaves, one adds an edge between x and y, one obtains an unrooted bipartite planar map M(T ) such that all the single leaves are incident to the same face of M(T ). One now wants to transform M(T ) into a regular m-Eulerian map. First one adds, in the face of M(T ) containing the single leaves, a plane tree formed of an internal A-vertex and m B-leaves: this tree is called a star. Next, for i ∈ [m], one matches the i th B-leaf of the star (visited from right to left) to the i th single leaf of T visited during a preorder traversal of T . We denote by M ′ (T ) the unrooted bipartite planar map thus obtained. Finally, for every pair (x, y) of matched leaves, the parent of x (resp. y) in T being denoted x ′ (resp. y ′ ), one removes the vertices x and y (and the edges incident to these vertices) and adds an edge incident to x ′ and y ′ . One obtains in this way an unrooted bipartite planar map such that every vertex has degree m. If we root this map at the edge incident to the A-vertex of the star and to the only child of the root of T , one obtains a regular m-Eulerian map (Fig. 8). We do not describe the inverse construction, which is far more complicated (see [START_REF] Bousquet-Mélou | Enumeration of planar constellations[END_REF] for such a description, and the works of Schaeffer [START_REF] Schaeffer | Random sampling of large planar maps and convex polyhedra[END_REF] and Poulalhon [START_REF] Poulalhon | Problèmes énumératifs autour des cartes combinatoires et des factorisations dans le groupe symétrique[END_REF] for other applications of the conjugation of trees in enumeration and random generation of planar maps and related objects). The next two properties follow immediately from the previous construction.

Property 2.2 Let T be a regular m-Eulerian tree and E the corresponding regular m-Eulerian map. The internal A-vertices (resp. internal B-vertices) of T (including the star) correspond to the A-vertices (resp. B-vertices) of E.

Property 2.3 Let T be a regular m-Eulerian tree and E the corresponding regular m-Eulerian map (by Proposition 2). For every face F of M ′ (T ), there is exactly one edge incident to two matched leaves (an A-leaf x and a B-leaf y) such that following the edge (x, y) from x to y one has F on the right: we call x the closing A-leaf of F. This closing relation induces a one-to-one correspondence between the A-leaves of T and the faces of E.

-→ Proof. This is a direct consequence of Properties 2.1, 2.2 and 2.3 and of the coloring algorithm described above. ✷ We now focus on unrestricted regular m-Eulerian trees (i.e. balanced and unbalanced trees), and we show that the enumeration of balanced trees can be reduced to the enumeration of unrestricted trees (Lemma 3.4).

Let T be a regular m-Eulerian tree, r its root and x a leaf other that r. We say that we replant T on x if we use x as the new root, without changing the circular order of edges around vertices (we denote by T x the tree thus obtained, see Fig. 10).

Lemma 3.2 Let T be a regular m-Eulerian tree and x a leaf of T .

1. Two leaves x ′ and x ′′ match in T if and only if they match in T x .

2. If the coloring of T with c k as initial color (for some k ∈ [m]) induces that x is colored with c i (for some i ∈ [m]), then in the coloring of T x with c i for initial color, every leaf of T x has the same color as in the coloring of T with c k as initial color.

Proof. The proof of point 1 follows immediately from the fact that if the preorder traversal of T visits successively the leaves x 0 = r, x 1 , . . . , x i = x, . . . , x n , then the preorder traversal of T x visits successively the leaves x i = x, x i+1 , . . . , x n , x 0 = r, x 1 , . . . , x i-1 (see Fig. 10). This, together with the fact that the matching of leaves relies only on the order of visit of the leaves in a preorder traversal induces that replanting a tree does not modify the matched leaves.

For point 2, we say that the color of an edge (x, y) (with x the parent of y) is the color of the vertex y. Hence, it follows from the coloring algorithm (whatever the initial color for this coloring) that for every A-vertex (resp. B-vertex) z, we can choose an edge e incident to z and colored with c 1 in such a way that visiting, in counterclockwise (resp. clockwise) order all the edges incident to z, starting from e, makes visit edges successively colored with c 1 , . . . , c m . Clearly, replanting a tree does not modify this coloring of the edges, which proves our result. ✷ If T is unbalanced, there is a single A-leaf of T , say x, colored with c i (for some i ∈ [m]). We deduce from Lemma 3.2 that T x is balanced and that its single leaves are the same as the single leaves of T . If c i = c m , the result follows immediately from the previous case. Otherwise, we notice that the color c k of every vertex of T x , colored with c i for initial color, is obtained from its color c j in T , colored with c m for initial color, by k = (( j + mi -1) mod m) + 1, and the result follows from this remark and from the case Proof. Let T be a regular m-Eulerian tree having n i A-leaves colored with c i (i ∈ [m]), and R(T ) the set of regular m-Eulerian trees obtained by replanting T on one of its A-leaves colored with c m . Replanting a tree does not change the matched leaves, consequently the trees of R(T ) are pairwise distinct (due to the position of the single A-leaf colored with c m relatively to the root), which implies that there are n m trees in R(T ). Moreover, it follows from Lemma 3.2 that every tree of R(T ) has exactly n i A-leaves colored with c i (i = 1, . . . , m), and from Lemma 3.3 that only one of these trees is balanced (the one replanted on the single leaf colored with c m ). As for every T ′ ∈ R(T ), R(T ′ ) = R(T ), the set of all the regular m-Eulerian trees having n i A-leaves colored with c i (i ∈ [m]) can partitioned into sets of n m trees, each one containing only one balanced tree, which implies the result.

✷

From m-Eulerian trees to m-stellar trees. We conclude this section by describing a correspondence between m-Eulerian trees and m-stellar trees, which leads to a proof of Theorem 5.

Lemma 3.5 There is a one-to-one correspondence between regular m-Eulerian trees having n i A-leaves colored with c i (i ∈ [m]) and m-stellar trees having n i vertices colored with c i (i ∈ [m -1]

) and (n m -1) vertices colored with c m .

Proof. Let T be a regular m-Eulerian tree having n i A-leaves colored with c i (i = 1, . . . , m). The principle of the transformation of T into an m-stellar tree S is to remove, in four steps, all of the internal vertices and the B-leaves of T . We illustrate this construction with an example through this proof.

Step 1. One removes all the B-leaves of T (we denote by T 1 the tree thus obtained). By the definition of a regular m-Eulerian tree, we can say that every internal A-vertex of T 1 has exactly one child, which is an internal B-vertex. The reverse construction (from T 1 to T ) follows immediately from the fact that if an internal A-vertex of T is colored with c i , its (m -1) children are respectively colored, from left to right, by c i+1 , . . . , c m , c 1 , . . . , c i-1 .

←→

color c 1 color c 2 color c 3 color c 4

Step 2. Next, one removes the B-vertices from T 1 (all of them are internal vertices) by merging every B-vertex x with its parent y, the resulting vertex being colored with the color of y. We denote by T 2 the tree thus obtained, which has only vertices of the same type (A-vertices). In the following figures, we display the vertices with circles.

c j -→ c i c i T ′ 1 T ′ m-1 T ′ 1 T ′ m-1
In our example, we have the following transformation.

←→ color c 1 color c 2 color c 3 color c 4 color c 1 color c 2 color c 3 color c 4
We can deduce from the coloring of T the following properties about T 2 .

1. The root r is colored with c m and has (m -1) children totally ordered and colored in such a way that the i th rightmost child is colored with c i .

2. Let x = r be a vertex of T 2 , colored with c i (for some i ∈ [m]). There is exactly one k ∈ [m] (k = i) such that no child of x is colored with c k . Moreover, the children of x are totally ordered, from left to right, by cyclically decreasing colors, starting at c k-1 (c k-1 , . . . , c 1 , c m , c m-1 , . . . , c k+1 ).

3. The tree T 2 has n i leaves colored with c i (i = 1, . . . , m -1) and (n m -1) leaves colored with c m (due to the fact that the root of T 2 is no more a leaf).

For the reverse transformation, it suffices to "explode" every internal vertex x of T 2 colored with c i (i ∈ [m]) into an edge incident to an A-vertex colored with c i and a B-vertex colored with the color which does not appear among the children of x (point 2 above).

Step 3. Next, one removes the internal vertices from T 2 in the following way. Let x be a vertex of T 2 other that the root, colored with c i (for some i ∈ [m]), y the only child of x colored with c i (see point 2 above) and c j ( j = i) the color which does not appear among the children of x. One removes y from the children of x and one grafts its subtrees (the subtrees having for roots the children of y) under x, to the left of its other children, which, without y, are now organized as an (i, j)-block.

T ′ 1 T ′ k x 1 x m-1 x j-1 x j+1 y T ′ 1 T ′ k -→ x 1 x j-1 x j+1 x m-1
Applying recursively this operation to the subtrees of x in the new tree gives an m-stellar tree T ′ having n i vertices colored with c i (i = 1, . . . , m -1) and n m vertices colored with c m .

color c 1 color c 2 color c 3 color c 4

←→

The reverse transformation proceeds as follows. During a preorder traversal of T ′ , for every internal vertex x (other that the root) colored with c i (for some i ∈ [m]), one removes the edges adjacent to x and to its children blocks, except for the rightmost block, one adds a vertex y colored with c i into the children of x (its color induces its position among these children) and one grafts under y the removed blocks.

Step 4. Finally, it suffices to remove the c m -colored root of the current tree, to use its c m-1 -colored child x as new root, to create a new (m -1, m)-block with its (m -2) other children that is inserted as the first (leftmost) child-block of x and to reorder the vertices in the blocks by increasing color. The reverse transformation is immediate, which concludes the proof of this lemma. ✷ Proof of Theorem 5. This is a direct consequence of Lemma 2.1 (which relates m-constellation and regular (m + 1)-constellations), the correspondence induced by duality between regular Eulerian maps and regular constellations, Proposition 2 (which relates regular constellations to balanced regular Eulerian trees), Lemmas 2.1, 3.1 and 3.4 (relating balanced regular Eulerian trees and unrestricted regular Eulerian trees), and Lemma 3.5 above. ✷

Enumerative consequences

In this section, we deduce from Theorem 5 enumerative results about constellations, bipartite planar maps and bi-Eulerian planar maps.

Constellations having a given face color distribution.

Theorem 6 Let m ≥ 2, f ≥ 2 and p ≥ f . The number of m-constellations having p polygons and f white faces is

1 f [(m -1)p -f + 2] m -1 m f -1 (m -1)p f -1 p-f +1 ∑ k=0 m k+ f mp -f -k p -f -k k + f -2 f -2 (9)
Remark 4.1 This result is concerned with the same problem that Theorem 2, that is enumerating constellations having a given face color distribution (polygons and white faces), but proposes a different formula from [START_REF] Bousquet | Théorie des espèces et applications au dénombrement de cartes et de cactus planaires[END_REF]. It is possible to deduce ( 9) from ( 4), but the calculus involved is not trivial [START_REF] Bousquet-Mélou | [END_REF]. Moreover, our approach is purely constructive and induces a uniform random generation algorithm for constellations having a given face distribution (see Remark 4.3). We should also notice that, unlike Theorem 2 our result is limited to constellations having at least two white faces. However the case of cacti, that is Theorem 3, follows immediately from a slight restriction of our proof of Theorem 6 (see Remark 4.2 below).

We now turn to the proof of Theorem 6. The Euler's formula [START_REF] Arquès | Relations fonctionnelles et dénombrement des hypercartes planaires pointées[END_REF] implies that an m-constellation with p polygons and f white faces has n = p(m -1)f + 2 vertices. Hence, in order to prove Theorem 6, we will deduce from Theorem 5 a formula for the number of m-constellations having n vertices and f white faces, and replace n by p(m -1)f + 2 in this formula to obtain [START_REF] Bousquet-Mélou | Enumeration of planar constellations[END_REF]. Let Cm,n, f be the number of m-constellations having n vertices and f white faces.

We deduce from Theorem 5 that Cm,n, f follows immediately from the number of (m + 1) stellar trees having n vertices of color belonging to (c 1 , . . . , c m ) and f -1 vertices of color c m+1 (it suffices to divide this number by f ). This leads us to the introduction of the family of sketched m-stellar trees. • for every A-vertex, its children are organized as a totally ordered set of A-blocks (where an A-block is a totally ordered set of (m -2) A-vertices) and B-blocks (where a B-block is a totally ordered set of (m -3) A-vertices, followed by one B-vertex) ;

• the first (leftmost) child-block of the root is an A-block ;

• for every B-vertex, its children are organized as a totally ordered set of A-blocks.

It is clear that such a tree S is obtained from an m-stellar tree T by replacing vertices colored with c m+1 by B-vertices and others vertices by A-vertices. We say that S is the sketch of T . Moreover, these trees are Lagrangian trees, and we will count them with a bijective proof of the Good-Lagrange formula [START_REF] Bousquet | A bijective proof of the arborescent form of the multivariable Lagrange inversion formula[END_REF][START_REF] Goulden | Multivariable Lagrange inversion, Gessel-Viennot cancellation, and the matrix tree theorem[END_REF].

For our purpose, we need to distinguish three types of edges in sketched stellar trees: an edge incident to an A-vertex and an A-block (resp. to an A-vertex and a B-block ; to a B-vertex and an A-block) is a 1-edge (resp. 2-edge ; 3-edge). As before, we represent A-vertices by squares and B-vertices by triangles.

Lemma 4.1 Let m ≥ 3 and S be a sketched m-stellar tree having f B-vertices and k 3-edges. The number of m-stellar trees having S for sketch is

(m -2) f (m -1) k .
Proof. To transform S into an m-stellar tree having S for sketch, we can use the following rules, applied during a preorder traversal of S: 2. if an edge incident to a vertex x colored with c i and to a block b is a 1-edge (x is an A-vertex and b is an A-block ), then the (m -2) vertices of b must respectively be colored with the colors other that c m and c i , in increasing order from left to right ;

1-edges 2-edges 3-edges

3. if an edge incident to a vertex x colored with c i and to a block b is a 2-edge (x is an A-vertex and b is a B-block), we must choose a color c j ( j = i and j = m) that will not appear among the vertices of b, color the (m -3) A-vertices of b with the colors other that c m , c j and c i , in increasing order from left to right, and color the B-vertex of b with c m ;

4. if an edge incident to a vertex x colored with c i and to a block b is a 3-edge (x is a B-vertex, which implies that c i = c m , and b is an A-block), we must choose a color c j ( j = m) that will not appear among the vertices of b and color the (m -2) A-vertices of b with the colors other that c m and c j , in increasing order from left to right.

The result follows immediately from these rules. ✷ It follows that the enumeration of m-stellar trees having n (c 1 , . . . , c m-1 )-colored vertices and f c mcolored vertices reduces to the enumeration of sketched m-stellar trees. Following two bijective proofs of the Good-Lagrange formula [START_REF] Bousquet | A bijective proof of the arborescent form of the multivariable Lagrange inversion formula[END_REF][START_REF] Goulden | Multivariable Lagrange inversion, Gessel-Viennot cancellation, and the matrix tree theorem[END_REF] we can reduce this problem to the enumeration of a family of enriched endofunction, which we call sketched m-stellar endofunctions. such that the preimage g -1 (x) of every element of {0} ∪ [n, p] is organized (enriched in the language of species theory [START_REF] Bergeron | Combinatorial species and tree-like structures, volume 67 of Encyclopedia of mathematics and its applications[END_REF]) with the following combinatorial rules:

1. for every A-element x, the preimage g -1 (x) of x is organized as a totally ordered set of labeled A-blocks (a totally ordered set of (m -2) A-elements) and labeled B-blocks (a totally ordered set of (m -3) A-elements followed by one B-element) ; 2. g -1 (0) contains exactly 1 A-element, followed by an A-block, one of these (m -1) A-elements being labeled with 1 ;

3. for every B-element x, the preimage g -1 (x) of x is organized as a totally ordered set of labeled A-blocks.

In the following figure, we represent such an endofunction by a directed graph where A-elements (resp. B-elements) are squares (resp. triangles). As for sketched stellar trees, we distinguish three types of edges in such endofunctions: we say that an edge (x, b) (b is a block in the preimage of x) is a 1-edge (resp. 2-edge ; 3-edge) if x is an A-element and b an A-block (resp. x is an A-element and b a B-block ; x is a B-element and b an A-block, or x is the element 0). We use the same convention for drawing edges as in the previous figure. andE m,n, f ,k the number of sketched m-stellar endofunctions over

(m ≥ 3, n ≥ 1, f ≥ 1, k ≥ 0),
[n, f ] having k 3-edges (m ≥ 3, n ≥ 1, f ≥ 0 and k ≥ 0). Then E m,n, f ,k = n! × f ! × T m,n, f ,k .
Proof. In the context of describing a bijective proof of a multivariable formal power series inversion formula (called the arborescent form of the Good-Lagrange formula), there is a one-to-one correspondence between some families of enriched endofunctions and enriched labeled trees (see [START_REF] Goulden | Multivariable Lagrange inversion, Gessel-Viennot cancellation, and the matrix tree theorem[END_REF]Theorem 2.1] or [6, Section 2]), which specializes to a one-to-one correspondence between sketched m-stellar endofunctions over [n, f ] and sketched m-stellar trees having n A-vertices, f B-vertices, such that the A-vertices are labeled over [n] and the B-vertices over [ f ], this correspondence conserving the number of 3-edges. The lemma follows from this result and from the fact that since a sketched m-stellar tree is a plane tree, the number of such labeled trees is n! × f ! × T m,n, f ,k . ✷ Lemma 4.3 Let m ≥ 3, n ≥ 1 and f > 1 be integers such that there exists p satisfying p = (n + f -1)/(m -2) and 1 ≤ f ≤ p. The number of sketched m-stellar endofunctions having n A-elements, f B-elements and k 3-edges is

(m -1) × (n -1)! × f ! × k + f -1 f -1 × p + n -k -2 n -1 × p -k -1 f .
Proof. First, it follows immediately from the definition of p that there are p blocks in our endofunctions, and f of them are B-blocks (there is exactly one B-element in a B-block and no B-element in the preimage of 0). We deduce from the fact that no B-block is in the preimage of a B-element and from the definition of 3-edges that 0 ≤ k ≤ (pf ). Now, we describe the enumeration of these sketched m-stellar endofunctions in three steps.

Step 1. First we consider the preimages of 0 and of the A-element labeled 1. From the definition of this preimage (point 2 of Definition 4.2), we deduce that 0 can have

(m -1)! n -1 m -2 different preimages.
Step 2. Next, we consider the repartition of the blocks in the preimages of the A-elements and B-elements.

We recall that there are (p -1f ) A-blocks and f B-blocks in the preimages of the A-elements and Belements of sketched endofunctions. Moreover, by fixing the number k of 3-edges, we know that there are exactly k A-blocks in the preimages of the B-elements, which implies that the (p -1k) other blocks are in the preimages of A-elements. Hence, we have

k + f -1 f -1
different repartitions of the k blocks in the preimages of the f B-elements, and

n + p -k -2 n -1 p -k -1 f
different repartitions of the (p -1k) blocks in the preimages of the n A-elements, f of these blocks being B-blocks.

Step 3. During the last step, we assign a label to every element in the blocks. There are (nm + 1)! × p! different assignments, which concludes the proof. ✷ Proof of Theorem 6. It follows from Lemmas 4.2 and 4.3 that the number of m-stellar trees having whose sketch tree has n A-vertices and f B-vertices is given by

1 n (m -2) f p-f ∑ k=0 (m -1) k+1 p -k -1 f p + n -k -2 n -1 k + f -1 f -1 . (10)
By the relationships of (m + 1)-stellar trees having a given vertex color distribution with sketched (m + 1)stellar trees (Lemma 4.1) and with m-constellations (Theorem 5) we obtain, by replacing m by m + 1 and f by f -1 in [START_REF] Bouya | Topological classification of complex polynomials: new experimental results[END_REF] and by dividing the resulting formula by f , the following formula for m-constellations having n vertices and f faces

1 n f (m -1) f -1 p-f +1 ∑ k=0 m k+1 p -k -1 f -1 p + n -k -2 n -1 k + f -1 f -2 . ( 11
)
Finally, it follows from Euler's formula [START_REF] Arquès | Relations fonctionnelles et dénombrement des hypercartes planaires pointées[END_REF], that an m-constellation with n vertices and f white faces has p = (n + f -2)/(m -1) polygons. Hence, it is sufficient to replace n by (m -1)pf + 2 in [START_REF] Chauve | Another enumeration of constellations[END_REF] to obtain [START_REF] Bousquet-Mélou | Enumeration of planar constellations[END_REF]. ✷

Remark 4.2

The formula for cacti (the case f = 1, Theorem 3) follows from the same arguments, if we notice that in this case the number of 3-edges should be 0.

Remark 4.3

As a byproduct of our combinatorial proof of Theorem 6, we can design a uniform random generation algorithm for m-constellations having p polygons and f white faces. This algorithm follows immediately from our proof of Theorem 6. We focus on the case f ≥ 2 (for m-cacti, a more efficient algorithm is presented in [START_REF] Bousquet | Enumération et génération aléatoire de cactus m-aires[END_REF]). The algorithm is the following.

1. let t := 0 and n := (m -1)pf + 2 2. for k from 0 to pf + 1 do

t k := m k+1 mp -f -k p -f -k k + f -2 f -

Constellations having a given white faces/color distribution

Here, we are interested in the enumeration of constellations given a white face/vertex color distributions. We give a system of Lagrangian functional equations for the multivariable generating function g(x 1 , . . . , x m+1 ) of constellations enumerated with respect to these constraints.

Proposition 3 Let C n 1 ,...,n m , f be the number of m-constellations having f white faces and n i vertices of color c i (i = 1, . . . , m). Then

C n 1 ,...,n m , f = 1 f [x n 1 1 • • • x n m m x f -1 m+1 ] m ∏ i=1 v i (x 1 , . . . , x m+1 ), (12)
where, for i = 1, . . . , m + 1,

v i (x 1 , . . . , x m+1 ) = x i 1 -∑ ( j∈[m+1], j =i) ∏ (k∈[m+1], k =i, j) v k (x 1 , . . . , x m+1 ) . (13)
Proof. This result follows immediately from the definition of (m + 1)-stellar trees, Theorem 5, and classical results relating colored trees and multivariable formal power series (see [2, Chapter 3] for example). ✷ Remark 4. [START_REF] Bousquet | Théorie des espèces et applications au dénombrement de cartes et de cactus planaires[END_REF] The system [START_REF] Cori | Maps, hypermaps and their automorphisms: a survey[END_REF], that expresses the "Lagrangian" nature of constellations and the correspondence between constellations with a distinguished white face and stellar trees, follows from ( 6) by the formal substitution v i (x 1 , . . . , x m+1 ) = x i + ∑ ( j∈[m+1], j =i) u j (x 1 , . . . , x m+1 ) and an easy computation [START_REF] Schaeffer | [END_REF], but we obtained it by purely combinatorial arguments.

Bipartite planar maps.

To conclude this section, we derive (from Theorem 5 and Theorem 6) some results on bipartite and bi-Eulerian planar maps. As we consider here only planar maps, from now we will mostly use the terms bipartite and bi-Eulerian maps.

Bipartite maps. First, we notice (following [START_REF] Schaeffer | Conjugaison d'arbres et cartes combinatoires aléatoires[END_REF]) that in a bipartite map, with every A-vertex (resp. B-vertex) replaced with a vertex colored with c 1 (resp. c 2 ), and every edge by a 2-gon, one obtains a 2constellation. This construction induces a bijection between bipartite maps having n 1 (resp. n 2 ) A-vertices (resp. B-vertices) and f faces and 2-constellations having n 1 (resp. n 2 ) vertices colored with c 1 (resp. with c 2 ) and f white faces. As in the above construction edges of bipartite maps are in correspondence with polygons, we can deduce from Theorem 6 a formula for bipartite maps having p edges and f faces.

Theorem 7 The number of bipartite planar maps having p edges and f faces

( f > 1) is 1 2 f -1 f (p -f + 2) p f -1 p-f +1 ∑ k=0 2 k+ f 2p -f -k p -f -k k + f -2 f -2 (14)
Proof. This result is obtained by plugging m = 2 into (9). ✷ Remark 4.5 In [START_REF] Walsh | Hypermaps versus bipartite maps[END_REF], Walsh gave the following formula for the number of bipartite maps having p edges and f faces (see also [START_REF] Arquès | Relations fonctionnelles et dénombrement des hypercartes planaires pointées[END_REF]).

2 (p -1)! ( f -1)!(p -f + 2)! p-f ∑ k=0 2p p -f -k k + f f .
This formula, different from ( 14), follows easily from the case m = 2 of formula (4).

Moreover, we can immediately deduce from Proposition 3, the following result dealing with the enumeration of bipartite maps according to the number of faces and of vertices of every type (Arques gives related results in [START_REF] Arquès | Relations fonctionnelles et dénombrement des hypercartes planaires pointées[END_REF], but they are obtained in a very different way).

Proposition 4 Let Bip n 1 ,n 2 , f be the number of bipartite planar maps having n 1 A-vertices, n 2 B-vertices and f faces. Then

Bip n 1 ,n 2 , f = 1 f [x n 1 1 x n 2 2 x f -1 3 ]v 1 × v 2 , (15)
where v 1 and v 2 are formal power series in (x 1 , x 2 , x 3 ) defined by the system

v 1 = x 1 1 -v 2 -v 3 ( 16
)
v 2 = x 2 1 -v 1 -v 3 ( 17
)
v 3 = x 3 1 -v 1 -v 2 (18) (19)
Bi-Eulerian maps. A bi-Eulerian map is a bipartite maps where all the vertices have an even degree. It follows from this definition that this family of maps is stable by duality (the dual map of a bi-Eulerian map is a bi-Eulerian map), which implies that the faces of such maps can be in two sets (say A-faces and B-faces) in such a way that two faces incident to a given edge do not belong to the same set, and, when following the root-edge from its A-vertex to its B-vertex, one has to the left an A-face. To avoid confusion, we do not use squares and triangles to represent A-vertices and B-vertices of bi-Eulerian maps. This family of maps has been recently studied by Liskovets and Walsh [START_REF] Liskovets | Enumeration of unicursal maps[END_REF], and by Poulalhon and Schaeffer [START_REF] Poulalhon | Problèmes énumératifs autour des cartes combinatoires et des factorisations dans le groupe symétrique[END_REF][START_REF] Poulalhon | A note on bipartite eulerian planar maps[END_REF], who described a one-to-one correspondence between bi-Eulerian maps and regular 4-Eulerian maps. For the sake of completeness, we describe here their construction, which relies on the following property: the edge map of a bi-Eulerian map is a regular 4-Eulerian map. More precisely, in order to obtain the regular 4-Eulerian map E corresponding to a bi-Eulerian map B:

A-vertices B-vertices A-faces B-faces

1. put a vertex on every edge of B in such a way that the vertex r on the root-edge is an A-vertex and that the vertices on two edges successively incident to a same vertex are an A-vertex and a B-vertex ;

2. add an edge between two of these new vertices if and only if they are on edges of B that are successively incident to a same vertex of B ;

3. remove the edges and vertices of B and root the map so obtained in the edge incident to r and to the counterclockwise successive edge of B.

The maps E so obtained is a regular 4-Eulerian map where faces of color c 1 (resp. This construction, together with the relationship between regular 4-Eulerian maps and 3-constellations, and Proposition 3, implies immediately the following result.

Proposition 5 Let BipEul n 1 ,n 2 , f 1 , f 2 be the number of bi-Eulerian planar maps having n 1 A-vertices, n 2 B-vertices f 1 A-faces and f 2 B-faces. Then

BipEul n 1 ,n 2 , f 1 , f 2 = 1 n 2 [x f 1 1 x n 1 2 x f 2 3 x n 2 -1 4 ]v 1 × v 2 × v 3 , (20)
where v 1 , v 2 and v 3 are formal power series in (x 1 , x 2 , x 3 , x 4 ) defined by the system

v 1 = x 1 1 -v 2 v 3 -v 2 v 4 -v 3 v 4 ( 21
)
v 2 = x 2 1 -v 1 v 3 -v 1 v 4 -v 3 v 4 ( 22
)
v 3 = x 3 1 -v 1 v 2 -v 1 v 4 -v 2 v 4 ( 23
)
v 4 = x 4 1 -v 1 v 2 -v 1 v 3 -v 2 v 3 (24)
We give in Tables 1 and2 the first values for Bip n 1 ,n 2 , f and BipEul n 1 ,n 2 , f 1 , f 2 , computed using Maple and the Good-Lagrange formula.

(n 1 , n 2 ) f = 1 f = 2 f = 3 f = 4 f = 5 f = 6 f = 7 (1,1) 1 1 1 1 1 1 1 (2,

Conclusion and questions

In this paper, we derive from the results of Bousquet-Mélou and Schaeffer, relating constellations and Eulerian trees, a new correspondence between constellations and a family of Lagrangian trees, the stellar trees. This gives a complete characterization of constellations as Lagrangian objects, and enumerative results about constellations and bipartite planar maps. One of the main interests in characterizing the Lagrangian nature of constellations is that it allows the application of all the combinatorial and algorithmic theory related to the Good-Lagrange formula. We did it, for instance, in the proof of Theorem 6, by reducing our problem of enumerating sketched stellar trees to the problem of enumerating sketched stellar endofunctions, and we had, as a bonus result, a random generation algorithm.

As we remarked in the introduction, our main result (Theorem 5) generalizes some well known results for constellations with one white face, that is cacti. But if we focus on our construction relating constellations and stellar trees, we can remark that it is much more complicated than the construction relating cacti and cacti-trees and in general the m-cacti tree associated to a m-cacti by our construction is different from the classical coding of cacti by cacti trees. It is then natural to ask for a construction relating constellations and stellar trees that, in the case of cacti, reduces to this coding. A solution to this problem would be interesting, especially if we are interested in factorizations of permutations. Indeed, in this problem, the number (and degrees) of the white faces and of the vertices of every color in constellations are very important [START_REF] Bousquet-Mélou | Enumeration of planar constellations[END_REF]. If, for cacti, these parameter are immediately readable on cacti trees (which allows to enumerate cacti having a given degree distribution [START_REF] Goulden | The combinatorial relationship between trees, cacti and certain connection coefficients for the symmetric group[END_REF][START_REF] Bóna | Enumeration of m-ary cacti[END_REF][START_REF] Bousquet | Enumération et génération aléatoire de cactus m-aires[END_REF]), this is not the case for stellar trees. It would be interesting to follow such parameters from constellations to stellar trees.

Fig. 2 :

 2 Fig. 2: A 3-cacti tree and the corresponding 3-cactus

color c 4 color c 1 color c 3 color c 2

 132

Fig. 4 :

 4 Fig. 4: A 3-constellation and the corresponding regular 4-constellation

c 2 Fig. 5 :

 25 Fig. 5:A regular 4-constellation and its dual map, a regular 4-Eulerian map: the circle associated with a face of the Eulerian map represents its color and the dashed edge is the root-edge.

Fig. 7 :

 7 Fig. 7: Matching of an unbalanced regular 4-Eulerian tree

Fig. 8 :c 1 color c 2 color c 3 color c 4 Fig. 9 :

 849 Fig. 8: A balanced regular 4-Eulerian tree, after the matching procedure and adding the star, and the corresponding regular 4-Eulerian map

c 1 color c 2 color c 3 color c 4 Fig. 10 :

 410 Fig. 10: Replanting a regular 4-Eulerian tree

3 . 4

 34 c i = c m . ✷ Lemma Let n 1 , . . . , n m be m positive integers, a n 1 ,...,n m (resp. b n 1 ,...,n m ) the number of regular m-Eulerian trees (resp. balanced regular m-Eulerian trees) having n i A-leaves colored with c i (i ∈ [m]). Then a n 1 ,...,n m = n m × b n 1 ,...,n m .

color c 1 color c 2 color c 3 color c 4

 4 ←→

Definition 4 . 1

 41 Let m ≥ 3. A sketched m-stellar tree is a plane tree such that • the vertices are of two types (A-vertices and B-vertices) and the root is an A-vertex ;

Fig. 11 :

 11 Fig. 11: A sketched 4-stellar tree cb-const-enum-squelette

Definition 4 . 2

 42 Let m ≥ 3. A sketched m-stellar endofunction over [n, p] is a function g from a set of n A-elements labelled by [n] and p B-elements labelled by [p] (this set is denoted by [n, p]) to {0} ∪ [n, p]

Fig. 12 :

 12 Fig.12:A sketched 4-stellar endofunction over[START_REF] Cori | Maps, hypermaps and their automorphisms: a survey[END_REF][START_REF] Bergeron | Combinatorial species and tree-like structures, volume 67 of Encyclopedia of mathematics and its applications[END_REF]

2 and t := t + t k 3 .

 3 generation of an integer k (0 ≤ k ≤ (pf + 1)) with probability t k /t ; 4. generation of a sketched (m + 1)-stellar endofunction g over [n, f -1] having k 3-edges (3 steps): -generation of the preimage g -1 (0) (following step 1 of the proof of Lemma 4.3, this task reduces to choosing randomly m -2 elements among the n -1 A-elements and computing a random permutation on these m -1 A-elements) ; -generation of a random repartition of the blocks (following step 2 of the proof of Lemma 4.3, this task reduces to choosing randomly pk -1 elements among n + pk -2 and f B-blocks among the pk -1 blocks) ; -generation of a random assignment of the labels (following step 2 of the proof of Lemma 4.3, this task reduces the random generation of two permutations) ; 5. transformation of g into a sketched (m + 1)-stellar tree S (see [18, 6]) ; 6. random coloring of S to obtain an (m + 1)-stellar tree A (proof of Lemma 4.1) ; 7. transformation of A into a regular (m + 1)-Eulerian tree B (proof of Lemma 3.5) ; 8. coloring B into a balanced regular (m + 1)-Eulerian tree B ′ (proof of Lemma 4.1) ; 9. transformation of B ′ into a regular (m + 1)-Eulerian map E (by the matching procedure) ; 10. transformation of E into a regular (m + 1)-constellation C ′ (by duality) ; 11. transformation of C ′ into an m-constellation C (proof of Lemma 2.1) ;

color c 1 color c 2 Fig. 13 :

 213 Fig. 13: A 2-constellation and the corresponding bipartite map

Fig. 14 :

 14 Fig. 14: A bi-Eulerian map

c 2 ,Fig. 15 :

 215 Fig. 15: (a) A bi-Eulerian map (b) Adding new vertices and edges (c) The corresponding regular 4-Eulerian map

Theorem 4

 4 Let m, p and n 1 , n 2 , . . . , n m be integers such that m ≥ 2, 1 ≤ n i ≤ p for i = 1, . . . , m and

§ We recall that a preorder traversal of a rooted tree T reads first the root r of T , then visits recursively the subtrees of T rooted in the children of r, these children being visited from left to right.

Acknowledgements

We thank Gilles Schaeffer who indicated us the problem and its relationship to the Good-Lagrange formula, Dominique Poulalhon, for providing us with reference [22], Mireille Bousquet-Mélou and Sacha Zvonkin for fruitful discussions about constellations and Marni Mishna for advice improving the text.


Peter Paule
email: peter.paule@risc.uni-linz.ac.at

Helmut Prodinger
email: helmut@maths.wits.ac.za

Fountains, histograms, and q-identities

Keywords: q-identities, fountains, histograms, Schur polynomials

We solve the recursion S n = S n-1 -q n S n-p , both, explicitly, and in the limit for n → ∞, proving in this way a formula due to Merlini and Sprugnoli. It is also discussed how computer algebra could be applied.

Fountains and histograms

Merlini and Sprugnoli [START_REF] Merlini | Fountains and histograms[END_REF] discuss fountains and histograms; for the reader's convenience, we review a few key issues here.

A fountain with n coins is an arrangement of n coins in rows such that each coin in a higher row touches exactly two coins in the next lower row.

A p-histogram is a sequence of columns in which the height of the ( j + 1)st column is at most k + p, if k is the height of column j; the first column has height r, with 1 ≤ r ≤ p.

It can be shown that the enumeration of coins in a fountain is equivalent with the enumeration of 1-histograms. The paper [START_REF] Merlini | Fountains and histograms[END_REF] addresses the enumeration of p-histograms with respect to area (=number of cells). Let f

[p]
n be the number p-histograms with area n and F [p] (q) the corresponding generating function

F [p] (q) = ∑ n f [p]
n q n . The authors of [START_REF] Merlini | Fountains and histograms[END_REF] use two different approaches: one produces the answer in the form with some polynomials D m , E m defined in the next section, and the other gives it as

F [p] (q) = lim m→∞ D m E m , †
F [p] (q) = ∑ k≥0 (-1) k q p( k+1 2 ) (1 -q) . . . (1 -q k ) ∑ k≥0 (-1) k q k+p( k 2 ) (1 -q) . . . (1 -q k )
.

According to [5], it would be nice to have a direct argument that these two answers coincide. This is the subject of the present note.

Generalized Schur polynomials

The polynomials mentioned in the introduction are for fixed p ≥ 1 defined as follows:

E n = E n-1 -q n E n-p , n ≥ p, E 0 = • • • = E p-1 = 1, D n = D n-1 -q n D n-p , n ≥ p, D i = 1 - i ∑ j=1 q j , i = 0, . . . , p -1.
They can be compared with the classical Schur polynomials [START_REF] Schur | Ein Beitrag zur additiven Zahlentheorie und zur Theorie der Kettenbrüche[END_REF], which occur for p = 2 and q = -1. Then Merlini and Sprugnoli want a direct proof of the formulae

E ∞ := lim n→∞ E n = ∑ k≥0 (-1) k q p( k+1 2 ) (1 -q) . . . (1 -q k ) , D ∞ := lim n→∞ D n = ∑ k≥0 (-1) k q k+p( k 2 ) (1 -q) . . . (1 -q k ) .
We will not only achieve that but actually derive explicit expressions for these polynomials! It should be mentioned that Cigler [START_REF] Cigler | Some algebraic aspects of Morse code sequences[END_REF] developed independently a combinatorial method to deal with recursions as ours, but also more general ones.

Let us study the generic recursion

S n = S n-1 + tq n-p S n-p ,
with unspecified initial values S 0 , . . . , S p-1 . For p = 2, these polynomials were studied by Andrews (and others) in the context of Schur polynomials, see [START_REF] Andrews | Fibonacci numbers and Rogers-Ramanujan identities[END_REF].

We will use standard notation from q-calculus, see [START_REF] Andrews | Special functions[END_REF]:

(x) n = (1 -x)(1 -xq) . . . (1 -xq n-1 ), n k = (q) n (q) k (q) n-k .
It will be convenient to define n k = 0 for n < 0 or k > n. Now we will proceed as in [START_REF] Andrews | Special functions[END_REF] and consider noncommutative variables x, η, such that xη = qηx; all other variables commute. Lemma 1.

x + x p η n = n ∑ k=0 n k q p( n 2 )-pnk+p( k+1 2 ) x k+p(n-k) η n-k .
Proof. We write

x + x p η n = n ∑ k=0 a n,k x k+p(n-k) η n-k ,
and x + x p η n+1 = x + x p η n x + x p η resp. as x + x p η n+1 = x + x p η x + x p η n , compare coefficients, and get the recursions

a n+1,k = a n,k-1 + a n,k q k+p(n-k) , a n+1,k = a n,k-1 q n+1-k + a n,k q p(n-k) .
From this we derive, taking differences,

a n,k = 1 -q n+1-k 1 -q k q -p(n-k) a n,k-1 .
The result follows from iteration by noting that a n,0 = q p( n 2 ) . Of course we also have

x + tx p η n = n ∑ k=0 n k q p( n 2 )-pnk+p( k+1 2 ) x k+p(n-k) t n-k η n-k .
Now we derive the generating function for

F(x) = ∑ n≥0 S n x n ;
the following procedure is inspired by [START_REF] Andrews | Fibonacci numbers and Rogers-Ramanujan identities[END_REF]. Note that we can alternatively view η as an operator, defined by η f (x) = f (qx). Cigler worked also much with this technique [START_REF] Cigler | Elementare q-Identitäten[END_REF][START_REF] Cigler | Some algebraic aspects of Morse code sequences[END_REF]. We find

∑ n≥p S n x n = ∑ n≥p S n-1 x n + ∑ n≥p tq n-p S n-p x n = x ∑ n≥p-1 S n x n + tx p ∑ n≥0 ηS n x n or F(x) -∑ n<p S n x n = xF(x) -x ∑ n<p-1 S n x n + tx p ηF(x), and
F(x) = 1 1 -x -tx p η ∑ i<p S i x i -∑ i<p-1 S i x i+1 .
Now we can apply our lemma and write

F(x) = ∑ n≥0 x + tx p η n ∑ i<p S i x i -∑ i<p-1 S i x i+1 = ∑ n≥0 n ∑ k=0 n k q p( n 2 )-pnk+p( k+1 2 ) x k+p(n-k) t n-k η n-k ∑ i<p S i x i -∑ i<p-1 S i x i+1 = ∑ n≥0 n ∑ k=0 n k q p( n 2 )-pnk+p( k+1 2 ) x k+p(n-k) t n-k ∑ i<p S i q i(n-k) x i -∑ i<p-1 S i q (i+1)(n-k) x i+1 = ∑ n≥0 n ∑ k=0 n k q p( k 2 ) x n-k+pk t k ∑ i<p S i q ik x i -∑ i<p-1 S i q (i+1)k x i+1 = ∑ k,n≥0 n + k k q p( k 2 ) x n+pk t k ∑ i<p S i q ik x i -∑ i<p-1 S i q (i+1)k x i+1 = ∑ k≥0 q p( k 2 ) x pk t k 1 (x) k+1 ∑ i<p S i q ik x i -∑ i<p-1 S i q (i+1)k x i+1 .
From this we find an explicit formula for S n (the quantity S -1 has to be interpreted as 0):

S n = ∑ 0≤i<p (S i -S i-1 ) ∑ k≥0 n -(p -1)k -i k q p( k 2 )+ik t k .
Now we specialize this to our instance. Here, t = -q p , and thus

S n = ∑ 0≤i<p (S i -S i-1 ) ∑ k≥0 n -(p -1)k -i k q p( k+1 2 )+ik (-1) k . Therefore E n = ∑ k≥0 n -(p -1)k k q p( k+1 2 ) (-1) k .
From this, the limit of E n is immediate. For D n we eventually get the following form

D n = ∑ k≥0 n -(p -1)(k -1) k q k+p( k 2 ) (-1) k ,
from which the formula for D ∞ is immediate. To prove it, we need a simple lemma whose proof is just a routine calculation. Lemma 2.

m -i k q i(k+1) = g(i) -g(i -1) where g(i) = - m -i k + 1 q (i+1)(k+1) .
Now we can plug into the general formula above and compute

D n = E n - p-1 ∑ i=1 ∑ k≥0 n -(p -1)k -i k q p( k+1 2 )+i(k+1) (-1) k = E n -∑ k≥0 (-1) k q p( k+1 2 ) p-1 ∑ i=1 n -(p -1)k -i k q i(k+1) = E n -∑ k≥0 (-1) k q p( k+1 2 ) q k+1 n -(p -1)k k + 1 -q p(k+1) n -(p -1)(k + 1) k + 1 = 1 -∑ k≥0 (-1) k q p( k+1 2 ) q k+1 n -(p -1)k k + 1 ,
which is the announced formula after a simple change of variable. Note that in the penultimate step the telescoping property of the lemma has been used.

  Partially supported by SFB grant F1305 of the Austrian FWF. ‡ The research was started when this author visited the RISC in 2002. Partially supported by NRF grant 2053748. 1365-8050 c 2003 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France

Computer algebra proofs

The polynomial families (E n ) and (D n ) give rise to the following study with respect to possible computer proofs. Let us take as input our sum representations of E n and D n :

Then, if p is chosen as a specific positive integer, Riese's package qZeil [START_REF] Paule | A Mathematica q-analogue of Zeilberger's algorithm based on an algebraically motivated approach to q-hypergeometric telescoping, Special functions, q-series and related topics[END_REF] returns the recurrences S n = S n-1 -q n S n-p (n ≥ p) together with a certificate function Cert for independent verification. Despite the fact that for general "generic" integer parameter p there is no algorithm available, a general pattern can be easily guessed from running the algorithm for p = 1, p = 2, and p = 3, say. For example, let F(n, k) be the kth summand in our sum representation (3.1) of E n , then the recurrence for E n can be refined to the following statement.

Theorem 3.1. For n ≥ p and δ

where

Proof. After dividing both sides of (3.2) by F(n, k) the proof reduces to checking equality of rational functions. Namely, note that

Analogously, there is a refined version of the recurrence for D n . The certificate in this case is

Summarizing, with the sum representation for E n and D n in hand, the corresponding recurrences follow immediately by summing both sides of the computer recurrences (3.2) over all k ≥ 0.