How many lattice paths are there from $(0,0)$ to $(2n,2n)$ that avoids odd points

Question

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?

Answer 1

Let's call your sequence of valid, $(2i-1,2i-1)$ avoiding, paths $\langle a_k \rangle$. Then it has a recurrence, starting with $a_0=1$ shown below:

$$a_k=\sum_{i=1}^{k}2c_{2i-1}a_{k-i}\tag{1}$$

Since any path has some first point where it touches the diagonal at an even point $(2i,2i)$ there are $2c_{2i-1}$ catalan paths to this point from $(0,0)$ (one set of $c_{2i-1}$ paths above the diagonal and one below) then $a_{k-i}$ valid paths from $(2i,2i)$ to $(2k,2k)$. Hence the are $2c_{2i-1}a_{k-i}$ valid paths whose first intersection with the diagonal is $(2i,2i)$. Summing over all possible first diagonal intersection points $i=1,\ldots,k$ gives $(1)$.

Call the generating function for $\langle a_k \rangle$ $f(z)=\sum_{j\ge 0}a_jz^j$ and the catalan number generating function $C(z)$, then the odd catalan numbers have generating function

$$C_o(z)=\frac{1}{2}z^{1/2}(C(z^{1/2})+C(-z^{1/2}))=\sum_{j\ge 1}c_{2j-1}z^j\tag{2}$$

and even catalan number generating function

$$C_e(z)=\frac{1}{2}(C(z^{1/2})+C(-z^{1/2}))=\sum_{j\ge 0}c_{2j}z^j\tag{3}$$

then $(1)$ can be represented by the generating function relation

$$1+2C_o(z)f(z)=f(z)$$

so that

$$f(z)=(1-2C_o(z))^{-1}\tag{4}$$

It is known that the catalan number generating function is

$$C(z)=\frac{1}{2z}(1-\sqrt{1-4z})=\sum_{j\ge 0}c_jz^j$$

so $(2)$ and $(3)$ become

$$C_o(z)=\frac{1}{4}\left(2-\sqrt{1-4z^{1/2}}-\sqrt{1+4z^{1/2}}\right)\tag{2*}$$

$$C_e(z)=\frac{1}{-4z^{1/2}}\left(\sqrt{1-4z^{1/2}}-\sqrt{1+4z^{1/2}}\right)\tag{3*}$$

Now putting $(2\text{*})$ in $(4)$ gives

$$f(z)=\frac{2}{\sqrt{1-4z^{1/2}}+\sqrt{1+4z^{1/2}}}$$

then multiplying top and bottom by $\sqrt{1-4z^{1/2}}-\sqrt{1+4z^{1/2}}$ gives

$$\begin{align}f(z)&=\frac{2\left(\sqrt{1-4z^{1/2}}-\sqrt{1+4z^{1/2}}\right)}{(1-4z^{1/2})-(1+4z^{1/2})}\\[2ex] &=\frac{1}{-4z^{1/2}}\left(\sqrt{1-4z^{1/2}}-\sqrt{1+4z^{1/2}}\right)\\[2ex] &=C_e(z)\end{align}$$

hence $a_k=c_{2k}$ are the even catalan numbers

$$1,2,14,132,1430,\ldots$$

Answer 2

Let $C_k$ be the $k$-th Catalan number. If by "do not go through one of the points $(2i-1,2i-1)$" you mean "do not go through any of them", my answer is $$2C_{2n-1}=2\cdot \frac{1}{(2n-1)+1}\binom{2(2n-1)}{2n-1}=\frac{1}{n}\binom{4n-2}{2n-1}$$ Indeed, in every lattice path from $(0,0)$ to $(2n,2n)$ the first step, like any other step, is either "$\uparrow$" (going $1$ unit up) or "$\to$" (going $1$ unit to the right). WLOG, assume that one initially chooses "$\to$" and goes frim $(0,0)$ to $(1,0)$. Then the last step must be an "$\uparrow$" (i.e. going from $(2n,2n-1)$ to $(2n,2n)$) because it is required that the lattice path does not intersect the diagonal at all. Now the number of lattice paths from $(1,0)$ to $(2n,2n-1)$ that does not pass above the line segment $\ell$ joining those two points is $C_{2n-1}$. (Any lattice path from $(1,0)$ to $(2n,2n-1)$ that passes above $\ell$ will intersect the main diagonal). By symmetry, the number of lattice paths you are looking for is twice as many.

Answer 3

Let's write out some of the first few cases

Case 1) $n=1$

Number of lattice paths = $$\binom {4}{2}- \binom {2}{1} \binom {2}{1}= 2$$

Case 2) $n=2$

Number of lattice paths = $$\binom {8}{4}- \left [ \binom {2}{1}\binom {6}{3}+\binom {6}{3}\binom {2}{1}-\binom {2}{1}\binom {2}{1}\binom {4}{2}\right]= 14$$

Case 3)$n=3$

Number of lattice paths =$$\binom {12}{6}-\left[ \binom {2}{1}\binom {10}{5}+\binom {6}{3}\binom {6}{3}+\binom {10}{5}\binom {2}{1}-\binom {2}{1}\binom {4}{2}\binom {6}{3}-\binom {2}{1}\binom {6}{3}\binom {4}{2}-\binom {2}{1}\binom {2}{1}\binom {8}{4}+ \binom {2}{1}\binom {2}{1}\binom {4}{2}\binom {4}{2}\right]= 132$$

Case4) $n=4$

( It is bit messy one but I have found out the number of lattice paths so directly writing out the answer.)

Number of lattice paths =$1430$

So did you notice the pattern : $2,14,132,1430$?

These are respectively the $3^{rd}, 5^{th}, 7^{th} $ and $9^{th}$ Catalan numbers respectively.

Hence for generalized $n$ we have

Number if lattice paths= $(2n+1)^{th}$ Catalan number ( $n=1,2,3.......$)

Answer 4

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 :)

Answer 5

Here is a bijective proof. We construct a bijection $f$ from paths which avoid $(2k+1,2k+1)$ to paths which stay at or above the diagonal $y=x$.

Given a path $P$ which avoids odd diagonal points, write is as the concatenation $P_1P_2$, where the break point between $P_1$ and $P_2$ is the first time that $P$ returns to the diagonal.

• If $P_1$ is above the diagonal, then $f(P)=P_1f(P_2)$.

• If $P_1$ is below the diagonal, then $f(P)=\;\uparrow f(P_2)\rightarrow P_1'$, where $P_1'$ is attained from $P_1$ by removing its first and last steps, then reversing what remains.

This is a recursive definition. The base case is $f(\varnothing)=\varnothing$, where $\varnothing$ is the empty path.

For example, consider

                    K
                  / J
                / H I
              / F G
      9 A B C D E
      8   / 
    6 7 /   
    5 /
    4 
  / 3
0 1 2

Point $4$ is the first time the walk returns to the diagonal. The path before this $\rightarrow,\rightarrow,\uparrow,\uparrow$, which was below the diagonal. Therefore, the result is $$ \uparrow,f(P_2),\rightarrow,\uparrow,\rightarrow $$ We must recursively compute $f(P_2)$. $P_2$ looks like

                    K
                  / J
                / H I
              / F G
      9 A B C D E
      8   / 
    6 7 /   
    5 /
    4 

The line first touches the diagonal at $C$. The path before is above the diagonal, so we leave it alone and recurse on what comes after. Letting $P_3$ be what comes after, we are at $$ \def\u{\uparrow,}\def\r{\to,}\u(\u\u\r\u\u\r\r\r f(P_3))\r\u\r $$ What remains does not touch the diagonal until the end, so our recursion ends. Since $P_3$ is below, we trim its ends and reverse, and prepend $\u f(\varnothing) \r=\u\r$. The final result is $$ \u(\u\u\r\u\u\r\r\r (\u\r\u\r\u\r\u\r))\r\u\r $$ which looks like

                  J K
              G H I
            E F /
          C D /
        A B /
  6 7 8 9 /
  5     /
3 4   /
2   /
1 /
0