How many lattice paths are there from $(0,0)$ to $(2n,2n)$ that avoids odd points 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?
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 :)
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.