Log In
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
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)?$

  1. $\binom{2m}{n}$
  2. $\binom{m}{n}$
  3. $\binom{m+n}{n}$
  4. $m^{n}$
in Combinatory
retagged by

1 Answer

1 vote

Answer: C


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
0 answers
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.
asked Sep 13, 2019 in Graph Theory gatecse 77 views
2 votes
3 answers
Which of the words below matches the regular expression $a(a+b)^{\ast}b+b(a+b)^{\ast}a$? $aba$ $bab$ $abba$ $aabb$
asked Sep 13, 2019 in Theory of Computation gatecse 316 views
1 vote
2 answers
Akash, Bharani, Chetan and Deepa are invited to a party. If Bharani and Chetan attend, then Deepa will attend too. If Bharani does not attend, then Akash will not attend. If Deepa does not attend, which of the following is true? Chetan does not attend Akash does not attend either (A) or (B) none of the above
asked Sep 13, 2019 in Numerical Ability gatecse 124 views
1 vote
1 answer
In a running race, Geetha finishes ahead of Shalini and Vani finishes after Aparna. Divya finishes ahead of Aparna. Which of the following is a minimal set of additional information that can determine the winner? Geetha finishes ahead of Divya and Vani finishes ahead of Shalini. Aparna finishes ahead of Shalini. Divya finishes ahead of Geetha. None of the above.
asked Sep 13, 2019 in Numerical Ability gatecse 87 views