-2
$\begingroup$

What's the number of paths from the $(0,0)$ cell to the $(m,n)$ cell in a matrix, where you can only turn right or down?

$\endgroup$

closed as off-topic by Carl Mummert, Theoretical Economist, Key Flex, Lord Shark the Unknown, user21820 Oct 15 '18 at 4:07

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Carl Mummert, Theoretical Economist, Key Flex, Lord Shark the Unknown, user21820
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ This is a frequently asked question, but it also happens to have been last week's puzzle in The Riddler - for which the solution was posted yesterday: link. (Scroll down to the Riddler Classic from last week!) $\endgroup$ – Benjamin Dickman Sep 29 '18 at 21:16
1
$\begingroup$

We have to choose $m$ right moves among $m+n$ or $n$ left moves among $m+n$ to determine a path, therefore

$$N=\binom{m+n}{m}=\binom{m+n}{n}=\frac{(m+n)!}{m!n!}$$

Refer also to the related

$\endgroup$
1
$\begingroup$

If you want to get from $(0,0)$ to $(m,n)$ only performing $r$ and $d$ movements a typical path would look like $\underbrace{r,r,r, \cdots , r}_{m \text{ times}} + \underbrace{d,d,d, \cdots , d}_{n \text{ times}}$.

Note that regardless how to shuffle the $r$ and $d$ movements in the end you will always get to $(m,n)$. The only thing left to calculate is in how many ways you can choose $m$ (or $n$) elements out of $(n+m)$. In other words:

$$\binom{m+n}{n} \text{ or } \binom{m+n}{m}$$

$\endgroup$
1
$\begingroup$

In total, you have to make $m$ "right" moves and $n$ "down" moves. The total number of ways to arrive to $(m,n)$ is thus equal to the number of ways to arrange $m$ "right" moves and $n$ "down" moves, which is $$\frac{(m+n)!}{m!\,n!}\,.$$

The explanation is the following. First of all, for any collection of $k$ (distinguishable) objects, there are $k!$ ways to arrange them. How do we calculate the number of ways to arrange $m$ "right" moves and $n$ "down" moves from this? Well, let's start by noticing that there would be $(m!+n!)$ ways to arrange them if each move was distinguishable from the others (for example, if making a certain "down" move first and then another "down" move would be different from making the latter first and the former next—which of course doesn't make sense). So we need to "uncount" the arrangements where moves of the same type have been switched around amongst them.

The way to do that is to divide $(m+n)!$ by $m!$ and by $n!$, since $m!$ and by $n!$ are, respectively, the number of ways to arrange $m$ "right" moves and the number of ways to arrange $n$ "down" moves amongst themselves.

$\endgroup$
  • $\begingroup$ Thanks for response, can you please add more explanation? $\endgroup$ – Plompy Sep 29 '18 at 20:50
  • $\begingroup$ It is correct but maybe you should justify better the final formula. $\endgroup$ – gimusi Sep 29 '18 at 20:59
  • $\begingroup$ @Plompy I've added an explanation; tell me if you need more clarification. $\endgroup$ – Anakhand Sep 29 '18 at 21:00

Not the answer you're looking for? Browse other questions tagged or ask your own question.