Combinatorics – Counting Lattice Paths from (0,0) to (2n,2n) Avoiding Odd Points

combinatoricsdiscrete mathematicsrecursion

How many lattice paths are there from $(0,0)$ to $(2n,2n)$ that do not go through one of the points $(2i-1,2i-1)$ for $i=1,\dots,n$?

My idea is to count the number of total lattice paths one can take from $(0,0)$ to $(2n,2n)$. There are ${4n \choose 2n}$ such paths. Then subtract the number of paths that are not valid. In counting these, I reasoned that we must avoid the "odd points" inside the grid with height and width of $2n$. I counted the number of paths that take these of points to be ${4 \choose 2}^{n-1}{2 \choose 1}{2 \choose 1}$ with the reasoning that from $(0,0)$ to $(1,1)$, there are ${2 \choose 1}$ paths, similarly for $(2n-1,2n-1)$ to $(2n,2n)$. Now, there are a total of $n-1$ "odd points" we consider and the number of paths from say $(1,1)$ to $(3,3)$ is ${4 \choose 2}$, we consider $n-1$ such scenarios. But in comparing my result, it is wrong, I seem to be undercounting the number of invalid paths that I need to subtract from the total paths.


Edit: The result is expected to be the Catalan numbers of the form $C_{2n+1}$.

Edit 2: I've reworked the problem to make the first couple of terms match $C_{2n+1}$, by removing from the total number of lattice paths the invalid paths (a sum of all the possible cases by which we choose how many and which odd points our invalid path has gone through). It seems to be some recursive function, any ideas how to express this recursively?

Best Answer

Yeah, there is a nice way to do it. This looks long, but it's because I stated everything rigorously. If you draw pictures while reading this, it'll make a LOT more sense.

Let $f(2n)$ denote the number of paths from $(0, 0)$ to $(2n, 2n)$ not crossing through a point of the form $(2k+1, 2k+1)$. I claim that $f(2n) = C_{2n}$, where $C_{2n}$ is the $2n$-th Catalan number.

A well known property of Catalan number $C_{n}$ is that it satisfies the following recursion formula: $$ C_{n+1} = \sum_{i=0}^{n} C_i C_{n-i} \tag{1}$$ Another well known property is that it counts the number of paths from $(0,0)$ to $(2n,2n)$ which never go above the line $y=x$.

I'll prove the result by induction. Notice it's true for a base case of $n = 0$. Now, suppose the result is true for $f(0), f(2), \dots, f(2n-2)$.

To count $f(2n)$, we do casework on the first point of the form $(2k, 2k)$ our path goes through (other than $(0, 0)$). This casework covers all paths since all paths end up at $(2n, 2n)$. Suppose the first such point is $(2k, 2k)$. WLOG on our first step, we went $(0, 0) \to (1, 0)$, we'll multiply by $2$ in our final count. Then we must also end with $(2k, 2k-1) \to (2k, 2k)$. It remains to count the number of paths which go from $(1, 0)$ to $(2k, 2k-1)$ without passing any point of the form $(2k, 2k)$. This is just $C_{2k-1}$! After this, there are $f(2n-2k)$ ways to finish up the path $(2k, 2k) \to (2n, 2n)$. Therefore, we have $$f(2n) = \sum_{k=1}^{n} 2 \cdot C_{2k-1} f(2n-2k)$$ By the inductive hypothesis, $f(2n-2k) = C_{2n-2k}$, so we really have $$f(2n) = \sum_{k=1}^{n} 2 \cdot C_{2k-1} C_{2n-2k} = \sum_{k=1}^n C_{2k-1}C_{2n-2k} + \sum_{k=1}^nC_{2k-1}C_{2n-2k}$$ using $j = n-k$ as the iterator for the second sum, we get $$f(2n) = \sum_{k=1}^n C_{2k-1}C_{2n-2k} + \sum_{j = 0}^{n-1} C_{2j} C_{2n-2j}$$ The finish is in sight! The first sum is just $C_1C_{2n-2}+C_3C_{2n-4} + \dots C_{2n-1}C_{0}$ (i.e. the odd terms from $(1)$) while the second sum is just $C_{0}C_{2n-1} + \dots C_{2n-2}C_1$ (i.e. the even terms from $(1)$). Therefore, we deduce that $f(2n) = C_{2n}$ as desired.

I'm sure the bijective proof exists, but I have yet to try to find it. But given this, maybe you'll be able to do it :)

Related Question