1
$\begingroup$

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)$?

1 Answers 1

4

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.

  • 0
    @Salazar: Yes, you can combine each path from $(0,0)$ to $(n,n)$ with each path from $(n,n)$ to $(2n,2n)$, so you've got one path for every pair of paths, and the number of pairs of paths is the product of the numbers of paths.2011-11-02