Permutations of geometric structure

Question

Sorry about the title, i don't know how to describe this problem.

I tried counting my way through this problem but kept getting the wrong answer(which is 12, by the way). Is there a more systematic way of getting the answer? Thanks!

Answer 1

Look at the two verts to the left of $R$. The number of 6-edge paths to $R$ is sum of the number of 5-edge paths to these two.

The number of 5-edge paths to those two come as sums of the numbers of 4-edge paths to their predecessors, and so on, all the way back to $L$, where the number of $0$-edge paths from $L$ to $L$ is $1$. So the number of 1-edge paths to the two verts to the right of $L$ is $1$ each. Then you can compute the number of 2-edge paths from $L$ to the next 3three verts that are in a vertical line, and so on.

Reading top to bottom in each group, I get

             2
1  1  2  2   3  7   12
   1  2  3   2  5
      1

The systematic approach is to say, "Is there a simpler problem whose solution, if I knew it, would get me to my answer?"

In this case, the simpler problem is, "How many 5-edge paths are there to the predecessors of $R$?", which is simpler because $5$ is smaller than $6$ (and the graph you have to look at is smaller!), and whose solution is sufficient because the answer, at vertex $R$, is simply the sum of the simpler answers at the predecessors.

Once you've found such a simpler problem, there's usually a way to apply the same idea over and over, as in this case, until you get to a really simple question ("How many 0-edge paths are there from $L$ to $L$?"). And you can then build back up from there. This is a kind of recursion, which often gets used in graph-analysis problems.