CHROMATIC STATISTICS FOR TRIANGULATIONS AND FUSS–CATALAN COMPLEXES

Roland Bacher^{†} and Christian Krattenthaler^{‡}

† Université Grenoble I, CNRS UMR 5582, Institut Fourier, 100 rue de maths, BP 74, F-38402 St. Martin d’Hères Cedex, France.

           WWW: http://www-fourier.ujf-grenoble.fr/~bacher

‡ Fakultät für Mathematik, Universität Wien, Nordbergstraße 15, A-1090 Vienna, Austria.

               WWW: http://www.mat.univie.ac.at/~kratt

Abstract. We introduce Fuß–Catalan complexes as d-dimensional generalisations of triangulations of a convex polygon. These complexes are used to refine Catalan numbers and Fuß–Catalan numbers, by introducing colour statistics for triangulations and Fuß–Catalan complexes. Our refinements consist in showing that the number of triangulations, respectively of Fuß–Catalan complexes, with a given colour distribution of its vertices is given by closed product formulae. The crucial ingredient in the proof is the Lagrange–Good inversion formula.

1. Introduction

1.1. Catalan and Fuß–Catalan numbers. The sequence (C_{n})_{n≥0} of Catalan numbers

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, …,

see [13, sequence A108], defined by

C_{n} := \frac{1}{n + 1}\binom{2n}{n} = \frac{1}{n}\binom{2n}{n − 1},  (1.1)

is ubiquitous in enumerative combinatorics. Exercise 6.19 in [14] contains a list of 66 sequences of sets enumerated by Catalan numbers, with many more in the addendum [15]. In particular, there are \frac{1}{n+1} \binom{2n}{n} triangulations of a convex polygon^{1} with n + 2 vertices (see [14, Ex. 6.19.a]).

2010 Mathematics Subject Classification. Primary 05A15; Secondary 05A19. Key words and phrases. Catalan number, Fuß–Catalan number, triangulation, Fuß–Catalan com-

plex, barycentric subdivision, Schlegel diagram, vertex colouring, simplicial complex, Lagrange–Good inversion formula.

‡Research partially supported by the Austrian Science Foundation FWF, grants Z130-N13 and S9607-N13, the latter in the framework of the National Research Network “Analytic Combinatorics and Probabilistic Number Theory”.

1As is common, when we speak of a “convex polygon,” we always tacitly assume that all its angles are less than 180 degrees.

Even many years before Catalan’s paper [4], Fuß [7] enumerated the dissections of a convex ((d − 1)n + 2)-gon into (d + 1)-gons (obviously, any such dissection will consist of n (d + 1)-gons) and found that there are

\frac{1}{n}\binom{dn}{n − 1}  (1.2)

of those. These numbers are now commonly known as Fuß–Catalan numbers (cf. [1, pp. 59–60]).

Dissections of convex polygons into (d + 1)-gons have been studied frequently in the literature (see [11] for a survey). Moreover, they have been recently embedded into a reflection group framework in a very non-obvious way by Fomin and Reading [6], thereby extending earlier work of Fomin and Zelevinsky [5]. For further combinatorial occurrences of the Fuß–Catalan numbers, the reader is referred to [6, paragraph after (8.9)].

In the present paper, we propose a combinatorial interpretation of Fuß–Catalan numbers which, to the best of our knowledge, has not been considered before. Nevertheless it is, in some sense, perhaps a (geometrically) more natural generalisation of triangulations of a convex polygon (even if more difficult to visualise). Namely, we consider d-dimensional simplicial complexes on n + d vertices homeomorphic to a d-ball that consist of n maximal simplices all of dimension d, with the additional property that all simplices of dimension up to d − 2 lie in the boundary of the complex. (See Section 2 for the precise definition.) We call these complexes Fuß–Catalan complexes. It is not difficult to see (cf. Section 2.1) that the number of these complexes is indeed given by the Fuß–Catalan number (1.2).

We hope to provide sufficient evidence here that Fuß–Catalan complexes are generalisations of triangulations which are equally attractive as dissections of convex polygons by (d + 1)-gons. Some elementary properties of Fuß–Catalan complexes are listed in Section 2.2. Our main results (Theorems 1.1, 1.2, 2.1, and 2.2) present refinements of the plain enumeration of triangulations and Fuß–Catalan complexes arising from certain vertex-colourings of triangulations and Fuß–Catalan complexes, respectively. It seems that these are intrinsic to Fuß–Catalan complexes; in particular, we are not aware of any natural analogues of these results for polygon dissections (except for the case of triangulations).

1.2. Coloured refinements: short outline of this paper. To each triangulation, respectively, more generally, Fuß–Catalan complex, we shall associate a colouring of its vertices. In a certain sense, this colouring measures whether or not a large number of triangles (respectively maximal simplices) meets in single vertices. We show that the number of triangulations of a convex (n + 2)-gon (respectively of d-dimensional Fuß– Catalan complexes on n+d vertices) with a fixed distribution of colours of its vertices is given by closed formulae (see Theorems 1.1, 1.2, 2.1, and 2.2), thus refining the Catalan numbers (1.1) (respectively the Fuß–Catalan numbers (1.2)).

In order to give a clearer idea of what we have in mind, we shall use the remainder of this introduction to define precisely the colouring scheme for the case of triangulations, and we shall present the corresponding refined enumeration results (see Theorems 1.1 and 1.2). Subsequently, in Section 2 we generalise this setting by introducing d-dimensional Fuß–Catalan complexes for arbitrary positive integers d. The corresponding enumeration results generalising Theorems 1.1 and 1.2 are presented in Theorems 2.1 and 2.2. Section 3 is then devoted to the proof of Theorem 2.1, thus also establishing Theorem 1.1. Crucial in this proof is the Lagrange–Good inversion formula [8]. Finally, Section 4 is devoted to the proof of Theorem 2.2, and thus also of Theorem 1.2, which it generalises.

1.3. 3-Coloured triangulations. In the sequel, P_{n} stands for a convex polygon with n vertices. Since we are only interested in the combinatorics of triangulations of P_{n+2}, we can consider a unique polygon P_{n+2} for each integer n ≥ 0. A triangulation of P_{n+2} has exactly n triangles. We shall always use the Greek letter τ to denote triangulations. We call a triangulation τ of P_{n+2} 3-coloured if the n + 2 vertices of P_{n+2} are coloured with 3 colours in such a way that the three vertices of every triangle in τ have different colours. (Using a graph-theoretic term, we call a colouring with the latter property a proper colouring.) An easy induction on n shows the existence of such a colouring, and that it is unique up to permutations of all three colours.

A rooted polygon is, by definition, a (convex) polygon containing a marked oriented edge \overrightarrow{e}, the “root edge” (borrowing terminology from the theory of combinatorial maps; cf. [17]) in its boundary. In the illustrations in Figure 1, the marked oriented edge is always indicated by an arrow. We write P\overrightarrow{n+2} for a rooted polygon with n + 2 vertices. In the sequel, we omit a separate discussion of the degenerate case n = 0, where the rooted “polygon” P\overrightarrow{2} essentially only consists of the marked oriented edge \overrightarrow{e}. We agree once and for all that there is one triangulation in this case.

For n ≥ 1, a triangulation τ of P\overrightarrow{n+2} has a unique triangle Δ_{∗} that contains the marked oriented edge \overrightarrow{e}. We consider this “root triangle” as a triangle with totally ordered vertices v_{0} < v_{1} < v_{2}, where \overrightarrow{e} starts at v_{1} and ends at v_{2}. The n+2 vertices of a triangulation τ of P\overrightarrow{n+2} can then be uniquely coloured with three colours \{a,b,c\} such that \overrightarrow{e} starts at a vertex of colour b, ends at a vertex of colour c, and vertices of every triangle Δ ∈ τ have different colours. Figure 1 shows all such 3-coloured triangulations of P\overrightarrow{n+2} for n = 0, 1, 2, 3.

Figure 1. All 3-coloured triangulations for n = 0, 1, 2, 3.

Our first result provides a closed formula for the number of triangulations with a fixed colour distribution of its vertices.

Theorem 1.1. Let n be a non-negative integer and α, β, γ non-negative integers with α + β + γ = n + 2. Then the number of triangulations of the rooted polygon P\overrightarrow{n+2} with α vertices of colour a, β vertices of colour b, and γ vertices of colour c in the uniquely determined colouring induced by a triangulation, in which the starting vertex of the marked oriented edge \overrightarrow{e} has colour b, its ending vertex has colour c, and the three vertices in each triangle have different colours, is equal to

\frac{α(α + β + γ − 2)}{(β + γ − 1)(α + γ − 1)(α + β − 1)}\binom{β + γ − 1}{α}\binom{α + γ − 1}{β − 1}\binom{α + β − 1}{γ − 1} . (1.3)

In the case where α = 0, this has to be interpreted as the limit α → 0, that is, it is 1 if (α, β, γ) = (0, 1, 1) and 0 otherwise.

As we already announced, we shall generalise this theorem in Theorem 2.1 from triangulations to simplicial complexes. Its proof (given in Section 3) shows that the corresponding generating function, that is, the series

C = C(a, b, c) = ∑_{α,β,γ≥0} C_{α,β,γ}a^{α}b^{β}c^{γ},

where C_{α,β,γ} is the number of triangulations in Theorem 1.1, is algebraic. To be precise, from the equations given in Section 3 (specialised to d = 2), one can extract that

(bc)^{3}(1 + a) + (bc)^{2}((b + c)a − 1)C + (bc)^{2}(a − 2)C^{2} + 2bcC^{3} + bcC^{4} − C^{5} = 0 . (1.4)

Next we identify two of the three colours. In other words, we now consider improper colourings of triangulations of P\overrightarrow{n+2} by two colours, say black and white, such that every triangle has exactly one black vertex and two white vertices. There are then two possibilities to colour the marked oriented edge \overrightarrow{e}: either both of its incident vertices are coloured white, or one is coloured white and the other black (for the purpose of enumeration, it does not matter which of the two is white respectively black in the latter case). Remarkably, in both cases there exist again closed enumeration formulae for the number of triangulations with a given colour distribution.

Theorem 1.2. Let n, b, w be non-negative integers with b + w = n + 2.

(i) The number of triangulations of the rooted polygon P\overrightarrow{n+2} with b black vertices and w white vertices in the uniquely determined colouring induced by a triangulation, in which both vertices of the marked oriented edge \overrightarrow{e} are coloured white, and, in each triangle, exactly two of the three vertices are coloured white, is equal to

\frac{2b}{(w − 1)(2b + w − 2)}\binom{2b + w − 2}{w − 2}\binom{w − 1}{b} .

(ii) The number of triangulations of the rooted polygon P\overrightarrow{n+2} with b black vertices and w white vertices in the uniquely determined colouring induced by a triangulation, in which the starting vertex of the marked oriented edge \overrightarrow{e} is coloured white, its ending vertex is coloured black, and, in each triangle, exactly two of the three vertices are coloured white, is equal to

\frac{1}{2b + w − 2}\binom{2b + w − 2}{w − 1}\binom{w − 1}{b − 1} .

Obviously, the generating functions corresponding to the numbers in the above theorem must be algebraic. To be precise, it follows from (1.4) that the series Y = C(x, y, y) (the generating function for the numbers in item (i) of Theorem 1.2) and the series Z = C(x, x, y) (the generating function for the numbers in item (ii) of Theorem 1.2) satisfy the algebraic equations

(1 + x)y^{4} − y^{2}(1 + 2y)Y + y(2 + y)Y^{2} − Y^{3} = 0  (1.5)

and

x^{2}y^{2} + xy(x − 1)Z + Z^{3} = 0 ,  (1.6)

respectively. As we announced, Theorem 1.2 will be generalised from triangulations to simplicial complexes in Theorem 2.2.

Clearly, if we identify all three colours, then we are back to counting all triangulations of the polygon P_{n+2}, of which there are C_{n} = \frac{1}{n+1} \binom{2n}{n}.

We end this introduction by mentioning that checkerboard colourings of triangulations (obtained by colouring adjacent triangles with different colours chosen in a set of two colours) encode winding properties of the corresponding 3-vertex colouring. Indeed, a 3-coloured triangulation τ of P_{n+2} induces a unique piecewise affine map φ from P_{n+2} onto a vertex-coloured triangle Δ such that φ is colour-preserving on vertices and induces affine bijections between triangles of τ and Δ. The map φ is orientationpreserving, respectively orientation reverting, on black, respectively white, triangles of τ endowed with a suitable black-white checkerboard colouring. Restricting φ to the oriented boundary of P_{n+2} we get a closed oriented path contained in the boundary of Δ. The winding number of this path with respect to an interior point of Δ is given by the difference of black and white triangles in the checkerboard colouring mentioned above. The resulting statistics for Catalan numbers (and the obvious generalization to Fuß–Catalan numbers obtained by replacing winding numbers with the corresponding homology classes) have been studied by Callan in [2].

2. Refinements of Fuß–Catalan numbers

2.1. Fuß–Catalan complexes. Given an integer d ≥ 2, we define a d-dimensional Fuß–Catalan complex of index n ≥ 1 to be a simplicial complex Σ such that:

(i) Σ is a d-dimensional simplicial complex homeomorphic to a closed d-dimensional ball having n simplices of maximal dimension d.

(ii) All simplices of dimension up to d − 2 of Σ are contained in the boundary ∂Σ (homeomorphic to a (d − 1)-dimensional sphere) of Σ. (Equivalently, the (d − 2)-skeleton of Σ is contained in its boundary ∂Σ).

Such a complex Σ is rooted if its boundary ∂Σ contains a marked (d − 1)-simplex, Δ_{∗} say, with totally ordered vertices. We denote a rooted d-dimensional Fuß–Catalan complex by the pair (Σ, Δ_{∗}). By convention, a rooted d-dimensional Fuß–Catalan complex of index 0 is given by (Δ_{∗}, Δ_{∗}), where Δ_{∗} is a simplex of dimension d − 1 with totally ordered vertices.

Rooted d-dimensional Fuß–Catalan complexes are generalisations of rooted triangulations of polygons. In particular, a rooted 2-dimensional Fuß–Catalan complex of index n is a triangulation of the rooted polygon P\overrightarrow{n+2} with n + 2 vertices.

Let fc_{d}(n) denote the number of d-dimensional rooted Fuß–Catalan complexes of index n, and let FC_{d}(z) = ∑_{n≥0} fc_{d}(n)z^{n} be the corresponding generating function. Consider a rooted d-dimensional Fuß–Catalan complex (Σ, Δ_{∗}). The marked (d − 1)- dimensional simplex Δ_{∗} is contained in a unique d-dimensional simplex of Σ, which we call the root simplex of the complex. By deleting the root simplex, we are left with a set of d smaller Fuß–Catalan complexes — the d subcomplexes which were “glued” to the d facets of the root simplex. (This is the extension of the standard decomposition of a rooted triangulation when one removes the “root triangle”). These subcomplexes inherit also naturally a marked (d − 1)-dimensional simplex; that is, they are rooted Fuß–Catalan complexes themselves. Namely, if v_{1} < v_{2} < ⋯ < v_{d} is the total order of the vertices of Δ_{∗} and v_{0} is the additional vertex of the root simplex (containing Δ_{∗}), then we impose the order

v_{0} < v_{1} < ⋯ < v_{d}  (2.1)

on the vertices of the root simplex, and we declare the (d − 1)-dimensional simplex in which the subcomplex intersects the root simplex to be the marked simplex of the subcomplex, together with the total order which results from (2.1) by restriction. This decomposition leads directly to the functional equation

FC_{d}(z) = 1 + z( FC_{d}(z))^{d}.

Under the substitution FC_{d}(z) = 1 + f_{d}(z), this is equivalent to

\frac{f_{d}(z)}{(1 + f_{d}(z))^{d}} = z.

This shows that f_{d}(z) is the compositional inverse series of z/(1 + z)^{d}. Consequently, the coefficient of z^{n} in f_{d}(z), which equals the number fc_{d}(n), can be found using the Lagrange inversion formula (cf. [14, Theorem 5.4.2 with k = 1]). The result is the Fuß–Catalan number (1.2); that is, the number of d-dimensional rooted Fuß–Catalan complexes of index n is indeed given by \frac{1}{n} \binom{dn}{n−1}.

2.2. Elementary properties of Fuß–Catalan complexes. A Fuß–Catalan complex is completely determined by its 1-skeleton. This is seen by gluing simplices onto all cliques (maximal complete subgraphs) of the 1-skeleton. The boundaries of two different rooted Fuß–Catalan complexes of dimension > 2 are thus always combinatorially inequivalent when taking into account the marked simplex Δ_{∗} with its totally ordered vertices.

However, the dimension d and the number of vertices (or, equivalently, d and the number of d-dimensional simplices) determine the number of simplices of given dimension in a Fuß–Catalan complex completely: for i = 0, 1, …, d − 1, let f̃_{i}(n, d) denote the number of i-simplices contained in the boundary of a d-dimensional Fuß–Catalan complex (Σ, Δ_{∗}) consisting of n > 0 simplices of maximal dimension d. (The interior of Σ contains of course n simplices of maximal dimension d separated by (n − 1) simplices of dimension d − 1.) We then have f̃_{i}(1, d) = \binom{d+1}{i+1} for i ∈ \{0, 1, …, d − 1\} since a Fuß–Catalan complex with n = 1 is a d-dimensional simplex, which has \binom{d+1}{i+1} simplices of dimension i. For n ≥ 1, there hold the explicit formulae

f̃_{d−1}(n, d) = n(d − 1) + 2,  (2.2)
f̃_{i}(n, d) = n\binom{d}{i} + \binom{d}{i + 1},  for i = 0, 1, …, d − 2.  (2.3)

Indeed, gluing an additional d-dimensional simplex to a Fuß–Catalan complex adds one vertex and d new (d − 1)-dimensional simplices on the boundary and hides a unique (d − 1)-dimensional simplex in the interior. Moreover, for i < d − 1, an i-simplex is either contained in the boundary of the old complex or it involves the newly added point and is entirely contained in the added new d-dimensional simplex. In particular, there are \binom{d}{i} i-simplices of the latter kind.

It is natural to ask whether Fuß–Catalan complexes admit “natural” realisations as polytopes. We shall present such a realisation in the next paragraph. It is based on the observation that Fuß–Catalan complexes of dimension d can equivalently be described by (d−1)-dimensional Schlegel diagrams. In order to explain this alternative description, we embed a given Fuß–Catalan complex as a d-dimensional convex polytope P of ℝ^{d}. We choose now a point O ∈ ℝ^{d} \ P such that the convex hull of P and O is obtained by gluing a unique simplex spanned by O and Δ_{∗} onto P. We require moreover that every segment joining O to a vertex of P \ Δ_{∗} intersects the marked boundary simplex Δ_{∗} in its interior. The central projection of P onto Δ_{∗} with respect to the point O is then called a Schlegel diagram of P. It contains all the combinatorial information allowing the reconstruction of the initial Fuß-Catalan complex. More precisely, it is given (up to combinatorial equivalence) by so-called barycentric subdivisions starting with the marked simplex Δ_{∗} (which, as always, we consider with the extra-structure given by its completely ordered vertices): a barycentric subdivision of a (d − 1)-dimensional simplex Δ with vertices V is obtained by partitioning Δ into d simplices Δ_{v}, indexed by v ∈ V, defined by considering the convex hull of V \ {v} and of the barycenter b = \frac{1}{d} ∑_{w∈V} w of Δ. Iterating barycentric subdivisions n times in all possible ways starting with the (d − 1)-dimensional simplex Δ_{∗} gives exactly the set of all Schlegel diagrams (as described above) of all d-dimensional Fuß–Catalan complexes consisting of n simplices of maximal dimension d. Note that barycentric subdivisions add only points with rational coordinates if all vertices of Δ_{∗} have rational coordinates (more precisely, all vertices belong to A (ℤ [\frac{1}{d}])^{d} if A is a positive integer such that AΔ_{∗} has integral coordinates). A pleasant feature of barycentric subdivisions is the fact that they carry a natural distributive lattice structure (defined by unions and intersections).

A (more or less) natural polytope P ⊂ ℝ^{d} representing a given d-dimensional Fuß-Catalan complex (Σ, Δ_{∗}) can now be constructed as follows: choose the d ordered points

(1 − d, 1, 1, …, 1) < (1, 1 − d, 1, 1, …, 1) < ⋯ < (1, 1, …, 1, 1, d − 1)

of ℤ^{d} as vertices for Δ_{∗} and use Δ_{∗} for constructing a barycentric subdivision BS corresponding to (Σ, Δ_{∗}). Associate to a vertex V = (a_{1}, a_{2}, …, a_{d}) of BS the point

Ṽ = (a_{1}, a_{2}, …, a_{d}) + (1, 1, …, 1) ∑_{j=1}^{d} a_{j}^{2} ∈ ℚ^{d} .

The set of all points Ṽ associated to vertices of BS is then the set of vertices of a polytope realising (Σ, Δ_{∗}) in ℝ^{d}.

2.3. (d + 1)-colourings of d-dimensional Fuß–Catalan complexes. Let C be a set of colours. A proper colouring of a simplicial complex Σ with vertex set V by colours from C is a map γ : V ⟶ C such that γ(v) ≠ γ(w) for any pair of vertices v, w defining a 1-simplex of Σ. Equivalently, a proper colouring of a simplicial complex Σ is a proper colouring of the graph defined by the 1-skeleton of Σ.

Every rooted d-dimensional Fuß–Catalan complex (Σ, Δ_{∗}) has a unique colouring by (d + 1) totally ordered colours c_{0} < c_{1} < ⋯ < c_{d} such that the i-th vertex of Δ_{∗} (in the given total order of the vertices of Δ_{∗}) has colour c_{i}, i = 1, 2, …, d. The following theorem presents a closed formula for the number of Fuß–Catalan complexes of index n with a given colour distribution.

Theorem 2.1. Let d, n, γ_{0}, γ_{1}, …, γ_{d} be non-negative integers with d ≥ 2 and γ_{0} +γ_{1} + ⋯ + γ_{d} = n + d. Then the number of d-dimensional Fuß–Catalan complexes (Σ, Δ_{∗}) of index n with γ_{i} vertices of colour c_{i}, i = 0, 1, …, d, in the uniquely determined proper colouring by the colours c_{0}, c_{1}, …, c_{d} in which the i-th vertex of the root simplex Δ_{∗} has colour c_{i}, i = 1, 2, …, d, is equal to

s^{d−1} \frac{γ_{0}}{s − γ_{0} + 1}\binom{s − γ_{0} + 1}{γ_{0}} ∏_{j=1}^{d} \frac{1}{s − γ_{j} + 1}\binom{s − γ_{j} + 1}{γ_{j} − 1} ,  (2.4)

where s = −d + ∑_{j=0}^{d} γ_{j}. In the case where γ_{0} = 0, this has to be interpreted as the limit γ_{0} → 0, that is, it is 1 if (γ_{0}, γ_{1}, …, γ_{d}) = (0, 1, 1, …, 1) and 0 otherwise.

Formula (2.4) generalises Formula (1.3), the latter corresponding to the case d = 2 of the former.

2.4. Specialisations obtained by identifying colours. Generalising the scenario in Theorem 1.2, we now identify some of the colours. Namely, given a non-negative integer k and k +1 positive integers β_{0}, β_{1}, β_{2}, …, β_{k} with β_{0} +β_{1} +β_{2} +⋯+β_{k} = d+1, we set

c_{0} = ⋯ = c_{β_{0}−1} = c′_{0}
c_{β_{0}} = ⋯ = c_{β_{0}+β_{1}−1} = c′_{1}
⋮
c_{β_{0}+β_{1}+···+β_{i−1}} = ⋯ = c_{β_{0}+β_{1}+···+β_{i}−1} = c′_{i}
⋮
c_{β_{0}+β_{1}+···+β_{k−1}} = ⋯ = c_{d} = c′_{k}.

Given a rooted Fuß–Catalan complex (Σ, Δ_{∗}) with its uniquely determined colouring as in Theorem 2.1, after this identification we obtain a colouring of the simplices of (Σ, Δ_{∗}) in which each d-dimensional simplex has β_{i} vertices of colour c′_{i}, i = 0, 1, …, k. Our next theorem presents a closed formula for the number of d-dimensional Fuß–Catalan complexes of index n with a given colour distribution after this identification of colours.

Theorem 2.2. Let d, k, n, β_{0}, β_{1}, …, β_{k}, γ_{0}, γ_{1}, …, γ_{k} be non-negative integers with d ≥ 2, β_{0} + β_{1} + β_{2} + ⋯ + β_{k} = d + 1, and γ_{0} + γ_{1} + ⋯ + γ_{k} = n + d. Then the number of d-dimensional Fuß–Catalan complexes (Σ, Δ_{∗}) of index n with γ_{i} vertices of colour c′_{i}, i = 0, 1, …, k, in the uniquely determined colouring in which the first β_{0} − 1 vertices of the root simplex Δ_{∗} have colour c′_{0}, the next β_{1} vertices have colour c′_{1}, the next β_{2} vertices have colour c′_{2}, …, the last β_{k} vertices have colour c′_{k}, and in which each d-dimensional simplex has β_{i} vertices of colour c′_{i}, i = 0, 1, …, k, is equal to

s^{k−1} \frac{γ_{0} − β_{0} + 1}{β_{0}s + β_{0} − γ_{0}} \binom{β_{0}s + β_{0} − γ_{0}}{γ_{0} − β_{0} + 1} ∏_{j=1}^{k} \frac{β_{j}}{β_{j}s + β_{j} − γ_{j}} \binom{β_{j}s + β_{j} − γ_{j}}{γ_{j} − β_{j}} ,

where s = −d + ∑_{j=0}^{k} γ_{j}.

This theorem contains all the afore-mentioned results as special cases. Clearly, Theorem 2.1 is the special case of Theorem 2.2 where k = d and β_{0} = β_{1} = ⋯ = β_{d} = 1 (and Theorem 1.1 is the further special case in which d = 2). Item (i) of Theorem 1.2 results for d = 2, k = 1, β_{0} = 1, β_{1} = 2, while item (ii) results for d = 2, k = 1, β_{0} = 2, β_{1} = 1. Moreover, upon setting k = 0 and β_{0} = d+1 in Theorem 2.2, we obtain Formula (1.2) (and (1.1) in the further special case where d = 2).

3. Generating functions and the Lagrange–Good inversion formula

In this section we provide the proof of Theorem 2.1. It makes use of generating function calculus, which serves to reach a situation in which the Lagrange–Good inversion formula [8] (see also [10, Sec. 5] and the references cited therein) can be applied to compute the numbers that we are interested in. The proof requires as well a determinant evaluation, which we state and establish separately at the end of this section.

Proof of Theorem 2.1. Let

C_{d}(x_{0}, x_{1}, …, x_{d}) := ∑_{(Σ,Δ_{∗})} x_{0}^{γ_{0}(Σ,Δ_{∗})}x_{1}^{γ_{1}(Σ,Δ_{∗})} ⋯ x_{d}^{γ_{d}(Σ,Δ_{∗})},

where the sum is over all d-dimensional Fuß–Catalan complexes (Σ, Δ_{∗}) (of any index, including the (d − 1)-dimensional complex (Δ_{∗}, Δ_{∗}) of index 0), and where γ_{i}(Σ, Δ_{∗}) denotes the number of vertices of colour c_{i} in the unique colouring of (Σ, Δ_{∗}) described in the statement of Theorem 2.1. It is our task to compute the coefficient of x_{0}^{γ_{0}}x_{1}^{γ_{1}} ⋯ x_{d}^{γ_{d}} in the series C_{d}(x_{0}, x_{1}, …, x_{d}).

Starting from our generating function C_{d}(x_{0}, x_{1}, …, x_{d}), we define d + 1 series by cyclically permuting the variables,

C^{{0}}(x_{0}, x_{1}, …, x_{d}) = C_{d}(x_{0}, x_{1}, …, x_{d}),
C^{{1}}(x_{0}, x_{1}, …, x_{d}) = C_{d}(x_{1}, x_{2}, …, x_{d}, x_{0}),
⋮
C^{{d}}(x_{0}, x_{1}, …, x_{d}) = C_{d}(x_{d}, x_{0}, x_{1}, …, x_{d−1}).

The decomposition of rooted d-dimensional Fuß–Catalan complexes (Σ, Δ_{∗}) determined by the unique d-dimensional simplex containing Δ_{∗}, which we described in Section 2.1, yields a system of equations relating these d + 1 series. To be precise, let (Σ, Δ_{∗}) be a rooted d-dimensional Fuß–Catalan complex of index n ≥ 1, and let Δ_{∗}^{d} be its unique d-dimensional simplex containing Δ_{∗}. It intersects Σ \ Δ_{∗}^{d} along d rooted sub-Fuß– Catalan complexes, with their marked (d − 1)-dimensional simplices defined by their intersection with the boundary of Δ_{∗}^{d}. These sub-complexes define a decomposition of (Σ, Δ_{∗}). It shows that

C_{d}(x_{0}, x_{1}, …, x_{d}) = x_{1} ⋯ x_{d} + \frac{1}{x_{0}(x_{0}x_{1} ⋯ x_{d})^{d−2}} ∏_{j=1}^{d}C^{\{j\}}(x_{0}, x_{1}, …, x_{d}),

and, more generally,

C^{\{i\}}(x_{0}, x_{1}, …, x_{d}) = \frac{x_{0}x_{1} ⋯ x_{d}}{x_{i}} + \frac{1}{x_{i}(x_{0}x_{1} ⋯ x_{d})^{d−2}}_{∏_{j=0}^{d} ; j≠i}C^{\{j\}}(x_{0}, x_{1}, …, x_{d}),

i = 0, 1, …, d. (3.1)

In order to simplify this system of equations, we define d + 1 series g_{0}, g_{1}, …, g_{d} by the equations

C^{\{i\}}(x_{0}, x_{1}, …, x_{d}) = \frac{1}{x_{i}} (1 + g_{i}(x_{0}, x_{1}, …, x_{d})) ∏_{j=0}^{d} x_{j},  i = 0, 1, …, d. (3.2)

The reader should keep in mind that we want to compute the coefficient of x_{0}^{γ_{0}}x_{1}^{γ_{1}} ⋯ x_{d}^{γ_{d}} in the series C_{d}(x_{0}, x_{1}, …, x_{d}), that is, in terms of the new series, the coefficient of x_{0}^{γ_{0}}x_{1}^{γ_{1}−1}x_{2}^{γ_{2}−1} ⋯ x_{d}^{γ_{d}−1} in the series g_{0}(x_{0}, x_{1}, …, x_{d}).

From now on, we suppress the arguments of series for the sake of better readability; that is, we write g_{i} instead of g_{i}(x_{0}, x_{1}, …, x_{d}), etc., for short. With this notation, the system (3.1) becomes

g_{i} = \frac{x_{i}}{(1 + g_{i})} ∏_{j=0}^{d}(1 + g_{j}), i = 0, 1, …, d,

or, equivalently,

x_{i} = \frac{g_{i}(1 + g_{i})}{∏_{j=0}^{d}(1 + g_{j})}, i = 0, 1, …, d.

By a straightforward application of the Lagrange–Good inversion formula [8], we have

⟨x^{γ}⟩ g_{0} = ⟨x^{−1}⟩ x_{0} det(J_{d+1}) ∏_{j=0}^{d} \frac{(1 + x_{j})^{d+|γ|−γ_{j}}}{x_{j}^{γ_{j}+1}} ,

where ⟨x^{γ}⟩ g_{0} denotes the coefficient of x_{0}^{γ_{0}}x_{1}^{γ_{1}} ⋯ x_{d}^{γ_{d}} in the series g_{0}, ⟨x^{−1}⟩ f denotes the coefficient of x_{0}^{−1}x_{1}^{−1} ⋯ x_{d}^{−1} in the series f, |γ| stands for ∑_{j=0}^{d} γ_{j}, and J_{d+1} is the Jacobian of the map (x_{0}, x_{1}, …, x_{d}) ⟼ (y_{0}, y_{1}, …, y_{d}) defined by

y_{i} = \frac{x_{i}(1 + x_{i})}{∏_{j=0}^{d}(1 + x_{j})}, i = 0, 1, …, d.

A simple computation yields that the entries of J_{d+1} are given by

(J_{d+1})_{i,j} = −\frac{x_{i}(1 + x_{i})}{(1 + x_{j}) ∏_{k=0}^{d}(1 + x_{k})}, if i ≠ j,
(J_{d+1})_{i,i} = \frac{1 + x_{i}}{∏_{k=0}^{d}(1 + x_{k})}.

CHROMATIC STATISTICS FOR TRIANGULATIONS AND FUSS–CATALAN COMPLEXES 11

By Proposition 3.1 at the end of this section, it follows that

⟨x^{γ}⟩ g_{0} = ⟨x^{−1}⟩ x_{0}( ∏_{j=0}^{d} \frac{(1 + x_{j})^{|γ|−γ_{j}−1}(1 + 2x_{j})}{x_{j}^{γ_{j}+1}})(1 − ∑_{k=0}^{d} \frac{x_{k}}{1 + 2x_{k}} )

= ⟨x^{γ}⟩ x_{0}( ∏_{j=0}^{d}(1 + x_{j})^{|γ|−γ_{j}−1}(1 + 2x_{j}))(1 − ∑_{k=0}^{d} \frac{x_{k}}{1 + 2x_{k}} ).

Consequently, we get ⟨x^{γ}⟩ g_{0}

= (\binom{|γ| − γ_{0} − 1}{γ_{0} − 1} + 2\binom{|γ| − γ_{0} − 1}{γ_{0} − 2}) ∏_{j=1}^{d} (\binom{|γ| − γ_{j} − 1}{γ_{j}} + 2\binom{|γ| − γ_{j} − 1}{γ_{j} − 1})

− \binom{|γ| − γ_{0} − 1}{γ_{0} − 2} ∏_{j=1}^{d} (\binom{|γ| − γ_{j} − 1}{γ_{j}} + 2\binom{|γ| − γ_{j} − 1}{γ_{j} − 1})

− (\binom{|γ| − γ_{0} − 1}{γ_{0} − 1} + 2\binom{|γ| − γ_{0} − 1}{γ_{0} − 2})

× ∑_{k=1}^{d} \binom{|γ| − γ_{k} − 1}{γ_{k} − 1}_{∏_{j=1}^{d} ; j≠k} (\binom{|γ| − γ_{j} − 1}{γ_{j}} + 2\binom{|γ| − γ_{j} − 1}{γ_{j} − 1}) .

Setting

P = ∏_{j=1}^{d} (\binom{|γ| − γ_{j} − 1}{γ_{j}} + 2\binom{|γ| − γ_{j} − 1}{γ_{j} − 1})

= |γ|^{d} ∏_{j=1}^{d} \frac{(|γ| − γ_{j} − 1)!}{γ_{j}! (|γ| − 2γ_{j})!} ,

we can rewrite this as

⟨x^{γ}⟩ g_{0} = (\binom{|γ| − γ_{0} − 1}{γ_{0} − 1} + \binom{|γ| − γ_{0} − 1}{γ_{0} − 2}) P

− (\binom{|γ| − γ_{0} − 1}{γ_{0} − 1} + 2\binom{|γ| − γ_{0} − 1}{γ_{0} − 2}) P ∑_{k=1}^{d} \frac{\binom{|γ|−γ_{k}−1}{γ_{k}−1}}{\binom{|γ|−γ_{k}−1}{γ_{k}} + 2\binom{|γ|−γ_{k}−1}{γ_{k}−1}}

= \binom{|γ| − γ_{0}}{γ_{0} − 1}P − \frac{|γ| − 1}{|γ| − γ_{0}} \binom{|γ| − γ_{0}}{γ_{0} − 1}P ∑_{k=1}^{d} \frac{γ_{k}}{|γ|}

= \frac{1}{|γ|}\binom{|γ| − γ_{0}}{γ_{0} − 1}P .

This shows that

⟨x^{γ}⟩ g_{0} = \frac{|γ|^{d−1}(|γ| − γ_{0})!}{(γ_{0} − 1)! (|γ| + 1 − 2γ_{0})!} ∏_{j=1}^{d} \frac{(|γ| − γ_{j} − 1)!}{γ_{j}! (|γ| − 2γ_{j})!} .  (3.3)

Now we should remember that we actually wanted to compute the coefficient of x_{0}^{γ_{0}}x_{1}^{γ_{1}−1}x_{2}^{γ_{2}−1} ⋯ x_{d}^{γ_{d}−1} in the series g_{0}(x_{0}, x_{1}, …, x_{d}). So, we have to replace γ_{i} by γ_{i} − 1 for i = 1, 2, …, d and, thus, |γ| by s = −d + ∑_{j=0}^{d} γ_{j} in (3.3). If we do this, then we arrive easily at (2.4). □

Proposition 3.1. Let d be a non-negative integer and J_{d+1} be the (d + 1) × (d + 1) matrix

(\begin{cases}\frac{1+x_{i}}{∏_{k=0}^{d}(1+x_{k})} & i = j \\ −\frac{x_{i}(1+x_{i})}{(1+x_{j}) ∏_{k=0}^{d}(1+x_{k})} & i ≠ j \end{cases} )_{0≤i,j≤d} .

Then we have

det(J_{d+1}) = (1 − ∑_{k=0}^{d} \frac{x_{k}}{1 + 2x_{k}} ) ∏_{j=0}^{d} \frac{1 + 2x_{j}}{(1 + x_{j})^{d+1}} .  (3.4)

Proof. By factoring terms that only depend on the row index or only on the column index, we see that

det(J_{d+1}) = ∏_{j=0}^{d} \frac{1}{(1 + x_{j})^{d+1}} det (\begin{cases}1 + x_{i} & i = j \\ −x_{i} & i ≠ j \end{cases} )_{0≤i,j≤d} .  (3.5)

The above determinant equals the sum over all principal minors of the matrix

(\begin{cases}x_{i} & i = j \\ −x_{i} & i ≠ j \end{cases} )_{0≤i,j≤d} ,

where, as usual, a principal minor is by definition the determinant of a submatrix with rows and columns indexed by a common subset of {0, 1, …, d}. Again factoring terms that only depend on the row index, we may write the principal minor corresponding to the submatrix indexed by i_{1}, i_{2}, …, i_{k} in the form

x_{i_{1}}x_{i_{2}} ⋯ x_{i_{k}} det (\begin{cases}1 & i = j \\ −1 & i ≠ j \end{cases} )_{1≤i,j≤k} .  (3.6)

The determinant in this expression occurs frequently. In fact, we have

det(λI_{k} − A_{k}) = λ^{k−1}(λ − k),

where I_{k} is the k ×k identity matrix and A_{k} the k ×k all-1’s-matrix. (This is easily seen by observing that the matrix A_{k} has an eigenvector (1, 1, …, 1) with eigenvalue k and that the space orthogonal to (1, 1, …, 1) is the kernel of A_{k}.) By using this observation with λ = 2, it follows that the expression (3.6) simplifies to

x_{i_{1}}x_{i_{2}} ⋯ x_{i_{k}}2^{k−1}(2 − k).

If this is substituted in (3.5), we obtain

det(J_{d+1}) = ∏_{j=0}^{d} \frac{1}{(1 + x_{j})^{d+1}} ∑_{k=0}^{d+1} 2^{k−1}(2 − k)e_{k}(x_{0}, x_{1}, …, x_{d}) ,  (3.7)

CHROMATIC STATISTICS FOR TRIANGULATIONS AND FUSS–CATALAN COMPLEXES 13

where e_{k}(x_{0}, x_{1}, …, x_{d}) = ∑_{0≤i_{1}<···<i_{k}≤d} x_{i_{1}}x_{i_{2}} ⋯ x_{i_{k}} denotes the k-th elementary symmetric function. As is well-known, these polynomials satisfy the generating function identity

∑_{k=0}^{d+1} e_{k}(x_{0}, x_{1}, …, x_{d}) t^{k} = ∏_{j=0}^{d}(1 + x_{j}t) .  (3.8)

By differentiating this identity with respect to t, we obtain the further equation

∑_{k=1}^{d+1} k e_{k}(x_{0}, x_{1}, …, x_{d}) t^{k−1} = ∑_{k=0}^{d} \frac{x_{k}}{1 + x_{k}t} ∏_{j=0}^{d}(1 + x_{j}t) .

Using both with t = 2 in (3.7), we arrive exactly at the right-hand side of (3.4). □

4. Proof of Theorem 2.2

We perform a reverse induction on k. For the start of the induction, we remember that Theorem 2.2 is nothing but Theorem 2.1 (which we established in the previous section) if k = d and β_{0} = β_{1} = β_{2} = ⋯ = β_{d} = 1.

For the induction step, we have to distinguish two cases. Suppose first that β_{0} = 1 and that Theorem 2.2 holds for all (suitable) sequences β_{0} = 1, β_{1}, β_{2}, …, β_{k+1}. Then Theorem 2.2 holds for β_{0} = 1, β_{1} + β_{2}, β_{3}, …, β_{k+1} if and only if

s ∑_{k=β_{1}}^{γ−β_{2}} \frac{β_{1}}{β_{1}s + β_{1} − k} \binom{β_{1}s + β_{1} − k}{k − β_{1}} \frac{β_{2}}{β_{2}s + β_{2} − (γ − k)}\binom{β_{2}s + β_{2} − (γ − k)}{γ − k − β_{2}}

= \frac{(β_{1} + β_{2})}{(β_{1} + β_{2})(s + 1) − γ} \binom{(β_{1} + β_{2})(s + 1) − γ}{γ − β_{1} − β_{2}}

for all γ ≥ β_{1} + β_{2}. (Without loss if generality, it suffices to consider the addition of β_{1} and β_{2}, since all other combinations lead to analogous and equivalent statements.) This is a special case of an identity commonly attributed to Rothe [12] (to be precise, it is the case α → β_{1}s, β → −1, γ → β_{2}s + β_{1} + β_{2}, n → γ − β_{1} − β_{2} of [9, Eq. (4)]; see [16] for historical comments and more on this kind of identities, although, for some reason, it misses [3]), which establishes the induction step in this case.

Suppose now that Theorem 2.2 holds for all (suitable) sequences β_{0}, β_{1}, β_{2}, …, β_{k+1}. Then Theorem 2.2 holds for β_{0} + β_{1}, β_{2}, β_{3}, …, β_{k+1} if and only if

∑_{k=β_{0}}^{γ−β_{1}} \frac{β_{1}s}{β_{0}s + β_{0} − k} \binom{β_{0}s + β_{0} − k}{k − β_{0}}\binom{β_{1}s + β_{1} − 1 − (γ − k)}{γ − k − β_{1}}

= \binom{(β_{0} + β_{1})(s + 1) − 1 − γ}{γ − β_{0} − β_{1}}

for all γ ≥ β_{0} +β_{1}. (Again, without loss if generality, it suffices to consider the addition of β_{0} and β_{1}.) This is a special case of another identity commonly attributed to Rothe [12] (to be precise, it is the case α → β_{0}s, β → −1, γ → β_{1}s+β_{0}+β_{1}−1, n → γ−β_{0}−β_{1} of [9, Eq. (11)]), establishing the induction step in this case also. □

References

[1] D. Armstrong, Generalized noncrossing partitions and combinatorics of Coxeter groups, Mem. Amer. Math. Soc., vol. 202, no. 949, Amer. Math. Soc., Providence, R.I., 2009.

[2] D. Callan, Flexagons yield a curious Catalan number identity, preprint, arχiv:math/1005.5736.

[3] L. Carlitz, Some expansions and convolution formulas related to MacMahon’s master theorem, SIAM J. Math. Anal. 8 (1977), 320–336.

[4] E. C. Catalan, Note sur une équation aux différences finies, J. Math. Pure Appl. (1) 3 (1838), 508–516; 4 (1839), 95–99.

[5] S. Fomin and A. Zelevinsky, Y -systems and generalized associahedra, Ann. of Math. (2) 158 (2003), 977–1018.

[6] S. Fomin and N. Reading, Generalized cluster complexes and Coxeter combinatorics, Int. Math. Res. Notices 44 (2005), 2709–2757.

[7] N. Fuß, Solio quæstionis, quot modis polygonum n laterum in polygona m laterum, per diagonales resolvi quæat, Nova acta academiæ scientarium Imperialis Petropolitanæ 9 (1791), 243–251.

[8] I. J. Good, Generalizations to several variables of Lagrange’s expansion, with applications to stochastic processes, Proc. Cambridge Philos. Soc. 56 (1960), 367–380.

[9] H. M. Gould, Some generalizations of Vandermonde’s convolution, Amer. Math. Monthly 63 (1956), 84–91.

[10] C. Krattenthaler, Operator methods and Lagrange inversion: A unified approach to Lagrange formulas, Trans. Amer. Math. Soc. 305 (1988), 431–465.

[11] J. H. Przytycki and A. S. Sikora, Polygon dissections and Euler, Fuss, Kirkman, and Cayley numbers, J. Combin. Theory Ser. A 92 (2000), 68–76.

[12] H. A. Rothe, Formulae de serierum reversione demonstratio universalis signis localibus combinatorio-analyticorum vicariis exhibita, dissertatio academica, Leipzig, 1793.

[13] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, available electronically at

www.research.att.com/~njas/sequences/.

[14] R. P. Stanley, Enumerative Combinatorics, vol. 2, Cambridge University Press, Cambridge, 1999.

[15] R. P. Stanley, Catalan Addendum, continuation of Exercise 6.19 from [14]; available at

http://math.mit.edu/~rstan/ec/catadd.pdf.

[16] V. Strehl, Identities of Rothe–Abel–Schläfli–Hurwitz-type, Discrete Math. 99 (1992), 321–340.

[17] W. T. Tutte, A census of planar maps, Canad. J. Math. 15 (1963), 249–271.

Université Grenoble I, CNRS UMR 5582, Institut Fourier, 100 rue de maths, BP 74,

F-38402 St. Martin d’Hères, France. WWW: http://www-fourier.ujf-grenoble.fr/~bacher.

Fakultät für Mathematik, Universität Wien, Nordbergstrasze 15, A-1090 Vienna,

Austria. WWW: http://www.mat.univie.ac.at/~kratt.