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

11

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