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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Possible Duplicate:
Counting number of moves on a grid

I have an exercise in my Computer Science class, to figure out how many paths there are from $(0,0)$ to $(x,y)$ on a cartesian coordinate system, while the only legal moves are move up and move right.

Is there a simple method to calculate the number of available paths?

share|cite|improve this question

marked as duplicate by Austin Mohr, Micah, Davide Giraudo, Martin Argerami, martini Dec 8 '12 at 4:10

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

yes they are, edited. – Georgey Dec 7 '12 at 21:53
Note that ${x + y} \choose x$ = ${x + y}\choose y$ – amWhy Dec 7 '12 at 21:57
This is very similar to PE 15 (FYI)... – apnorton Dec 7 '12 at 22:01
up vote 2 down vote accepted

Yes, there is. You must go right $x$ times and up $y$ times, and you may make these $x+y$ moves in any order. Write R for a right move and U for an up move: you want the number of strings of $x$ R’s and $y$ U’s. There are $\binom{x+y}x$ ways to choose which $x$ places get the R’s, and that completely determines the string, so the answer is $\binom{x+y}x$.

share|cite|improve this answer

Assuming $x\ge 0$ and $y\ge 0$ you will make $x+y$ moves in total and among these are $y$ moves up. That should be $x+y\choose y$.

share|cite|improve this answer
@amWhy Of course, thanks – Hagen von Eitzen Dec 7 '12 at 23:38
+1. I knew what you meant! ;-) – amWhy Dec 7 '12 at 23:40

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