# Constellations and multicontinued fractions: application to Eulerian triangulations

Marie Albenque<fnref n="1" /> and Jérémie Bouttier²³

**Abstract.** We consider the problem of enumerating planar constellations with two points at a prescribed distance. Our approach relies on a combinatorial correspondence between this family of constellations and the simpler family of rooted constellations, which we may formulate algebraically in terms of multicontinued fractions and generalized Hankel determinants. As an application, we provide a combinatorial derivation of the generating function of Eulerian triangulations with two points at a prescribed distance.

**Résumé.** Nous considérons le problème du comptage des constellations planaires à deux points marqués à distance donnée. Notre approche repose sur une correspondance combinatoire entre cette famille de constellations et celle, plus simple, des constellations enracinées. La correspondance peut être reformulée algébriquement en termes de fractions multicontinues et de déterminants de Hankel généralisés. Comme application, nous obtenons par une preuve combinatoire la série génératrice des triangulations eulériennes à deux points marqués à distance donnée.

**Keywords:** Constellations, planar maps, Eulerian triangulations, continued fractions, lattice paths

## 1 Introduction

From the initial work of Hurwitz (1891) about transitive ordered factorizations of the identity in the symmetric group, to the bijective approach of Bousquet-Mélou and Schaeffer (2000) and Bouttier et al. (2004), including the more algebraic approach of Goulden and Jackson (1997), constellations appear in many forms in different areas of combinatorics. We refer the reader to the book of Lando and Zvonkin (2004) for an extensive review of the variety of contexts in which constellations appear.

We here focus on the map point of view, and consider the problem of enumerating planar constellations with two points at a prescribed distance. This problem is originally motivated by the seminal work of Chassaing and Schaeffer (2004) where the distribution of distances to the root vertex in a random quadrangulation was investigated via a correspondence with so-called well-labeled trees. Determining the law of the first moment of this distribution amounts to counting planar quadrangulations with two points at a prescribed distance, a question which was first addressed by Bouttier et al. (2003a) (in a slightly different “dual” picture): the associated generating function was found to obey a recurrence equation which, remarkably, admits an explicit solution, see also Bouttier et al. (2003b). This recurrence equation was generalized to the case of bipartite maps (2-constellations) with controlled face degrees, and a general

<footnote n="1">¹CNRS, LIX, École Polytechnique, 91128 Palaiseau Cedex, France</footnote>

<footnote n="2">²Institut de Physique Théorique, CEA, IPhT, F-91191 Gif-sur-Yvette Cedex, France, CNRS URA 2306</footnote>

<footnote n="3">³LIAFA, Université Paris Diderot - Paris 7, case 7014, 75205 Paris Cedex 13, France, CNRS UMR 7089</footnote>
form for its solution was conjectured, hinting at a mysterious integrability property (Bouttier et al., 2003a, Section 5). Di Francesco (2005) further extended this approach to general constellations. Recently, Bouttier and Guitter (2011) proved the validity of the solution in the case of bipartite maps by a different approach relying on the combinatorial theory of continued fractions of Flajolet (1980). The purpose of our work is to generalize this new approach to constellations, with the intent of proving Di Francesco's formulas and of shedding light on this "combinatorial integrability".

The present paper makes a first step in this direction. We exhibit a connection between our enumeration problem and the *a priori* simpler problem of counting rooted constellations. This connection relies on a decomposition involving some lattice paths, which we may rephrase in terms of multicontinued fractions. Solving our enumeration problem amounts to finding unknown coefficients in such a multicontinued fraction, which can be done via a generalization of Hankel determinants. We illustrate this approach in the case of Eulerian triangulations, where we provide the first combinatorial derivation of a formula found in Bouttier et al. (2003b) for the generating function of Eulerian triangulations with two points at prescribed distance. These objects are in bijection with "very-well-labeled trees with small labels", see also (Bousquet-Mélou, 2006, Section 2.1). The next section presents in more detail our main results and the organization of the paper.

## 2 Definitions and main results

A *planar map* is a proper embedding of a connected graph into the sphere, where proper means that edges are smooth simple arcs which meet only at their endpoints. Two planar maps are identical if one of them can be mapped onto the other by a homeomorphism of the sphere preserving the orientation. A planar map is made of *vertices*, *edges* and *faces*. The *degree* of a vertex or face is the number of edges incident to it (counted with multiplicity). Following Bousquet-Mélou and Schaeffer (2000), we consider a particular class of planar maps called *constellations*, see Fig.1.

**Definition 1** For $p \in [2, \infty]$, a $(p-)$constellation is a planar map whose faces are colored black or white in such a way that:

* adjacent faces have opposite colors,

* the degree of any black face is $p$,

* the degree of any white face is a multiple of $p$.

Each edge of a constellation receives a canonical orientation by requiring that the white face is on its right. It is easily seen that the length of each oriented cycle is a multiple of $p$, and that any two vertices are accessible from one another. A constellation is *rooted* if one of its edges is distinguished. The *white root face* and *black root face* are respectively the white and black faces incident to the root edge. The *root degree* is the degree of the white root face. A constellation is said to be *pointed* if it has a distinguished vertex. Note that, in a pointed rooted constellation, the pointed vertex is not necessarily incident to the root edge.

In this paper, we consider $p$-constellations subject to a control on white face degrees, i.e. for each positive integer $k$ we fix the number of white faces of degree $kp$. This amounts to considering multivariate generating functions of constellations depending on an infinite sequence of variables $(x_k)_{k \ge 1}$, where $x_k$ is the weight per white face of degree $kp$ and the global weight of a constellation is the product of the weights of its white faces. Two families of constellation generating functions will be of interest here.
<figure><img src="image_1.png" /><figcaption>**Fig. 1:** (a) A rooted 4-constellation with root degree 8 and weight $x_1^2 x_2^2 x_4$, contributing to $F_2$ (note that vertex types around the root face form a 4-excursion). (b) A pointed rooted 4-constellation of type $3 \to 2$, with weight $x_1^3 x_2$, contributing to all $V_i$ with $i \ge 3$.</figcaption></figure>

The first family is that of rooted constellations with a prescribed root degree. More precisely, for $n \ge 1$, let $F_n \equiv F_n(x_1, x_2, \dots)$ denote the generating function of rooted $p$-constellations with root degree $np$. By convention, we do not attach a weight $x_n$ to the white foot face and we set $F_0 = 1$.

The second family is that of pointed rooted constellations with a bounded “distance” between the root edge and the pointed vertex. More precisely, in a pointed constellation, we say that a vertex $v$ is of type $j \in \mathbb{N}$ if $j$ is the minimal length of an oriented path from $v$ to the pointed vertex (due to the orientation, it is slightly inappropriate to think of $j$ as distance) and we say that an edge is of type $j \to j'$ if its origin and endpoint are respectively of type $j$ and $j'$. Then, for $i \ge 1$, let $V_i \equiv V_i(x_1, x_2, \dots)$ denote the generating function of pointed rooted $p$-constellations where the root edge is of type $j \to j-1$ with $j \le i$ (see Fig. 1). Note that $V_1$ is the generating function for rooted constellations (since for $i=1$, the pointed vertex must be the endpoint of the root edge). Furthermore, we add a conventional term 1 to $V_i$, for all $i \ge 1$.

The fundamental observation of this paper may be stated as:

**Theorem 1** The sequences $(F_n)_{n \ge 0}$ and $(V_i)_{i \ge 1}$ are related via the multicontinued fraction expansion

$$ \sum_{n \ge 0} F_n t^n = \frac{1}{1 - t \prod_{i_1=1}^{p-1} \frac{V_{i_1}}{1 - t \prod_{i_2=1}^{p-1} \frac{V_{i_1+i_2}}{1 - t \prod_{i_3=1}^{p-1} \frac{V_{i_1+i_2+i_3}}{\ddots}}}} \quad (1) $$

In the case $p=2$, the r.h.s. of (1) reduces to an ordinary continued fraction (of Stieljes-type). This corresponds to the bipartite case discussed in (Bouttier and Guitter, 2011, Eq. (1.13)): indeed, 2-constellations may be identified with bipartite planar maps upon “collapsing” the bivalent black faces into non-oriented edges.

In the spirit of the combinatorial theory of continued fractions initiated by Flajolet (1980), an alternate formulation of Theorem 1 may be given in terms of some lattice paths. We call $p$-path a lattice path on $\mathbb{Z} \times \mathbb{N}$ made of two types of steps: rises $(1, p-1)$ and falls $(1, -1)$. Note that a $p$-path starting from $(i_0, j_0)$ only visits vertices $(i, j)$ with $i + j \equiv i_0 + j_0 \pmod p$. A $p$-excursion of length $np$ is a $p$-path that starts
at (0, 0) and ends at (np, 0). It is well-known that such p-excursions are in one-to-one correspondence with p-ary rooted plane trees with n nodes, in number $\frac{1}{np+1} \binom{np+1}{n}$. To each fall in a p-path, we attach a weight $V_i$ where i is the starting height of the fall (i.e. the fall starts from (j, i) for some j, and thus ends at (j + 1, i - 1)). We define the weight of a p-path as the product of the weights of its falls. As discussed in Section 3, the alternate formulation of Theorem 1 is then:

**Theorem 2** For all $n \ge 0$, $F_n$ is equal to the sum of weights of all p-excursions of length np.

We prove this theorem in Section 4. As an illustration, for $p = 3$ and $n = 1, 2, 3$, the equality reads

$$ 
\begin{align} 
F_1 &= V_1 V_2 \nonumber \\ 
F_2 &= V_1 V_2 (V_1 V_2 + V_2 V_3 + V_3 V_4) \nonumber \\ 
F_3 &= V_1 V_2 (V_1^2 V_2^2 + 2 V_1 V_2^2 V_3 + V_2^2 V_3^2 + 2 V_1 V_2 V_3 V_4 + 2 V_2 V_3^2 V_4 + \nonumber \\ 
& \qquad V_3^2 V_4^2 + V_2 V_3 V_4 V_5 + V_3 V_4^2 V_5 + V_3 V_4 V_5 V_6) \tag{2} 
\end{align} 
$$

We are now interested in inverting the relation (1), i.e. expressing $V_i$ in terms of the $F_n$'s. For $p = 2$, this may be done using Hankel determinants (see below). However, as soon as $p \ge 3$, it is not difficult to see that knowing the sequence $(F_n)_{n \ge 0}$ alone is not sufficient (for instance in (2) it appears that we have “twice as many unknowns as equations”).

We thus need some extra knowledge. A possible way is to consider, for all $n \ge 0$ and $r \ge 0$, the sum of weights of all p-paths that start at $(-r, r)$ and end at $(np, 0)$, which we denote by $F_n^{(r)}$. Note that $F_n^{(0)} = F_n$ and, since a p-excursion necessarily starts with a rise, $F_n^{(p-1)} = F_{n+1}$. From now on, we restrict the values of $r$ to the interval $[0, p-2]$. As will be discussed in Section 4, those $F_n^{(r)}$ have a natural interpretation in terms of constellations. Let us write down the first few $F_n^{(1)}$ for $p = 3$:

$$ 
\begin{align} 
F_0^{(1)} &= V_1 \nonumber \\ 
F_1^{(1)} &= V_1 V_2 (V_1 + V_3) \nonumber \\ 
F_2^{(1)} &= V_1 V_2 (V_1^2 V_2 + 2 V_1 V_2 V_3 + V_2 V_3^2 + V_1 V_3 V_4 + V_3^2 V_4 + V_3 V_4 V_5) \tag{3} 
\end{align} 
$$

It appears that, interlacing the equations in (3) and (2), we obtain a triangular system of equations for $V_1, \dots, V_6$. This fact turns out to be general and, furthermore, the solution to our inverse problem is provided by the following formula, which we derive combinatorially in Section 3.

**Theorem 3** For $m \in [0, p-1]$ and $n \in \mathbb{N}$, we have the determinantal identity

$$ H_{m;n} := \det_{0 \le i,j \le n} F_{q_{i+m}+j}^{(r_{i+m})} = \prod_{i=0}^{n} \prod_{j=1}^{ip+m} V_j \qquad (4) $$

where, for $k \in \mathbb{N}$, $q_k$ and $r_k$ denote respectively the quotient and the remainder in the Euclidean division of k by $p-1$, namely $q_k = \lfloor \frac{k}{p-1} \rfloor$ and $r_k = k - (p-1)q_k$.

**Corollary 4** Let $m \in [0, p-1]$, $n \in \mathbb{N}$, and set by convention $H_{m;-1} = 1$. We have

$$ V_{pn+m} = \begin{cases} \frac{H_{m;n} H_{m-1;n-1}}{H_{m;n-1} H_{m-1;n}} & \text{if } m \ge 1 \\ \frac{H_{0;n} H_{p-1;n-2}}{H_{0;n-1} H_{p-1;n-1}} & \text{if } m = 0 \text{ and } n \ge 1. \end{cases} \qquad (5) $$
Note that, for $p = 2$, we recover the Hankel determinants: $H_{m;n} = \det_{0 \le i,j \le n} F_{i+j+m}$ with $m = 0$ or $1$. For $p = 3$, the first few determinants read

$$ 
\begin{array}{l@{\qquad}l@{\qquad}l}
H_{0;0} = F_0^{(0)} = 1 & H_{1;0} = F_0^{(1)} & H_{2;0} = F_2^{(0)} \\
H_{0;1} = \begin{vmatrix} F_0^{(0)} & F_1^{(0)} \\ F_0^{(1)} & F_1^{(1)} \end{vmatrix} & H_{1;1} = \begin{vmatrix} F_0^{(1)} & F_1^{(1)} \\ F_1^{(0)} & F_2^{(0)} \end{vmatrix} & H_{2;1} = \begin{vmatrix} F_1^{(0)} & F_2^{(0)} \\ F_1^{(1)} & F_2^{(1)} \end{vmatrix} & (6) \\
H_{0;2} = \begin{vmatrix} F_0^{(0)} & F_1^{(0)} & F_2^{(0)} \\ F_0^{(1)} & F_1^{(1)} & F_2^{(1)} \\ F_1^{(0)} & F_2^{(0)} & F_3^{(0)} \end{vmatrix} & & &
\end{array}
$$

and the reader may check, using (2) and (3), that those determinants are indeed monomials in the $V_i$'s, in agreement with (4). We conjecture that, up to a simple normalization factor, $H_{m;n}$ coincides with $u_{(n+1)p+m}^{(p-2)}$ as defined at Equation (6.31) in Di Francesco (2005), so that Equation (6.30) ibid. amounts to Corollary 4.

In this paper, we present a simple application of Theorem 3 to the case of *Eulerian triangulations*, namely 3-constellations where all the white faces are also triangular. This corresponds to specializing the generating functions defined above at the values $p = 3$, $x_1 = x$, $x_k = 0$ for $k \ge 2$, where $x$ is a variable controlling the number of triangles. In this case, the sequence $(V_i)_{i \ge 1}$ is known to satisfy the simple recurrence

$$ V_i = 1 + xV_i (V_{i-1} + V_{i+1}), \quad i \ge 1, V_0 = 0, \quad (7) $$

see Bouttier et al. (2003b). Clearly, this equation fully determines $V_i$ as a power series in $x$. In the same reference, it was observed that the solution of this equation has a remarkably simple form

$$ V_i = V \frac{(1 - y^i)(1 - y^{i+4})}{(1 - y^{i+1})(1 - y^{i+3})}. \quad (8) $$

where $V$ and $y$ are power series determined by the equations $V = 1 + 2xV^2$, $y + y^{-1} = (xV)^{-1} - 2$. So far, there was no combinatorial explanation for the form of Equation 8. Theorem 3 provides such an explanation. Let us introduce the Fibonacci polynomials defined as follows (Flajolet and Sedgewick, 2009, eq. (62), p.327)

$$ \varphi_{n+2}(z) = \varphi_{n+1}(z) - z\varphi_n(z), \quad \varphi_0(z) = 0, \quad \varphi_1(z) = 1, \quad (9) $$

which are reciprocals of Chebyshev polynomials of the second kind, i.e. satisfy the relation

$$ \varphi_n \left( \frac{1}{y + y^{-1} + 2} \right) = \frac{1 - y^n}{(1 - y)(1 + y)^{n-1}}. \quad (10) $$

Then, Equation 8 results from the following proposition, which we prove in Section 5.

**Proposition 5** Let $p = 3$, $x_k = x\delta_{k,1}$ for $k \ge 1$ and $V = \sum_{n=0}^{\infty} \frac{(2n)!}{n!(n+1)!} (2x)^n$. For all $n \ge 0$, we have

$$ 
\begin{aligned}
H_{0;n-1} &= V^{n(3n-1)/2} \varphi_{3n+1}(xV) \\
H_{1;n-1} &= V^{n(3n+1)/2} \varphi_{3n+2}(xV)
\end{aligned}
\quad (11) $$

$$ (1 - xV)H_{2;n-1} = V^{n(3n+3)/2} \varphi_{3n+3}(xV). $$
## 3 p-paths and multicontinued fractions

We consider multivariate generating functions for p-paths with, for all $i \ge 1$, a weight $V_i$ per fall starting from a height $i$. All results stated in this section will hold with $(V_i)_{i \ge 1}$ a sequence of formal variables (i.e. its definition of Section 2 in terms of constellations is not needed). Recall that, for $n, r \ge 0$, $F_n^{(r)}$ is defined as the generating function of p-paths starting from $(-r, r)$ and ending at $(np, 0)$. Let us add an extra weight $t$ per rise and sum over all lengths, to obtain the generating functions

$$F^{(r)}(t; V_1, V_2, \dots) := \sum_{n \ge 0} F_n^{(r)} t^n. \qquad (12)$$

By elementary recursive decompositions of p-paths, we obtain the recursive equations (see Fig.2)

$$F^{(r)}(t; V_1, V_2, \dots) = \begin{cases} 1 + t F^{(p-1)}(t; V_1, V_2, \dots) & \text{if } r = 0 \\ V_r F^{(0)}(t; V_{r+1}, V_{r+2}, \dots) F^{(r-1)}(t; V_1, V_2, \dots) & \text{if } r \ge 1. \end{cases} \qquad (13)$$

We easily deduce that

$$F^{(0)}(t; V_1, V_2, \dots) = \frac{1}{1 - t \prod_{i=1}^{p-1} V_i F_n^{(0)}(t; V_{i+1}, V_{i+2}, \dots)} \qquad (14)$$

By iterating this relation, we find that $F^{(0)}(t; V_1, V_2, \dots)$ is equal to the multicontinued fraction on the r.h.s. of (1). This shows that Theorem 2 (established in Section 4) implies Theorem 1.

<figure><img src="image_2.png" /><figcaption>**Fig. 2:** Decomposition of p-paths: for $r = 0$ we remove the first rise (a), for $r \ge 1$ we perform first-passage decomposition at height $r - 1$, (b).</figcaption></figure>

We now turn to the proof of Theorem 3, which is an application of the celebrated LGV lemma (Lindström, 1969; Gessel and Viennot, 1989). We consider the weighted acyclic directed planar graph whose vertices are the $(k, l) \in \mathbb{Z} \times \mathbb{N}$ such that $k + l \equiv 0 \mod p$, and whose edges are the rises $(k, l) \to (k+1, l+p-1)$, weighted 1, and the falls $(k, l) \to (k+1, l-1)$, weighted $V_l$. For $n \in \mathbb{N}$, let $q_n$ and $r_n$ be respectively the quotient and the remainder in the Euclidean division of $k$ by $p-1$, and let

$$A_n := (-n - q_n, r_n) = (-pq_n - r_n, r_n), \qquad B_n := (np, 0). \qquad (15)$$

The generating function for paths from $A_i$ to $B_j$ $(i, j \ge 0)$ is nothing but $F_{q_i+j}^{(r_i)}$. Theorem 3 then results from the LGV lemma and the following proposition, illustrated on Fig.3.

**Proposition 6** For $m \in [0, p-1]$, there is a unique configuration of non-intersecting lattice paths connecting the sources $A_m, A_{m+1}, \dots, A_{m+n}$ to the sinks $B_0, B_1, \dots, B_n$: for $i \in [0, n]$, the source $A_{m+i}$ is connected to the source $B_i$ via the highest possible path, passing through $(-m, m+ip)$. The weight of this configuration is $\prod_{i=0}^{n} \prod_{j=1}^{ip+m} V_j$.
<figure><img src="image_3.png" /><figcaption>Fig. 3: The unique configurations of non-intersecting lattice paths contributing respectively to $H_{0;3}$, $H_{1;3}$ and $H_{2;3}$ for $p=3$.</figcaption></figure>

The proof is left to the reader. For $p=2$ we recover the known combinatorial interpretation of Hankel determinants, see e.g. Viennot (1998).

# 4 Constellations, p-paths, and the slice decomposition

In this section, we establish Theorem 2 and related results. Let us start with some definitions and notations. For $n \ge 1$, let $\mathcal{F}_n$ (resp. $\mathcal{F}_n^*$) be the set of rooted (resp. pointed rooted) p-constellations with root degree $np$. The generating function of $\mathcal{F}_n$ is $F_n$ as defined in Section 2. Similarly, let $\mathcal{V}_i$ ($i \ge 1$) be the set of pointed rooted p-constellations whose root edge is of type $j \to j-1$ with $j \le i$, to which we add a conventional “empty map” with weight 1. The generating function of $\mathcal{V}_i$ is $V_i$.

A *constellated path* is a *p-path* such that, for all $i \ge 1$, an element of $\mathcal{V}_i$ is associated with each fall from height $i$. The weight of a constellated path is the product of the weights of its associated constellations. We shall consider constellated excursions and bridges, where a *p-bridge* of length $np$ is a *p-path* starting from $(0, j)$ and ending at $(np, j)$ from some $j \in \mathbb{N}$. Theorem 2 then follows from:

**Proposition 7** There is a weight-preserving bijection between $\mathcal{F}_n$ and the set of constellated excursions of length $np$. More generally, there is a weight-preserving bijection between $\mathcal{F}_n^* \times \mathbb{N}$ and the set of constellated bridges of length $np$.

This bijection is a byproduct of the correspondence between constellations and mobiles introduced in Bouttier et al. (2004). Here we provide a direct construction, the so-called *slice decomposition*, extending the one given for $p=2$ by Bouttier and Guitter (2011).

We start from a constellation $C \in \mathcal{F}_n^*$, and a $\ell \in \mathbb{N}$ (whose role will be discussed at the very end). The white root face of $C$ forms a directed cycle which we denote by $(v_0, v_1, \dots, v_{np-1}, v_{np} = v_0)$ where, say, $v_0$ is the endpoint of the root edge (hence $v_{np-1}$ is its origin). Let $j_s$ be the type of $v_s$ (recall that the type of a vertex $v$ is the minimal length of an oriented path from $v$ to the pointed vertex), and let

$$P := ((0, j_0 + \ell), (1, j_1 + \ell), \dots, (np, j_{np} + \ell)). \qquad (16)$$

We claim that $P$ is a $p$-bridge, i.e. $j_{s+1} - j_s \in \{-1, p-1\}$ holds true for all $s \in [0, np-1]$. Indeed, since $(v_s, v_{s+1})$ is an oriented edge, we have $j_s \le j_{s+1}+1$ by the definition of type. Furthermore, the black face incident to $(v_s, v_{s+1})$ forms an oriented path of length $p-1$ from $v_{s+1}$ to $v_s$, hence $j_{s+1} \le j_s + p - 1$. Finally, since $p$ divides the length of any oriented cycle on $f$, we have $j_s \equiv j_{s+1} + 1 \mod p$, which concludes the proof of our claim. In particular, when $C$ is a rooted constellation that we point at the endpoint of the root edge, and $\ell = 0$, then $P$ is a $p$-excursion.
<figure><img src="image_4.png" /><figcaption>**Fig. 4:** The decomposition of a rooted pointed 4-constellation along leftmost minimal path into slices (a). Slices corresponding to edges of type $m \to m + 3$ are reduced to black faces (b). Identifying the two sides of the boundary of a slice of an edge of type $m \to m - 1$ yields to a pointed-rooted constellation (c).</figcaption></figure>

Let us now explain how $P$ is constellated. Assume that the constellation $C$ is embedded in the plane with the white root face as outer face, and consider, for each $s$, the *leftmost* minimal (oriented) path from $v_s$ to the pointed vertex, where minimal refers to the length of the path. This family of paths leads to a decomposition of $C$ into connected components that we call *slices*, see Fig.4(a). A slice is associated with each edge $(v_s, v_{s+1})$ incident to the white root face (thus with each step of $P$). More precisely, it is delimited by $(v_s, v_{s+1})$ and the two paths starting from $v_s$ and $v_{s+1}$ (in general, those two paths merge before reaching the pointed vertex, and we remove their common part).

Observe that when $j_{s+1} = j_s + p - 1$, the slice is reduced to a single black face (as the path starting from $v_{s+1}$ passes through $v_s$ after circumventing this face) with weight 1, see Fig. 4 (b).

Let us now assume that $j_{s+1} = j_s - 1$: we claim that the slice corresponds to an element of $\mathcal{V}_{j_s+\ell}$. Two cases may occur. If the path starting from $v_s$ passes through $v_{s+1}$, then the slice is empty, and corresponds to the empty map in $\mathcal{V}_{j_s+\ell}$. Otherwise, let $w_s$ be the vertex where the two paths starting from $v_s$ and $v_{s+1}$ merge. The boundary of the slice is therefore made of two (non-empty) oriented paths from $v_s$ to $w_s$ that do not meet except at their extremities. By construction those two paths have the same length: we may identify pairwise their edges, see Fig.4(c). This identification preserve the degrees of the white faces, hence the weights, and the orientations guarantee that the resulting map is a constellation $C_s$, which we root at $(v_s, v_{s+1})$ and point at $w_s$. By construction, the identified paths form in $C_s$ the leftmost minimal path starting with the root edge and ending at the pointed vertex. Thus, in $C_s$ the root edge is of type $j'_s \to j'_s - 1$, with $j'_s \le j_s \le j_s + \ell$, so that $C_s \in \mathcal{V}_{j_s+\ell}$ as claimed. Note that since the pointed vertex of $C$ is incident to at least one white face, there is at least one $s$ such that $j'_s = j_s$ i.e. $C_s \in \mathcal{V}_{j_s} \setminus \mathcal{V}_{j_s-1}$. This remark allows to characterize $\ell$ as the largest integer such that $P - (0, \ell)$ is still a constellated bridge.

In conclusion, the slice decomposition yields a constellated bridge. By following the steps in reverse
order, it is clear how to reconstruct a pointed rooted constellation from a constellated bridge. By the above remark we also recover the integer $\ell$ and we may check that the correspondence is one-to-one (note that constellated bridges differing by a height shift yield the same constellation, but different values of $\ell$). Thereby we prove Proposition 7 and Theorem 2. Let us now mention other byproducts of our construction.

**Proposition 8** For all $n \ge 0$ and $r \in [0, p-1]$, $F_n^{(r)}$ is the generating function of rooted p-constellations with root degree $(n+1)p$ such that, if we denote by $(v_0, v_1, \dots, v_{(n+1)p} = v_0)$ the directed cycle corresponding to the white root face ($v_0$ being the endpoint of the root edge), then all the vertices $v_1, v_2, \dots, v_{p-1-r}$ are bivalent.

**Proof:** Apply the slice decomposition with $v_0$ as pointed vertex and $\ell = 0$. The leftmost minimal path from $v_1$ to $v_0$ visits successively $v_2, \dots, v_{p-r}$, so that the constellated bridge starts with one rise followed by $p-1-r$ falls corresponding to empty slices. Removing those $p-r$ trivial steps, we obtain a constellated path with $np+r$ steps going from height $r$ to height 0. $\square$

**Proposition 9 (Bouttier et al. (2004); Di Francesco (2005))** Let $F_n^{(i-1;i)}$ be the generating function for constellated paths from $(0, i-1)$ to $(np-1, i)$. We have:

$$V_i = 1 + V_i \sum_{n=1}^{\infty} x_n F_n^{(i-1;i)} \qquad (17)$$

**Proof:** Apply the slice decomposition to a (non-empty) map in $V_i$. Taking $\ell = i-j$, where $j \to j-1$ is the type of the root edge, we obtain a constellated bridge of arbitrary length, starting at height $i-1$ and ending with a fall from height $i$, thus the factor $V_i$. The weight $x_n$ accounts for the white root face. $\square$

Note the recursive nature of (17): $F_n^{(i-1;i)}$ is a polynomial in the $V_j$'s such that $|j-i| < (p-1)n$. In particular, for $i \to \infty$, $V_i$ converges (in a suitable topology) to $V$ the generating function of $V = \bigcup_{i \ge 1} V_i$, and $F_n^{(i-1;i)} \to \binom{np-1}{n} V^{n(p-1)-1}$. Hence $V$ satisfies the recursive equation

$$V = 1 + \sum_{k=1}^{\infty} \binom{np-1}{n} x_n V^{n(p-1)}. \qquad (18)$$

By the Lagrange inversion formula, we may obtain an explicit expression for the coefficients of $V$ (Bouttier, 2005, p.131), and recover the number of rooted constellations with a prescribed degree distribution (Bousquet-Mélou and Schaeffer, 2000, Theorem 2.3). By extending the construction in (Bouttier and Guitter, 2011, Section 3.3), we may express the generating function $F_n$ in terms of $V$ as follows.

**Proposition 10** For $n \ge 0$, and $V$ the solution of (18), we have

$$F_n = \frac{1}{np+1} \binom{np+1}{n} V^{n(p-1)+1} - \sum_{k \ge 1} \left( \sum_{j=0} \frac{jp+1}{np+1} \binom{np+1}{n-j} \binom{kp-1}{k+j} \right) x_k V^{(k+n)(p-1)}. \qquad (19)$$

It would be interesting to have a similar formula for all $F_n^{(r)}$. We could then apply Theorem 3 and Corollary 4 and deduce a general expression for $V_i$. We may express $F_n^{(r)}$ in terms of $F_n$ using a Tutte-like decomposition (Bousquet-Mélou and Jehanne, 2006, Section 5.3), for instance for $p = 3$ and $r = 1$.
we have

$$F_n^{(1)} = \sum_{l \ge 1} x_l F_{n+l} + \sum_{i=0}^{n} F_i F_{n-i}. \qquad (20)$$

Applying Proposition 10 yields in principle to an expression of $F_n^{(r)}$ in terms of $V$. In practice it seems to quickly become intractable, except in the case of Eulerian triangulations on which we focus next.

# 5 Application to Eulerian triangulations

We now specialize our formulas to the case of Eulerian triangulations, i.e. $p = 3$ and $x_k = x\delta_{k,1}$. Note first that (17) reduces to (7), while (18) yields the simple equation $V = 1 + 2xV^2$, hence $V$ is as in Proposition 5. Furthermore, (19) and (20) become respectively:

$$F_n = (p_n^{(0)} \cdot (1 - 2xV) - p_{n-1}^{(3)} \cdot (xV)) V^{2n+1}, \qquad F_n^{(1)} = xF_{n+1} + \sum_{i=0}^{n} F_i F_{n-i}, \qquad (21)$$

where we introduce the shorthand notation $p_n^{(r)} := \frac{r+1}{3n+r+1} \binom{3n+r+1}{n}$, the number of 3-paths from $(-r, r)$ to $(0, 3n)$. By the relation $p_n^{(1)} = p_n^{(0)} + p_{n-1}^{(3)}$ (whose path interpretation is obvious), we may rewrite

$$F_n = (p_n^{(0)} \cdot (1 - xV) - p_n^{(1)} \cdot (xV)) V^{2n+1}. \qquad (22)$$

Using this relation in the expression (21) for $F_n^{(1)}$, and using some summation formulas for the $p_n^{(r)}$'s (following from several classical path decompositions), we arrive at

$$F_n^{(1)} = (p_n^{(1)} \cdot (1 - xV)^2 - p_{n+1}^{(0)} \cdot (xV)) V^{2n+2}. \qquad (23)$$

We are now ready to substitute these formulas into the determinants $H_{n;m}$ ($m = 0, 1, 2$) so as to prove Proposition 5. We will once again use the LGV lemma, to give another non-intersecting lattice path interpretation (NILP) of the $H_{n;m}$'s. Let us consider the same acyclic directed planar graph introduced in Section 3 for $p = 3$ (i.e. the graph on which the 3-paths live), but now with a uniform weight 1 on every edge (rise or fall). Let $A_n$ and $B_n$ be as in (15), namely $A_n = (-[3n/2], r_n)$ and $B_n = (3n, 0)$, and let us extend the graph by adding the vertices $A'_n := ((3n+1)/2, -1)$, for $n \ge 0$ and the special edges

$$\left\{ \begin{array}{ll} e_{2n} := A'_{2n} \rightarrow A_{2n} & \text{weighted } 1-xV \\ \bar{e}_{2n} := A'_{2n} \rightarrow A_{2n+1} & \text{weighted } -xV \end{array} \right. \qquad \left\{ \begin{array}{ll} e_{2n+1} := A'_{2n+1} \rightarrow A_{2n+1} & \text{weighted } (1-xV)^2 \\ \bar{e}_{2n+1} := A'_{2n+1} \rightarrow A_{2n+2} & \text{weighted } -xV \end{array} \right. . \qquad (24)$$

We readily see that the resulting graph is planar and, up to a factor $V^{2(i+j)+1}$ (resp. $V^{2(i+j+1)}$), that the generating function for paths from $A'_{2i}$ (resp. $A'_{2i+1}$) to $B_j$ ($i, j \ge 0$) is nothing but $F_{i+j}$ (resp. $F_{i+j}^{(1)}$). We may get rid of those extra factors by defining

$$T_{3k+1} := \frac{H_{0;k-1}}{V^{k(3k-1)/2}}, \qquad T_{3k+2} := \frac{H_{1;k-1}}{V^{k(3k+1)/2}}, \qquad T_{3k+3} := \frac{H_{2;k-1}(1-xV)}{V^{k(3k+3)/2}}. \qquad (25)$$

and it follows from the LGV lemma that $T_{3k+1}$ (resp. $T_{3k+2}$ and $T_{3k+3}/(1-xV)$) is the generating function of NILP configurations from the sources $A'_0, \dots, A'_{k-1}$ (resp. $A'_1, \dots, A'_k$ and $A'_2, \dots, A'_{k+1}$) to
<figure><img src="image_5.png" /><figcaption>Fig. 5: The decomposition of a configuration of $H_{0;4}$ into a configuration of $H_{0;3}$ (see (a)) or of $H_{1;3}$ (see (b)).</figcaption></figure>

the sinks $B_0, \dots, B_{k-1}$. By convention, empty configurations (for $n=0$) receive the weight 1 so that $T_1 = T_2 = 1$ and $T_3 = 1 - xV$. We claim that the $T_n$'s satisfy the recurrence relation

$$T_{n+3} = (1 - xV)T_{n+1} - xVT_n \quad (26)$$

and this is sufficient to prove that $T_n = \phi_n(xV)$, since the Fibonacci polynomials with $z = xV$ satisfy the same recurrence and initial conditions, by (9). We prove (26) via a case-by-case analysis, depending on the residue of $n$ modulo 3. Here we only check the case $n = 3k + 1$, and leave the others cases to the reader (beware the extra $1 - xV$ factor in $T_{3k+3}$). Consider a NILP configuration from $A'_0, \dots, A'_k$ to $B_0, \dots, B_k$, as counted by $T_{3k+4}$. We first easily see that, for all $i$, the path $i$ (from $A'_i$ to $B_i$) visits $(0, 3i)$, and all the steps afterward are falls. We now distinguish whether the step before $(0, 3k)$ on the uppermost path is a rise or a fall.

* If it is a fall, then all the preceding steps are rises, so that the path visits $A_{k+1}$ and passes through the special edge $\bar{e}_k$, thus has weight $-xV$. All the remaining paths form an unconstrained NILP configuration from the sources $A'_0, \dots, A'_{k-1}$ to the sinks $B_0, \dots, B_{k-1}$, with generating function $T_{3k+1}$. The global contribution of this case is $-xVT_{3k+1}$ (see Fig.5(a)).

* If it is a rise, i.e. the uppermost path visits $(-1, 3k-1)$, then, by non-intersection, the path $i$ must visit $(-1, 3i-1)$ for all $i \ge 1$, and the path 0 is reduced to the special edge $e_0$, thus has weight $1-xV$. Remove the path 0, and for each path $i \ge 1$, replace its steps after the vertex $(-1, 3i-1)$ by $3i-1$ falls (see Fig.5): the resulting configuration is a NILP configuration from the sources $A'_1, \dots, A'_k$ to the sinks $B_0, \dots, B_{k-1}$, with generating function $T_{3k+2}$. Since the correspondence is one-to-one, the global contribution of this case is $-xVT_{3k+2}$ (see Fig.5(b)).

This shows that (26) holds with $n = 3k + 1$. Together with the cases $n = 3k + 2$ and $n = 3k + 3$, this concludes the proof of Proposition 5.

## Acknowledgements

We thank P. Di Francesco for fruitful discussions. The work of M.A. in partially funded by the ERC under the agreement "ERC StG 208471 - ExploreMap".
References

M. Bousquet-Mélou. Limit laws for embedded trees: applications to the integrated superBrownian excursion. *Random Structures and Algorithms*, 29(4):475–523, 2006. arXiv:math/0501266 [math.CO].

M. Bousquet-Mélou and A. Jehanne. Polynomial equations with one catalytic variable, algebraic series and map enumeration. *Journal of Combinatorial Theory, Series B*, 96(5):623–672, 2006. arXiv:math/0504018 [math.CO].

M. Bousquet-Mélou and G. Schaeffer. Enumeration of planar constellations. *Advances in Applied Mathematics*, 24(4):337–368, 2000.

J. Bouttier. *Physique statistique des surfaces aléatoires et combinatoire bijective des cartes planaires*. These, Université Pierre et Marie Curie - Paris VI, June 2005. URL http://tel.archives-ouvertes.fr/tel-00010651/en/.

J. Bouttier and E. Guitter. Planar maps and continued fractions. *Comm. Math. Phys.*, to appear, 2011. doi: 10.1007/s00220-011-1401-z. arXiv:1007.0419 [math.CO].

J. Bouttier, P. Di Francesco, and E. Guitter. Geodesic distance in planar graphs. *Nuclear Physics B*, 663 (3):535–567, 2003a. arXiv:cond-mat/0303272 [cond-mat.stat-mech].

J. Bouttier, P. Di Francesco, and E. Guitter. Statistics of planar graphs viewed from a vertex: a study via labeled trees. *Nuclear Physics B*, 675(3):631–660, 2003b. arXiv:cond-mat/0307606 [cond-mat.stat-mech].

J. Bouttier, P. Di Francesco, and E. Guitter. Planar maps as labeled mobiles. *Electron. J. Combin.*, 11(1): R69, 2004. arXiv:math/0405099 [math.CO].

P. Chassaing and G. Schaeffer. Random planar lattices and integrated superBrownian excursion. *Probab. Theory Related Fields*, 128(2):161–212, 2004. ISSN 0178-8051. doi: 10.1007/s00440-003-0297-8. URL http://dx.doi.org/10.1007/s00440-003-0297-8.

P. Di Francesco. Geodesic distance in planar graphs: An integrable approach. *The Ramanujan Journal*, 10(2):153–186, 2005. arXiv:math/0506543 [math.CO].

P. Flajolet. Combinatorial aspects of continued fractions. *Discrete Mathematics*, 32(2):125–161, 1980.

P. Flajolet and R. Sedgewick. *Analytic combinatorics*. Cambridge University Press, 2009.

I. Gessel and X. Viennot. Determinants, paths, and plane partitions. preprint, 132(197.15), 1989.

I. Goulden and D. Jackson. Transitive factorisations into transpositions and holomorphic mappings on the sphere. *Proceedings of the American Mathematical Society*, 125(1):51–60, 1997.

A. Hurwitz. Über Riemann’sche Flächen mit gegebenen Verzweigungspunkten. *Mathematische Annalen*, 39(1):1–60, 1891.

S. Lando and A. Zvonkin. *Graphs on surfaces and their applications*, volume 141. Springer Verlag, 2004.

B. Lindström. Determinants on semilattices. *Proc. Amer. Math. Soc.*, 20:207–208, 1969.

X. G. Viennot. Une théorie combinatoire des polynômes orthogonaux. *Notes de Cours*, UQAM, Montréal, 1998. URL http://web.mac.com/xgviennot/Xavier_Viennot/polyn%C3%B4mes_orthogonaux.html.