[Math] Lattice Paths to $(2n, 2n)$ that do not go through $(n,n)$

combinatoricsinteger-lattices

I know that from the origin to $(x,y)$ there are $${x+y \choose x} = {x+y \choose y}$$
Lattice paths. The question is finding the number of paths from the origin to $(2n, 2n)$ not passing through $(n,n)$. My attempt at the solution is first count all the possible paths which is equal to $${4n \choose 2n}$$
Then we subtract all paths that go through point $(n,n)$ which has to equal to all paths that end at $(n,n)$ which is $${2n \choose n}$$
So the total number of paths from $(2n, 2n)$ to $(n,n)$ is $${4n \choose 2n} – {2n \choose n}$$
I don't know though if those are the total number of paths that do not go through $(n,n)$ and end at $(2n,2n)$. If this is true, how do I go about proving that there are only ${2n \choose n}$ paths going through $(n,n)$?

Best Answer

You've made a good start. The only problem is that $\binom{2n}n$ only counts the number of paths from $(0,0)$ to $(n,n)$. You can combine each of these with any path from $(n,n)$ to $(2n,2n)$, and there are also $\binom{2n}n$ of those, so the total number of paths going through $(n,n)$ is $\binom{2n}n^2$.

If you're not sure about something like this, a good idea is to try it out concretely for small numbers. In the present case, you can very easily enumerate all the paths for $n=1$ and find that $4$ of the $6$ go through $(1,1)$. If you'd done this, you'd probably have noticed what was missing in your argument.

Related Question