# Number of ways of reaching a point from origin [duplicate]

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
-

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

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

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.

-
+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

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

-