> [!NOTE] Lemma > Let $n$ be a [[Natural Numbers|natural number]] and $C_{n}$ the $n$th [[Catalan Numbers|Catalan number]]. Then $C_{n}= {2n \choose n } - {2n \choose n-1} = \frac{1}{n+1} {2n \choose n}.$ ###### Bijective Proof using Dyck Paths We use the fact that $C_{n}$ [[Catalan Numbers Count Monotonic Lattice Paths|counts the number of north-east lattice paths from (0,0) to (n,n) that never cross the diagonal]]. We know the number of lattice paths from $(0,0)$ to $(n,n)$ is given by ${2n \choose n}$. Let $P$ be a path that crosses above the diagonal. Then reflecting everything after the first point where $P$ touches the line that is $1$ unit above the diagonal gives a path from $(0,0)$ to $(n-1,n+1)$. To see that this map gives a bijection $\Set\begin{array}{1} \text{non-Dyck paths from} \\ \text{ $(0,0)$ to $(n,n)$}\end{array} \rightarrow \Set\begin{array}{1} \text{Paths from} \\ \text{ $(0,0)$ to $(n-1,n+1)$}\end{array},$note that its inverse map takes a path $Q$ from $(0,0)$ to $(n-1,n+1)$ and reflects everything after first point where $Q$ touches the line that is $1$ unit above the diagonal. We conclude that $\begin{align} \# \Set\begin{array}{1} \text{non-Dyck paths from} \\ \text{ $(0,0)$ to $(n,n)$}\end{array} &= \# \Set\begin{array}{1} \text{Paths from} \\ \text{ $(0,0)$ to $(n-1,n+1)$}\end{array} \\ &= {2n \choose n-1} \end{align}$and so $\begin{align} C_{n} &= {2n \choose n } - {2n \choose n-1} \\ &= \frac{(2n)!}{n!n!} - \frac{(2n)!}{(n-1)!(n+1)!} \\ &= \frac{(2n)!(n+1) - (2n)!n }{(n+1)!n!} \\ &= \frac{(2n)!}{n!(n+1)!} = \frac{1}{n+1} {2n \choose n}. \end{align}$ ###### Proof (Taylor Expansion of its OGF)