Multivariate Fuss-Catalan numbers

Catalan triangle, binary trees, and Dyck paths

We recall in this section well-known results about Catalan numbers and ballot numbers.

are integers that appear in many combinatorial problems. These numbers first appeared in Euler’s work as the number of triangulations of a polygon by mean of non-intersecting diagonals. Stanley maintains a dynamic list of exercises related to Catalan numbers, including (at this date) 127 combinatorial interpretations.

Closely related to Catalan numbers are ballot numbers. Their name is due to the fact that they are the solution of the so-called ballot problem: we consider an election between two candidates A and B, which respectively receive $a>b$ votes. The question is: what is the probability that during the counting of votes, A stays ahead of B? The answer will be given below, and we refer to for Bertrand’s first solution, and to for André’s beautiful solution using the “reflection principle”.

Since our goal here is different, we shall neither define ballot numbers by the previous statement, nor by their explicit formula, but we introduce integers $B(n,k)$ defined for a positive integer $n$ and a nonnegative integer $k$ by the following conditions:

$\forall n>1$ and $0\leq k<n$, $B(n,k)=\sum_{i=0}^{k}B(n-1,i)$;

Observe that the recursive formula in the second condition is equivalent to:

We shall present the $B(n,k)$’s by the following triangular representation (zero entries are omitted) where moving down increases $n$ and moving right increases $k$.

\begin{array}[]{rrrrrr}1&&&&&\cr 1&1&&&&\cr 1&2&2&&&\cr 1&3&5&5&&\cr 1&4&9&14&14&\cr 1&5&14&28&42&42\cr\end{array}

The crucial observation is that computing the horizontal sums of these integers give : $1,\ 2,\ 5,\ 14,\ 42,\ 132$. We recognize the first terms of the Catalan series, and this intuition will be settled in Proposition 1.1, after introducing combinatorial objects.

A binary tree is a tree in which every internal node has exactly 2 sons. The number of binary trees with $n$ internal nodes is given by the $n$-th Catalan number. The nodes of the following tree are labelled to explain a bijection described in the next paragraph: internal nodes are labelled by letters and external nodes by numbers.

A Dyck path is a path consisting of steps $(1,1)$ and $(1,-1)$, starting from $(0,0)$, ending at $(2n,0)$, and remaining in the half-plane $y\geq 0$ (we shall sometimes say “remaining above the horizontal axis” in the same sense). The number of Dyck paths of length $2n$ is also given by the $n$-th catalan number. More precisely, the depth-first search of the tree gives a bijection between binary trees and Dyck paths: we associate to each external node (except the left-most one) a $(1,1)$ step and to each internal node a $(1,-1)$ step by searching recursively the left son, then the right son, then the root. As an example, we show below the Dyck path corresponding to the binary tree given above. The labels on steps correspond to those on the nodes of the tree.

An important parameter in our study will be the length of the right-most sequence of $(1,-1$) of the path. This parameter equals 2 in our example. Observe that under the correspondence between paths and trees, this parameter corresponds to the length of the right-most string of right sons in the tree. We shall use the expressions last down sequence and last right string, for these parts of the path and of the tree.

Now we come to the announced result. It is well-known and simple, but is the starting point of our work.

For $n$ a positive integer, we have the following equality:

Let us denote by ${\mathcal{C}}_{n,k}$ the set of Dyck paths of length $2n$ with a last down sequence of length equal to $n-k$.

We shall prove that $B(n,k)$ is the cardinality of ${\mathcal{C}}_{n,k}$.

The proof is done recursively on $n$. If $n=1$, this is trivial. If $n>1$, let us suppose that $B(n-1,k)$ is the cardinality of ${\mathcal{C}}_{n-1,k}$ for $0\leq k<n-1$. Let us consider an element of ${\mathcal{C}}_{n,k}$. If we erase the last step $(1,1)$ and the following step $(1,-1)$, we obtain a Dyck path of length $2(n-1)$, with a last decreasing sequence of length $n-1-l$ with $l\leq k$. If we keep track of the integer $k$, we obtain a bijection between ${\mathcal{C}}_{n,k}$ and $\cup_{l\leq k}{\mathcal{C}}_{n-1,l}$. We mention that this process is very similar to the ECO method .

This is a combinatorial proof of Proposition 1.1. ∎

Remark 1.2. The integers $B(n,k)$ are known as ballot numbers and are given by the explicit formula:

This expression can be obtained shortly by checking the recurrence (1.1). We can alternatively use the reflection principle (see for a clear presentation), or the cycle lemma (cf. ), which will be used in the next sections to obtain a formula in the general case.

The expression (1.2) constitutes a solution to the ballot problem. For this, we use a classical interpretation in terms of paths: we represent a vote for A by an up step, and a vote for B by a down step. The total number of countings of votes, or of paths from $(0,0)$ to $(a+b,a-b)$, is given by the binomial ${a+b\choose a}$. The countings such that A stays ahead of B correspond to paths remaining above the horizontal axis. Their number is given by $B(a,b)$. This implies that the probability asked for at the beginning of this section is $\frac{a-b}{a+b}$.

Of course , we could have used expression (1.2) to prove Proposition 1.1 by a simple computation, but our proof explains more about the combinatorial objects and can be adapted to ternary trees in the next section.

It should be mentionned here that our study of multivariate Fuss-Catalan has nothing to do with the many-candidate ballot problem, as considered for example in or . In particular, the multivariate ballot numbers considered in these papers do not sum to the Fuss-Catalan numbers $C_{p}(n)=\frac{1}{(p-1)n+1}{pn\choose n}$. Conversely, the numbers studied in the present article do not give any answer to the generalized ballot problem.

We easily observe that a Riordan array with the first two columns $M_{0}(x)$ and $M_{1}(x)$ of our Catalan array is relative to $g(x)=\frac{1}{1-x}$ and $f(x)=\frac{x}{1-x}$, which gives the Pascal triangle.

In fact, the Riordan array relative to $g(x)={\bf C}(x)=\sum C(n)x^{n}$ and $f(x)=x\,{\bf C}(x)$ gives the ballot numbers, but requires knowledge of the Catalan numbers.

Fuss-Catalan tetrahedron and ternary trees

This section, which is the heart of this work, is the study of a 3-dimensional analogue of the Catalan triangle of the previous section. That is we consider exactly the same recurrence, and let the array grow, not in 2, but in 3 dimensions. More precisely, we introduce the sequence $B_{3}(n,k,l)$ indexed by a positive integer $n$ and nonnegative integers $k$ and $l$, and defined recursively by:

$\forall n>1$, $k+l<n$, $B_{3}(n,k,l)=\sum_{0\leq i\leq k,0\leq j\leq l}B_{3}(n-1,i,j)$;

Observe that the recursive formula in the second condition is equivalent to:

and this expression can be used to make some computations lighter, but the presentation above explains more about the generalization of the definition of the ballot numbers $B(n,k)$.

Because of the planar structure of the sheet of paper, we are forced to present the tetrahedron of $B_{3}(n,k,l)$’s by its sections with a given $n$.

n=1\longrightarrow\left[\begin{array}[]{r}1\end{array}\right]

n=2\longrightarrow\left[\begin{array}[]{rr}1&1\cr 1&\end{array}\right]

n=3\longrightarrow\left[\begin{array}[]{rrr}1&2&2\cr 2&3&\cr 2&&\end{array}\right]

n=4\longrightarrow\left[\begin{array}[]{rrrr}1&3&5&5\cr 3&8&10&\cr 5&10&&\cr 5&&&\end{array}\right]

n=5\longrightarrow\left[\begin{array}[]{rrrrr}1&4&9&14&14\cr 4&15&30&35&\cr 9&30&45&&\cr 14&35&&&\cr 14&&&&\end{array}\right]

It is clear that $B_{3}(n,k,0)=B_{3}(n,0,k)=B(n,k)$. The reader may easily check that when we compute $\sum_{k,l}B_{3}(n,k,l)$, we obtain: $1,\ 3,\ 12,\ 55,\ 273$. These integers are the first terms of the following sequence (cf. ):

This fact will be proven in Proposition 2.1.

2. Combinatorial interpretation

FussNikolai Fuss (Basel, 1755 – St Petersburg, 1826) helped Euler prepare over 250 articles for publication over a period on about seven years in which he acted as Euler’s assistant, and was from 1800 to 1826 permanent secretary to the St Petersburg Academy.-Catalan numbers (cf. ) are given by the formula

and $C_{3}(n)$ appear as order-3 Fuss-Catalan numbers. The integers $C_{3}(n)$ are known to count ternary trees, ie. trees in which every internal node has exactly 3 sons.

Ternary trees are in bijection with 2-Dyck paths, which are defined as paths from $(0,0)$ to $(3n,0)$ with steps $(1,1)$ and $(1,-2)$, and remaining above the line $y=0$. The bijection between these objects is the same as in the case of binary trees, ie. a depth-first search, with the difference that here an internal node is translated into a $(1,-2)$ step. To illustrate this bijection, we give the path corresponding to the previous example of ternary tree:

We shall consider these paths with respect to the position of their down steps. The height of a down step is defined as the height of its end-point. Let ${\mathcal{D}}_{n,k,l}$ denote the set of 2-Dyck paths of length $3n$, with $k$ down steps at even height and $l$ down steps at odd height, excluding the last seqence of down steps. By definition, the last sequence of down steps is of length $n-k-l$.

Moreover, $B_{3}(n,k,l)$ is the cardinality of ${\mathcal{D}}_{n,k,l}$.

Let $k$ and $l$ be fixed. Let us consider an element of ${\mathcal{D}}_{n,k,l}$. If we cut this path after its $(2n-2)$-th up step, and complete with down steps, we obtain a 2-Dyck path of length $3(n-1)$ (see figure below). It is clear that this path is an element of ${\mathcal{D}}_{n,i,j}$ for some $i\leq k$ and $j\leq l$. We can furthermore reconstruct the original path from the truncated one, if we know $k$ and $l$. We only have to delete the last sequence of down steps (here the dashed line), to draw $k-i$ down steps, one up step, $l-j$ down steps, one up step, and to complete with down steps. This gives a bijection from ${\mathcal{D}}_{n,k,l}$ to $\cup_{0\leq i\leq k,0\leq j\leq l}{\mathcal{D}}_{n-1,i,j}$, which implies Proposition 2.1.

Remark 2.2. It is interesting to translate the bi-statistic introduced on 2-Dyck paths to the case of ternary trees. As previously, we consider the depth-first search of the tree, and shall not consider the last right string. We define ${\mathcal{T}}_{n,k,l}$ as the set of ternary trees with $n$ internal nodes, $k$ of them being encountered in the search after an even number of leaves and $l$ after and odd number of leaves. By the bijection between trees and paths, and Proposition 2.1, we have that the cardinality of $T_{n,k,l}$ is $B_{3}(n,k,l)$.

Remark 2.3. It is clear from the definition that:

But this fact is not obvious when considering trees or paths, since the statistics defined are not clearly symmetric. To explain this, we can introduce an involution on the set of ternary trees which sends an element of ${\mathcal{T}}_{n,k,l}$ to ${\mathcal{T}}_{n,l,k}$. To do this, we can exchange for each node of the last right string its left and its middle son, as in the following picture. Since the number of leaves of a ternary tree is odd, every “even” node becomes an odd one, and conversely.

3. Explicit formula

Now a natural question is to obtain explicit formulas for the $B_{3}(n,k,l)$. The answer is given by the following proposition.

We use a combinatorial method to enumerate ${\mathcal{D}}_{n,k,l}$. The method is a variation of the cycle lemma (called “penetrating analysis” in ).

If we forget the condition of “positivity” (ie. the path remains above the line $y=0$), and cut the last down sequence, a path consists in:

at even height: $n$ up steps, and $k$ down steps;

at odd height: $n$ up steps and $l$ down steps.

An important remark is to remember that an element of ${\mathcal{D}}_{n,k,l}$ has an up step just before the last sequence of down steps! If we suppose that all these steps are distinguished, we obtain:

$\frac{(n+k)!}{n!k!}$ choices for even places;

$\frac{(n-1+l)!}{(n-1)!l!}$ choices for odd places (we cannot put any odd down step after the last odd step).

Now we group the paths which are “even permutations” of a given path $P$. By even permutations, we mean cycle permutations which preserve the parity of the height of the steps.

We want to prove that the proportion of elements of ${\mathcal{D}}_{n,k,l}$ in any even orbit (i.e. in any orbit under even permutations) is given by $\frac{n-k-l}{n+k}$.

We suppose first that the path $P$ is acyclic (as a word): $P$ cannot be written as $P=U^{p}$ with $U$ a word in the two letters $(1,1)$ and $(1,-2)$. It is clear that such a path gives $n+k$ different even permutations. Now we have to keep only those which give elements of ${\mathcal{D}}_{n,k,l}$. To do this we consider the concatenation of $P$ and $P^{\prime}$, which is a duplicate of $P$.

The cyclic permutations of $P$ (not necessarily even) are the subpaths of $P+P^{\prime}$ of horizontal length $2n+k+l$. The number of such paths that remain above the horizontal axis, and end with an up step, is the number of (up) steps of $P$ in the light of an horizontal light source coming from the right. The only transformation is to put the illuminated up step at the end of the path. The number of illuminated up steps is $2n-2k-2l$, since every down step puts two up steps in the shadow. Among these $2n-2k-2l$ permutations, only half are even (observe that the set of heights of the illuminated steps is an interval). Thus $n-k-l$ paths among the $n+k$ elements of the orbit are in ${\mathcal{D}}_{n,k,l}$.

Now we observe that if $P$ is $p$-cyclic, then its orbit has $p$ times less elements, and we obtain $p$ times fewer different paths, whence the proportion of elements of elements of ${\mathcal{D}}_{n,k,l}$ in this orbit is:

Finally, we obtain that the cardinality of ${\mathcal{D}}_{n,k,l}$ is

Remark 2.5. The equation (2.3) is of course symmetric in $k$ and $l$:

Remark 2.6. I made the choice to present a combinatorial proof of Proposition 2.2. The interest is to show how these formulas are obtained, and to allow easy generalizations (cf. the next section). It is also possible to check directly the recurrence (2.1).

4. Generating function

Let $F$ denote the following generating series:

In this expression, the term “1” corresponds to the empty 2-Dyck path. Thus $F$ is the generating series of 2-Dyck paths with respect to their length (variable $t$), their number of down steps at even height –excluding the last down sequence– (variable $x$), and their number of down steps at odd height (variable $y$).

ie. $G$ is the generating function of 2-Dyck paths with respect to their length, to the number of down steps at even height -including the last down sequence- and to the number of down steps at odd height.

To obtain equations for $F$ and $G$, we decompose a non-empty 2-Dyck path by looking at two points: $\alpha$, defined as the last return to the axis (except the final point $(3n,0)$), and $\beta$ defined as the last point at height 1 after $\alpha$. This gives the following decomposition of a 2-Dyck path

with $P_{1}$, $P_{2}$, $P_{3}$ any 2-Dyck path (maybe empty).

By observing that the up steps after $\alpha$ and $\beta$ change the parity of the height, this gives the two following equations :

By permuting the variables $x$ and $y$ in (2.7), we obtain

and we can eliminate $G(t,y,x)$ from (2.7) and (2.8) to obtain the following result.

The generating function $F$ of the $B_{3}$’s is given by:

where $G(t,x,y)$ is a solution of the algebraic equation

An alternate approach to the generating function is to use formula 2.3 to obtain what MacMahon called a “redundant generating function “ (cf. ), since it contains terms other than those which are combinatorially significant.

To do this we extend the recursive definition of $B_{3}(n,k,l)$ as follows: we define $B^{\prime}_{3}(n,k,l)$ for integers $n>0$, and $k,l\geq 0$ by:

Of course when $k+l>n$, the integer $B^{\prime}_{3}(n,k,l)$ is negative.

As an example, here is the “section” of the array of $B^{\prime}_{3}(n,k,l)$ with $n=3$.

\left[\begin{array}[]{cccccc}1&2&2&0&-5&\cdots\cr 2&3&0&-10&-30&\cdots\cr 2&0&-12&-40&-90&\cdots\cr 0&-10&-40&-100&-200&\cdots\cr-5&-30&-90&-200&-375&\cdots\cr\vdots&\vdots&\vdots&\vdots&\vdots&\ddots\end{array}\right]

The equation (2.9) is equivalent to the following recursive definition: $\forall n\leq 0$ or $k,l<0,\ B^{\prime}_{3}(n,k,l)=0$ and

The interest of this presentation is to give a simple (rational!) generating series. Indeed, it is quite simple to deduce from the recursive definition of $B^{\prime}_{3}(n,k,l)$ that:

This formula then encodes the $B_{3}(n,k,l)$ since $\forall k+l<n,\ B_{3}(n,k,l)=B^{\prime}_{3}(n,k,l)$.

Fuss-Catalan p𝑝p-simplex and p𝑝p-ary trees

The aim of this final section is to present an extension of the results of Section 2 to $p$-dimensional recursive sequences. In the same spirit, we define the sequence $B_{p}(n,k_{1},k_{2},\dots,k_{p-1})$ by the recurrence:

$\forall n>1$ and $0\leq k_{1}+k_{2}+\cdots+k_{p-1}<n$,

$\forall k_{1}+k_{2}+\cdots+k_{p-1}\geq n$, $B_{p}(n,k_{1},k_{2},\dots,k_{p-1})=0$.

Every result of Section 2 extends to general $p$. We shall only give the main results, since the proofs are straightforward generalizations of the proofs in the previous section.

The integers $C_{p}(n)$ are order-$p$ Fuss-Catalan numbers and enumerate $p$-ary trees, or alternatively $p$-Dyck paths (the down steps are $(1,-p)$). In this general case, the recursive definition of $B_{p}(n,k_{1},k_{2},\dots,k_{p-1})$ gives rise to $p-1$ statistics on trees and paths analogous to those defined in section 3.

Remark 3.2. By the same method as in the previous section, it is possible to obtain an explicit formula for these multivariate Fuss-Catalan numbers:

Acknowledgement. The author is very grateful to referees (and in particular to the anonymous “Referee 3”) for valuable remarks and corrections.

References