https://gateoverflow.in/1275/gate2007-84

same concept

1 vote

How many paths are there in the plane from $(0,0)$ to $(m,n)\in \mathbb{N}\times \mathbb{N},$ if the possible steps from $(i,j)$ are either $(i+1,j)$ or $(i,j+1)?$

- $\binom{2m}{n}$
- $\binom{m}{n}$
- $\binom{m+n}{n}$
- $m^{n}$

1 vote

**Answer:****C**

**Explanation:**

The total number of steps that are required to reach $\mathbf {(m, n)}$ is $\color {green} {\underline {\mathbf {\color {red} {{m+n}}}}}$. So, $\mathbf m$ steps are required on the $\mathbf x-\text{axis}$ and $\mathbf n$ steps are required on the $\mathbf y-\text{axis}$.

From $\mathbf {m+n}$ stride, the number of steps which are taken on the $\mathbf x-\text{axis}$ and $\mathbf y-\text{axis}$ can be distributed in any way.

$\therefore $ If $\mathbf n$ steps are chosen on the $\mathbf y-\text{axis}$, then the remaining steps should go to the $\mathbf x -\text{axis}$.

$\therefore$ Total steps $=\fbox {$\Large \color {blue} {\mathbf {\binom{m+n}{n}}}$}$

$\therefore$ **C** is the correct option.