User:Aspaine/sandbox

Proofs of the general formula for $C_{m}(n,k)$

Proof 1

This proof involves extension of the Andres Reflection method as used in the second proof for the Catalan number. The following shows how every path from the bottom left $(0,0)$ to the top right $(k,n)$ of the diagram that crosses the constraint $n-k+m-1=0$ can also be reflected to the end point $(n+m,k-m)$.

We consider three cases to determine the number of paths from $(0,0)$ to $(k,n)$ that do not cross the constraint:

(1) when $m>k$ the constraint cannot be crossed, so all paths from $(0,0)$ to $(k,n)$ are valid, i.e. $C_{m}(n,k)=\left({\begin{array}{c}n+k\\k\end{array}}\right)$.

(2) when $k-m+1>n$ it is impossible to form a path that does not cross the constraint, i.e. $C_{m}(n,k)=0$.

(3) when $m\leq k\leq n+m-1$, then $C_{m}(n,k)$ is the number of 'red' paths $\left({\begin{array}{c}n+k\\k\end{array}}\right)$ minus the number of 'yellow' paths that cross the constraint, i.e. $\left({\begin{array}{c}(n+m)+(k-m)\\k-m\end{array}}\right)=\left({\begin{array}{c}n+k\\k-m\end{array}}\right)$.

Thus the number of paths from $(0,0)$ to $(k,n)$ that do not cross the constraint $n-k+m-1=0$ is as indicated in the formula in the previous section "Generalization".

Proof 2

Firstly, we confirm the validity of the recurrence relation $C_{m}(n,k)=C_{m}(n-1,k)+C_{m}(n,k-1)$ by breaking down $C_{m}(n,k)$ into two parts, the first for XY combinations ending in X and the second for those ending in Y. The first group therefore has $C_{m}(n-1,k)$ valid combinations and the second has $C_{m}(n,k-1)$. Proof 2 is completed by verifying the solution satisfies the recurrence relation and obeys initial conditions for $C_{m}(n,1)$ and $C_{m}(1,k)$.