5
$\begingroup$

Question:

Consider a square matrix of order $m$. At each step you can move one step to the right or one step to the top. How many possibilities are to reach $(m,m)$ from $(0,0)$?

I think it is just counting the Central binomial coefficients.

Am I right? If not what is be the correct answer and why?

  • 1
    It is a square *grid*, rather than a *matrix*, most obviously because it has $(m+1) \times (m+1)$ points, though $m$ edges on each side.2011-03-08

1 Answers 1

10

You are correct. The reason is to get to $(m,m)$ you need to take a total of $m+m$ steps. However, you need to choose $m$ of those steps to be steps up, so the total number of paths is $\binom{m+m}{m}=\binom{2m}{m}$, since the central binomial coefficient picks which of the $2m$ steps will be up.

To add to this, in general, the number of paths from $(0,0)$ to $(m,n)$ is then $\binom{m+n}{m}=\binom{m+n}{n}$ for the same reasoning.