Number of Dyck paths with maximal odd sequence of $(1,-1)$ ending on the $x$-axis

Question

A Dyck path from $(0,0)$ to $(2n+2,0)$ is a lattice path with steps $(1,1)$ and $(1,-1)$, never falling below the $x$-axis.

Find the number of Dyck paths from $(0,0)$ to $(2n+2,0)$ such that any maximal sequence of consecutive steps $(1,-1)$ ending on the $x$-axis has odd length.

The above question is from Richard Stanley's Enumerative Combinatorics. In fact, a solution is given by Stanley, but I am not sure why we should proceed like that.

Let $A(x)=x+x^3+2x^4+6x^5+\cdots$ (respectively, $B(x)=x^2+x^3+3x^4+8x^5+\cdots$) be the generating function for Dyck paths from $(0,0)$ to $(2n, 0)$ such that the path only touches the $x$-axis at the beginning and end, and the number of steps $(1,-1)$ at the end is odd (respectively, even).

How do we obtain these two generating functions? Why does it suffice to consider the paths that touch the $x$-axis at the beginning and the end?

Let $C(x)=1+x+2x^2+5x^3+\cdots$ be the generating function for all Dyck paths from $(0,0)$ to $(2n,0)$. Note that the coefficients are Catalan numbers. It is easy to see that $A=x(1+CB)$ and $B=xCA$. Solving for $A$ gives $$A=\frac{x}{1-x^2C^2}.$$

Although I may not understand how to come up with $A$ and $B$, this part is simply computation.

The generating function we want is $$\frac{1}{1-A}.$$

I again do not understand this part. Why do we have such a generating function?

The above simplifies to $1+xC$, which means that the required number follows the Catalan numbers.

Any help for the above question is appreciated.

Answer 1

Approach: The idea is to analyse specific types of Dyck paths which can be used as building blocks and to find generating functions for them. These generating functions will be used to specify the generating function we are actually looking for.

We put the focus on Dyck paths of length $2n$, starting at $(0,0)$ and ending at $(2n,0)$ which do not touch the x-axis between the start and end point. The number $n$ specifies the number of up steps which is equal to the number of down steps.

It is convenient to split these Dyck paths in paths which end with an odd number of down steps and those which end with an even number of down steps.

Generating functions A(x) and B(x)

Let's denote the generating function with an odd number of terminating down steps $A(x)$. In order to get a first impression of this function we look for the number of Dyck paths counted by $A(x)$ for small lenghts $2n$.

In the following we encode up steps with u and down steps with d. So, all paths counted by $A(x)$ start with an $u$ and end with an odd sequence of $d$'s.

• $n=2$: We get one path $\color{blue}{ud}$

• $n=4$: We get no path, since $udud$ touches the $x$-axis between start and end point and $uudd$ does not end with an odd sequence.

• $n=6$: We consider the pattern $\color{blue}{u(..)ddd}$ and obtain one path $\color{blue}{uuuddd}$.

• $n=8$: We consider the pattern $\color{blue}{uu(..)uddd}$. Since we have to start with two $u$'s in order to not touch the $x$-axis in between and we have due to the same reason to terminate with three $d$'s, which implies that there is an up step $u$ before them. We find the paths $\color{blue}{uu(ud)uddd}$ and $\color{blue}{uu(du)uddd}$.

• $n=10$: We consider the path $\color{blue}{uuuuuddddd}$ and the pattern $\color{blue}{uu(....)uddd}$ giving $1+\left(\binom{4}{2}-1\right)=6$ Dyck paths. Note, that we have to exclude $uu(dduu)uddd$ to not touch the $x$-axis in between.

We conclude

\begin{align*} A(x)=x+x^3+2x^4+6x^5+\cdots \end{align*}

With similar reasoning we can find the first coefficients of the generating function $B(x)$ counting all Dyck words which do not touch the $x$-axes in between and which terminate with an even number of down steps.

\begin{align*} B(x)=x^2+x^3+3x^4+8x^5+\cdots \end{align*}

$$ $$

Relationship $A(x),B(x)$ with $C(x)$:

We denote with $C(x)$ the generating function of the Catalan numbers $C_n=\frac{1}{n+1}\binom{2n}{n}$ \begin{align*} C(x)=\sum_{n=0}^{\infty}C_nx^n=\frac{1}{2x}\left(1-\sqrt{1-4x}\right) \end{align*} The coefficients $C_n$ give the number of all Dyck paths of length $2n$.

Let's look at the expression

\begin{align*} C(x)A(x)&=\left(\sum_{n=0}^{\infty}C_nx^n\right)\left(\sum_{n=0}^{\infty}A_nx^n\right)\\ &=\sum_{n=0}^{\infty}\left(\sum_{k=0}^{n}C_kA_{n-k}\right)x^n \end{align*}

If we consider e.g. the coefficient of $x^4$ we see \begin{align*} C_0A_4+C_1A_3+C_2A_2+C_3A_1+C_4A_0 \end{align*}

So, the coefficient of $x^4$ specifies the number of all Dyck paths $C_k$ of length $k\, (0\leq k \leq 4)$ concatenated with all specific Dyck paths $A_{4-k}$.

We conclude: The multiplication $C(x)A(x)$ specifies the number of all Dyck paths which terminate with an odd sequence of down steps. Note, here are also Dyck paths which touch the $x$-axis thanks to the left multiplication with $C(x)$ and the termination by an odd number of down steps is guaranteed by the multiplication with $A(x)$.

It follows, that \begin{align*} B(x)=xC(x)A(x) \end{align*} since the multiplication with $x$ represents a starting up step $u$ and an ending down step $d$. This guarantees that we end with an even number of down steps and it is also assured, that we do not touch the $x$-axis in between.

With a similar reasoning we see that \begin{align*} A(x)=x+xC(x)B(x) \end{align*} whereby the summand $x$ represents the Dyck path $\color{blue}{ud}$.

$$ $$

Concatenation of building blocks:

If we consider the geometric series

\begin{align*} G(x)=\frac{1}{1-A(x)}=1+A(x)+A^2(x)+A^3(x)+\cdots \end{align*}

we can think of $A^k(x)$ as counting the concatenation of $k$ Dyck paths each terminating with an odd number of down steps.

We observe that each $A^k(x)$ counts Dyck paths, which touch the $x$-axis between start and end point, $k-1$ times. So, the geometric series $G(x)$ provides us with all Dyck paths of the wanted shape.