Find the number of routes from leftmost vertex to rightmost vertex

Question

Suppose that one can move from one vertex to another if, and only if, the two vertices are connected by a unique common edge. The number of routes that one can take from the leftmost vertex L through 6 edges and 5 intermediate vertices to the rightmost vertex R is .......

This is my scholarship practice exam (pre-university level) and the only way I did it correctly is by counting but I feel it was a bit messy but it can be simplified by writing with alphabets such as (u for up, d for down, s for go straight).

However, there could be other solutions such as combination or permutation, probably. The answer key provided is 12. Please advise what you think and how to solve this problem.

Answer 1

The annoying bit are the two triangles at the bottom and top. You can get the answer by considering paths that don’t and do go through those triangles. For the ones that don’t, there are $2\cdot \ 2\cdot 1\cdot1\cdot 2\cdot 1=8$ paths.

For the ones that pass through the triangles, convince yourself that it’s only possible to pass through exactly one and not both. For the bottom triangle there are two possible paths (differing only at the R end). For the top triangle there are two possible ways to get to it from L and then only 1 way to get to R.

So the answer is 12

Answer 2

I'll give you a hint. Try to do these steps. I know it might feel tedious but I think in the process of going through it you might get an interesting idea.

You're going to start at the left vertex, and progressively move your way to the right. You'll be writing a number next to each vertex.

Start at the leftmost vertex. Write a number 1 next to it.

Now look at the second column of vertices. Write a 1 next to both of them too.

Now look at the third column of vertices. For each vertex, look at the edges that are coming into it from the left. For each edge coming in, get the number of the vertex on the left side of the edge (ie from column 2). Add up all the numbers you find, and write that number next to the vertex. Do that for all three vertices in the third column. So third column of vertices should read 2, 2, 1 from top to bottom.

Keep going with the same thing you did above for each column of vertices, getting the numbers of the vertices connected on the left, and adding those up. When you've done it for the final vertex, you should have the number of paths.

Here's how my diagram looks:

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

If you're still stuck, take a look at https://en.wikipedia.org/wiki/Divide-and-conquer_algorithm

Answer 3

Try labeling the vertices and writing down the resulting adjacency matrix. Then raise it to the power of 6, and read the entry in the (i, j) position, where i and j are the labels of the left- and right- most vertices, respectively. Since the adjacency matrix is 14 x 14, you should probably use a computer. I recommend using the Wolfram alpha website. Although it wouldn't be too hard by hand, since A^6 = (A^2)^2 A^2.