Lesson 4

First Proof: Reflection and Bad Paths.

Let us count the number of paths from \((0,0)\) to \((n,n)\) that do not enter the upper triangle (where each step is either a step to the right or upward). These are known as Dyck paths. It is easy to see that there is a natural bijection between such paths and valid bracket sequences.

The total number of paths from \((0,0)\) to \((n,n)\) is \(\binom{2n}{n}\). Below, we will focus on counting the number of bad such paths, i.e., paths that enter the upper triangle. Such paths touch or cross the line \((0,1)-(n-1,n)\), shown dashed in the figure below.

Consider the last moment where the bad path crosses the dashed line, and reflect the entire part of the bad path starting from this moment relative to this line. We obtain a path from \((0,0)\) to \((n-1,n+1)\).

An important observation: bad paths from \((0,0)\) to \((n,n)\) are in one-to-one correspondence with all paths from \((0,0)\) to \((n-1,n+1)\), and the mapping we considered establishes this correspondence (yes, we want to use the bijection rule). Indeed, any path from \((0,0)\) to \((n-1,n+1)\) must cross the dashed line (it starts below the line and ends above); reflecting its part after the last crossing, we obtain a bad path from \((0,0)\) to \((n,n)\). Performing the same operation on the resulting path, we obtain the original path, so this is indeed a bijection.

Thus, the number of bad paths equals \(\binom{2n}{n+1}\). Therefore, \[\begin{align*}C(n)&=\binom{2n}{n}-\binom{2n}{n+1}=\\&=\binom{2n}{n}-\frac{(2n)!}{(n+1)!(n-1)!}=\\&=\binom{2n}{n}-\frac{n}{n+1}\cdot \binom{2n}{n}=\\&=\frac{1}{n+1}\cdot \binom{2n}{n}\ .\end{align*}\]