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:
- Can anyone provide me some relevant references/papers?
- If 1. is not possible, is there a closed form formula of $F(\mathcal D_n)$ given $\mathcal D_n$?
- 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).
- If 1. to 3. are not possible, what can we say further about $F(\mathcal D_n)$? Does it encode something interesting?