Show that the number of Dyck$(2n)$-paths that avoid $\{(4k,0): 1 \leq k \leq n-1 \}$ is twice the number of Dyck $(2n-1)-$paths.

Question

A Dyck $n$-path is a path from $(0,0)$ to $(2n,0)$ using steps that move by $(1,1)$ or $(1,-1)$ without falling below x-axis. Show that the number of Dyck$(2n)$-paths that avoid $\{(4k,0): 1 \leq k \leq n-1 \}$ is twice the number of Dyck $(2n-1)-$paths.

My attempt: we know the number of Dyck $n$-path is the $n$th Catalan number, which is $C_{n}$. Now, the number of Dyck $2n$-path that does not touch $x=0$ line, hence does not touch all the points in $\{(4k,0): 1 \leq k \leq n-1 \}$ is $C_{n-1}$ because we can fix the second step as $(1,1)$ and second to last step as $(1,-1)$, and that is just the same as counting number of Dyck path from $(1,1)$ to $(4n-1,1)$.

So, I am able to count there is $C_{n-1}$ Dyck $2n$-path that does not touch all the points in $\{(4k,0): 1 \leq k \leq n-1 \}$ but I am wondering how to count the other $C_{n-1}$ path. Thanks.

Answer 1

Let $A_n$ be the number be the number of Dyck paths to $(4n,0)$ that avoid $\{(4k,0):1\le k\le n-1\}$.

First, show that $$ A_n=C_{2n}-\sum_{k=1}^{n-1} A_k C_{2(n-k)}\tag1 $$ This kind of equation is begging to be analyzed with generating functions.

To this end, let $A(x)=\sum_{n\ge 0} A_nx^n$, and let $E(x)=\sum_{n\ge 0} C_{2n}x^n$. Letting $$ C(x)=\sum_{n\ge 0} C_nx^n=\frac{1-\sqrt{1-4x}}{2x}, $$ $E(x)$ and $C(x)$ are related by $$ E(x)=\frac{C(x^{1/2})+C(-x^{1/2})}{2}=\frac{\sqrt{1+4x^{1/2}}-\sqrt{1-4x^{1/2}}}{4x^{1/2}}\tag2 $$

Equation $(1)$ translates to $$ A(x)=E(x)-(A(x)-1)(E(x)-1) $$ so $$ A(x)=2+\frac{-1}{E(x)}\tag3 $$ Combining $(2)$ and $(3)$, you determine $A(x)$. Then, letting $$ D(x)=\sum_{n\ge 0} C_{2n+1}x^n=\frac{C(x^{1/2})-C(-x^{1/2})}{2x^{1/2}} $$ you can relate $A(x)$ to $D(x)$. Namely, we will have $A(x)=2xD(x)+1$, which proves your claim.

Answer 2

I found a purely combinatorial proof, so I am posting a second answer.

---

Let $A$ be the set of Dyck paths to $(4n,0)$ which avoid $(4k,0)$ for $1\le k\le n-1$, and which touch the $x$ axis at least once strictly between $(0,0)$ and $(4n,0)$. You want to find a bijection from $A$ to the set of all Dyck paths to $(4n-2,0)$.

Given a path $P\in A$, we can break it up at the places it touches the $x$-axis. The result is something like $$ \def\u{\nearrow}\def\d{\searrow} P=\u,P_1,\d,\u,P_2,\d,\dots,\u,P_r,\d $$ where $P_1,\dots,P_r$ are smaller (possibly empty) Dyck paths. Since we assumed $P$ touches the $x$-axis at least once between its start and end, we always have $r\ge 2$.

Because $P$ cannot touch $(4k,0)$ for $1\le k\le n-1$, the first and last sections $P_1$ and $P_r$ will have even order (meaning the number of steps is a multiple of $4$), while the intermediate sections will all have odd order. I will denote this by $$ P=\u E_1\d \u D_1\d \u D_2\d\dots \u D_{r-2}\d \u E_2\d $$ I will describe the bijection from $A$ to the set of Dyck paths to $(4n-2,0)$ in several cases, based on the number of odd sections in this decompositions. $$ \begin{array}{c|c} \text{path in A} & \text{Dyck path of length $4n-2$} \\\hline\\ \u E_1 \d \u E_2\d & \u E_1 \d E_2 \\\\ \u E_1\d \u D_1 \d \u E_2 \d & \u \u E_1 \d E_2 \d D_1 \\\\ \u E_1\d \u D_1 \d\u D_2 \d \u E_2 \d & \u \u \u E_1 \d E_2 \d D_1 \d D_2 \\\\ \u E_1\d \u D_1 \d\u D_2 \d \u D_3 \d\u E_2 \d & \u \u \u \u E_1 \d E_2 \d D_1 \d D_2\d D_3 \\\\ \vdots & \vdots \end{array} $$ Hopefully the pattern is clear.

To verify this is a bijection, you just need to show that every Dyck path to $(4n-2,0)$ can be uniquely written in the one of the forms of the right column of that table. The inverse map is then given by matching the form of the given path in the right column, and rearranging it to make the corresponding entry in the left.

To prove every odd-order Dyck path can be written in the form of some path in the right column, first recall that every Dyck path $P$ can be uniquely decomposed as $$ P=\u P_1 \d P_2, $$ where $P_1$ and $P_2$ are smaller Dyck paths. Explicitly, $\u P_1 \d $ is the portion of $P$ up until the first time it touches the $x$-axis. In the case where $P$ has odd order, both of $P_1$ and $P_2$ will either both be even, or both be odd. That is, $P$ either looks like $$ \def \E{\text{even}}\def \D{\text{odd}} P = \qquad \u \E \d \E \qquad \text{or} \qquad \u \D \d \D $$ In the first case, we match which the first row of the right column, and are done. In the second, case we must break up the left odd part using the same procedure. The result is either $$ \u \color{blue}\D \d \D = \qquad \u \color{blue}{\u \E \d \E \d} \D \qquad \text{or}\qquad \u \color{blue}{\u \D \d \D \d} \D $$ Again, the case on the left matches the second row of the right column. We continue in this fashion, decomposing the leftmost odd path into $\u P_1 \d P_2$, until both $P_1$ and $P_2$ are even. This must happen eventually, since the process must stop. If the process stakes $r$ steps, then we match with the $r^{th}$ row of the right column.