Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
    
Thanks. So since they are complete path from (0,0) to (n,n) and (n,n) to (2n,2n), you use the rule of product and multiply instead of add, right? –  Salazar Nov 2 '11 at 8:58
    
@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. –  joriki Nov 2 '11 at 11:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.