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.

Possible Duplicate:
How can I find the number of the shortest paths between two points on a 2D lattice grid?

If we have a point p(x,y) in coordinate system [x>=0, y>=0; i.e 1st quadrant]

How to find the number of ways of reaching the point from origin (0,0).

Ex: If p(2,1); 

way1: 0,0 -> 1,0 -> 2,0 -> 2,1
way2: 0,0 -> 1,0 -> 1,1 -> 2,1 
way3: 0,0 -> 0,1 -> 1,1 -> 2,1

Is it possible to have a mathematical equation for it? and How? if we don't have, what's the best possible way to find those.

Rules:

  1. You can move only in horizontal, vertical directions (diagonal is not possible)
  2. you can only move to the point (a,b) such that 0<=a<=x and 0<=b<=y
  3. a, b can be only natural numbers
share|improve this question

marked as duplicate by JavaMan, Fabian, Srivatsan, Martin Sleziak, Asaf Karagila Jan 29 '12 at 11:44

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.

    
What counts as a way? From your examples, it's not clear what kinds of moves are allowed. For example, Does $(0,0) \rightarrow (42542, 152345) \rightarrow (2,1)$ count as a way to get to $(2,1)$ from the origin? –  JohnJamesSmith Jan 29 '12 at 4:10
    
Or $\:\: (0,0) \to \left(\frac13,\operatorname{ln}(2)\right) \to (2,1) \:\:$? $\;\;\;\;$ –  Ricky Demer Jan 29 '12 at 4:13
    
sorry for not mentioning rules, please look at the question, I added –  Surya Jan 29 '12 at 4:15
    
If there is no bound, you can go reach it in infinitely many ways, like specified above, $(0,0)\to(\infty,\infty)\to(2,1)$, do you take it to be a valid one ? , if not, specify some constraints and bounds @Surya –  Iyengar Jan 29 '12 at 4:17
    
only natural numbers are possible –  Surya Jan 29 '12 at 4:17

2 Answers 2

up vote 5 down vote accepted

It is well known that the number of ways to get to the lattice point $(x,y)$ (supposing $x, y \geq 0$) by taking steps of one unit each either in the eastward or northward direction is exactly $$ {x + y \choose x} = {x+y \choose y} = \frac{(x+y)!}{x! y!}. $$

Such paths are called lattice paths. See, for example, here.

share|improve this answer
    
+1 for a A very clear answer –  Iyengar Jan 29 '12 at 4:29
    
Why the down vote? –  JavaMan Jan 29 '12 at 4:55
    
Downvote ? , I gave an upvote. It wasn't me @JavaMan –  Iyengar Jan 29 '12 at 5:48
    
@iyengar: Thanks for the upvote, but I'm not too worried about who downvoted. I'm more worried about what part of my answer wasn't deemed satisfactory. –  JavaMan Jan 29 '12 at 5:50
    
Haven't you noticed that your answer has been selected, your answer was very good, and seems to fit in a good sense, its only some fools around here, who unnecessarily down-vote the answer, without leaving any comments, it happened to me quite many times, even got the worst votes. But if someone down-votes the answers without a comment, it surely acts as a cause of annoying the person who answers the question. But let us leave this topic, and why should we bother about points here, if your answer is perfect. Does points earn us anything in reality apart from an apparent fame here . –  Iyengar Jan 29 '12 at 6:03

It is a combinatorial question, where you have $x+y$ things and you have to pick $x$ (or $y$, both are symmetric) times when you can make a choice. In other words, you have $x$ ways to move in $x$ direction, $y$ way to move in $y$ direction. However, once you pick any $x$ direction, the choices for $y$ is fixed. Therefore, the total number of way you can do the above is $(x+y)$ choose $x$ (or $y$, respectively). Mathematically, it will be

$$\left( \begin{matrix} x+y \\ x \end{matrix} \right) = \left( \begin{matrix} x+y \\ y \end{matrix} \right).$$

share|improve this answer

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