# A generating function involving extensions and reductions of Dyck words

This is a followup question in a combinatoric proof of Involving Catalan numbers. The main ingredient of the post is to prove the following equality involving Catalan numbers:

$$\sum_{j=0}^n (-1)^j\binom{2n-j}{j}C_n = 0.$$

The combinatoric proof involves extending and reducing $2n$-Dyck words.

Backgrounds and Settings:

• A $2n$-Dyck word is a sequence of length $2n$, with $n$ letter $A$'s and $n$ letter $B$'s, such that every sub-word starting from the beginning always contains at least as many $A$'s than $B$'s. It is well known that the number of $2n$-Dyck words is the Catalan number $C_n$.

For instance, if $n=3$, $C_n = 5$, and there are five 6-Dyck words: $AAABBB$, $AABABB$, $AABBAB$, $ABAABB$, and $ABABAB$.

• Extending $2(n-j)$-Dyck words to form $2n$-Dyck words:

Starting from a $2(n-j)$-Dyck word, $\mathcal D_{n-j}$, we can form a $2n$-Dyck word by the following:

First start with $j$ letter $A$'s. Then select $j$ empty slots from the remaining $2n-j$ slots and put in letter $B$'s. There are $\binom{2n-j}j$ possible choices for the slots. Finally, in the remaining $2(n-j)$ slots, put in the Dyck word $\mathcal D_{n-j}$ in the correct order.

Example: From the 4-Dyck word $ABAB$, we can extend into a 6-Dyck word in 5 ways: $AB\color{red}{ABAB}$, $A\color{red}{A}B\color{red}{BAB}$, $A\color{red}{AB}B\color{red}{AB}$, $A\color{red}{ABA}B\color{red}{B}$, and $A\color{red}{ABAB}B$.

• Generating functions associated with a $2n$-Dyck word $\mathcal D_{n}$:

Let $\mathcal D_n$ be a $2n$-Dyck word and $0 \leq j \leq n$, we define $\mathcal D_{n,j}$ be the number of ways $\mathcal D_n$ can be extended from some $2(n-j)$-Dyck word. The associated generating function is defined as

$\displaystyle F(\mathcal D_n) = \sum_{j=0}^n \mathcal D_{n,j}x^j$.

Example: Let $\mathcal D_4 = AAABBABB$.

• $\mathcal D_{4,0} = 1$: the extension is $\color{red}{AAABBABB}$ (trivial).

• $\mathcal D_{4,1} = 4$: the extensions are $A\color{red}{AA}B\color{red}{BABB}$, $A\color{red}{AAB}B\color{red}{ABB}$, $A\color{red}{AABBA}B\color{red}{B}$, and $A\color{red}{AABBAB}B$.

• $\mathcal D_{4,2} = 5$: the extensions are $AA\color{red}{A}BB\color{red}{ABB}$, $AA\color{red}{A}B\color{red}{BA}B\color{red}{B}$, $AA\color{red}{A}B\color{red}{BAB}B$, $AA\color{red}{AB}B\color{red}{A}B\color{red}{B}$, and $AA\color{red}{AB}B\color{red}{AB}B$.

• $\mathcal D_{4,3} = 2$: the extensions are $AAABB\color{red}{A}B\color{red}{B}$ and $AAABB\color{red}{AB}B$.

• So $F(\mathcal D_4) = 1 + 4x + 5x^2 + 2x^3 = (1+x)^2(1+2x)$.

Example: The generating function of all $C_4 = 14$ 8-Dyck words are:

\begin{aligned} F(AAAABBBB) &= 1 + 4x + 6x^2 + 4x^3 + x^4 = (1+x)^4;\\ F(AAABABBB) &= 1 + 4x + 6x^2 + 3x^3 = (1+x)(1+3x+3x^2);\\ F(AAABBABB) &= 1 + 4x + 5x^2 + 2x^3 = (1+x)^2(1+2x);\\ F(AAABBBAB) &= 1 + 3x + 3x^2 + x^3 = (1+x)^3;\\ F(AABAABBB) &= 1 + 4x + 3x^2 = (1+x)(1+3x);\\ F(AABABABB) &= 1 + 4x + 3x^2 = (1+x)(1+3x);\\ F(AABABBAB) &= 1 + 3x + 2x^2 = (1+x)(1+2x);\\ F(AABBAABB) &= 1 + 2x + x^2 = (1+x)^2;\\ F(AABBABAB) &= 1 + 2x + x^2 = (1+x)^2;\\ F(ABAAABBB) &= 1 + x;\\ F(ABAABABB) &= 1 + x;\\ F(ABAABBAB) &= 1 + x;\\ F(ABABAABB) &= 1 + x;\\ F(ABABABAB) &= 1 + x. \end{aligned}

• First observations: Let $\mathcal D_n$ be a $2n$-Dyck word.

• If the first chunk of $A$ consists of $d$ $A$'s, then $\deg F(\mathcal D_n) = d$.

• If the first chunk of $B$ consists of $c$ $B$'s, then $(1+x)^c|F(\mathcal D_n)$. (This is actually what is needed to prove the equation in the top of the post).

• If the first $2(n-j)$ letters of $\mathcal D_n$ and $\mathcal D_{n-j}'$ coincides, then $F(\mathcal D_n) = F(\mathcal D_{n-j}')$.

I tried to relate similar Dyck words or used some recurrence relations, but nothing fruitful happened further...

My Questions:

1. Can anyone provide me some relevant references/papers?
2. If 1. is not possible, is there a closed form formula of $F(\mathcal D_n)$ given $\mathcal D_n$?
3. If 1. and 2. are not possible, what is a better way to calculate $F(\mathcal D_n)$ given $\mathcal D_n$? (Calculating them by hand is awful, although it should be easy to replace it by a computer).
4. If 1. to 3. are not possible, what can we say further about $F(\mathcal D_n)$? Does it encode something interesting?