10
$\begingroup$

This is a basic question in combinatorics with a little trick. Consider the following triangular array of numbers:

enter image description here

How many paths from a 1 on the diagonal to the 10 in the lower right where we only step to the right or down are there? For example, here is a legal path:

enter image description here


Batominovski's edit:

Attempt: It looks like each path is associated to a sequence of down steps ($D$) and right steps ($R$) of length $9$. The example above corresponds to $DRDDDRRDD$. Can it be any sequence? What is a correct answer?

$\endgroup$
  • 1
    $\begingroup$ Adding de possibilities for every number 1. The first one has 1, the second one has 9 and then I got stuck at the third one and could not find a pattern. $\endgroup$ – user3347814 Aug 27 '19 at 3:04
  • 2
    $\begingroup$ Please add your attempt in your question to remove the downvotes. $\endgroup$ – Culver Kwan Oct 10 '19 at 10:08
55
$\begingroup$

You can think the problem as start with the $10$ and follow the numbers in order until you reach $1$.

Then there is two ways for each step: up or left. Then there are $2^{10-1}=2^9=512$ ways. Done!

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I know the answer is correct. But I can't make intuitive sense out of it. Is there a another way to thing about this problem? $\endgroup$ – user3347814 Aug 27 '19 at 3:16
  • 10
    $\begingroup$ @user3347814 Another way is to observe that if you start from the "1" on $n$th floor ($n=0$ at the ground floor), then you need $9$ steps to reach $10$. Out of those nine steps, $n$ will go down, and you are free to choose when to go down, so there is a total of $\binom 9n$ paths starting from that particular $1$. Thus the total number of paths is $$\sum_{n=0}^9\binom 9n=(1+1)^9=2^9$$ by the binomial formula. Frankly, I think we should view Culver Kwan's answer as an elegant proof of the binomial formula in this case. I would not really consider any other argument worthy of presentation. $\endgroup$ – Jyrki Lahtonen Aug 27 '19 at 3:41
  • 1
    $\begingroup$ And if the argument leading $\binom 9n$ is not clear, take a look at this. It is the same idea. $\endgroup$ – Jyrki Lahtonen Aug 27 '19 at 3:44
  • 8
    $\begingroup$ @user3347814: This answer is the way to think about the problem: retrace your steps from the $10$ back to a $1$. You won't find an easier solution! $\endgroup$ – TonyK Aug 27 '19 at 11:14
29
$\begingroup$

enter image description here

Each square shows the number of (legal) paths to that square.

So the number of possible paths to the bottom right square is 512.

| cite | improve this answer | |
$\endgroup$
  • 19
    $\begingroup$ This could be more concrete by pointing out the number of ways to reach any square is the sum of the number of ways to reach the squares above and to the left of that square. $\endgroup$ – Bernhard Barker Aug 27 '19 at 15:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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