The Gateway to Computer Science Excellence
+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 by Boss (17.5k points)
retagged by | 52 views

1 Answer

0 votes

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.

by Boss (18.9k points)
edited by

Related questions

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
50,737 questions
57,271 answers
104,778 users