0
$\begingroup$

how to work out this kind of routes counting problem? I always missing or duplicated when counting, is there any good method to do counting or even best, there is a method to calculate for the result?

example for routes counting

$\endgroup$
0
$\begingroup$

Work backwards from points near B.enter image description here Here I've labeled each point with a letter, but that's just so I can talk about them. The lettres aren't important, and in solving such a problem, you needn't bother with them.

I'm going to say that point Y is a "son" of of point X if there's an arrow directly from point X to point Y. Again, that's just so I can talk about the problem.

First, we number point B with $1$. Now we repeatedly find the points all of whose sons are numbered, and number those points with the sum of the numbers on the sums. C and E both have B as their only son, so they get numbered 1. Now both of F's sons are numbered so F gets numbered 2. The number on a point represents the number of routes to get from that point to B. I think you can see why this works. When we're at some point X, we can only go to one of its sons, and if we already know how many ways to get to B from each of the sons, we just have to add them up to get the number of routes from X to B. Keep going until A is numbered.

You can check if I did it right. No guarantees -- this is the second time I've done it.

$\endgroup$
  • $\begingroup$ very clear, very simple to understand! thank you very much! $\endgroup$ – user3127293 Apr 10 at 5:55
  • $\begingroup$ @user3127293 It was my pleasure. $\endgroup$ – saulspatz Apr 10 at 11:14

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.