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?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.