1
$\begingroup$

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
  • 0
    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?2012-01-29
  • 0
    Or $\:\: (0,0) \to \left(\frac13,\operatorname{ln}(2)\right) \to (2,1) \:\:$? $\;\;\;\;$2012-01-29
  • 0
    sorry for not mentioning rules, please look at the question, I added2012-01-29
  • 0
    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 @Surya2012-01-29
  • 0
    only natural numbers are possible2012-01-29
  • 0
    @iyengar please look at the rules.2012-01-29
  • 0
    The move '0,1 -> 1,2' is diagonal.2012-01-29
  • 0
    @ByronSchmuland sorry, there was a mistake in example. However, I got the right answer. Please look at it now2012-01-29
  • 0
    For those interested: I answered this question, but then noticed that the same question (written a little more precisely) appeared previously.2012-01-29

2 Answers 2

10

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.

  • 0
    Why the down vote?2012-01-29
  • 0
    Downvote ? , I gave an upvote. It wasn't me @JavaMan2012-01-29
  • 0
    @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.2012-01-29
  • 0
    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 .2012-01-29
  • 0
    @iyengar: Just for the record, I never thought you downvoted, and actually I don't really care who downvoted just as I do not care about the reputation. I was merely more curious as to _why_ the downvoter did so, and how I could improve my answer.2012-01-29
  • 0
    @JavaMan I wonder if you could answer another question which is based on this one. [Link](http://math.stackexchange.com/questions/103506/what-is-the-maximum-point-for-which-number-of-way-to-reach-is-given)2012-01-29
  • 0
    @JavaMan : I too was curious in knowing the problems, even I posted a feature request in Meta, I too suggested the same thing, I said I am not bothering about down-votes, I suggested that if the person who down-votes the answer leaves the reason for doing so, it would be helpful for person who posted the answer, both in formatting and correcting himself. But majority people said, we dont need to keep such feature. So I left, but wont it hurt you ( not only you but any one who answers and gets downvoted without a reason ) ?, I don't know about you, but it hurts me a lot.2012-01-29
  • 0
    @JavaMan and : Do not worry about down or upvotes, I have seen many times other poeple's good answer (not only mine) have been downvoted for no reason, now a days I think it is comical for a good answer to get downvoted by some bozo without leaving a comment, I just do my bit and upvote, BTW : It wasn't me who downvoted :)2012-01-29
  • 0
    @Arjang : But is there any solution to eradicate that comical "Down-voting" foolishness ? .2012-01-29
  • 0
    @iyengar : Aaah yes, it has already been implemented, downvoting costs points, so it is not free to downvote!2012-01-29
3

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