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?

  • 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$ Aug 27, 2019 at 3:04
  • 2
    $\begingroup$ Please add your attempt in your question to remove the downvotes. $\endgroup$ Oct 10, 2019 at 10:08

2 Answers 2


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!

  • $\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$ Aug 27, 2019 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$ Aug 27, 2019 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$ Aug 27, 2019 at 3:44
  • 9
    $\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, 2019 at 11:14

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.

  • 20
    $\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$ Aug 27, 2019 at 15:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .