CMI2018-A-5

Question

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

• A. $\binom{2m}{n}$
• B. $\binom{m}{n}$
• C. $\binom{m+n}{n}$
• D. $m^{n}$

Comments

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

same concept

Answer 1

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.

Answer 2