How many ways is it possible to count from 1 to 10 in this diagram?

You must start with a 1 and follow the numbers in order until you reach 10.

  • 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 at 3:04
  • 1
    $\begingroup$ Please add your attempt in your question to remove the downvotes. $\endgroup$ – Culver Kwan Oct 10 at 10:08

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$ – user3347814 Aug 27 at 3:16
  • 9
    $\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 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 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 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.

  • 15
    $\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$ – Dukeling Aug 27 at 15:44

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