# CMI2018-A-5

1 vote
116 views

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

1. $\binom{2m}{n}$
2. $\binom{m}{n}$
3. $\binom{m+n}{n}$
4. $m^{n}$

retagged

1 vote

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.

edited by

## Related questions

1 vote
1
77 views
Let $G=(V,E)$ be an undirected graph and $V=\{1,2,\cdots,n\}.$ The input graph is given to you by a $0-1$ matrix $A$ of size $n\times n$ as follows. For any $1\leq i,j\leq n,$ the entry $A[i,j]=1$ ... which any two vertices are connected to each other by paths. Give a simple algorithm to find the number of connected components in $G.$ Analyze the time taken by your procedure.
Which of the words below matches the regular expression $a(a+b)^{\ast}b+b(a+b)^{\ast}a$? $aba$ $bab$ $abba$ $aabb$