Number of Paths from A to B

Question

These type of questions that ask the Number of Paths are relatively easy when it a ordered grid, However this one isn't:

How do I account for all the paths without counting. And when you are only allowed to move to the right or down.

This is part of a timed test so what would be the fastest way to do it?

Answer 1

Start by labelling the A as 1 (since there is one way to start your path, at A).

Then go to all the points that are reachable from already labelled points. The number of ways of getting to those points is the sum of the labels of the adjacent points. Repeat until you have the number of ways of travelling to B and all nodes are labelled.

If you are able to go backwards and repeat points then a simple cycle will tell you there are infinitely many ways of making it through the maze.

If you can only go on edges once then. Look at Eulerian paths. You'll need to omit some edges.

If you can only go to nodes once then see Hamiltonian paths.

Answer 2

First of all, we can label the vertices from which there is more than one viable path to $B.$

Now we work in reverse from $B.$ The only labeled vertex from which we can get to $B$ directly is $L,$ and there are clearly $3$ ways to do so. Hence, we get

We continue in the same way. The only vertex from which we can get directly to $L$ is $K,$ and $K$ can only get to either $L$ or a single unlabeled vertex, so there are $3+1=4$ ways to get from $K$ to $B.$

Next, only $J$ allows us a direct path to $K,$ and we can also get to an unlabeled vertex, so there are $4+1=5$ ways to get from $J$ to $B.$

Each of $E$ and $H$ connect directly to $J,$ and to exactly $1$ unlabeled vertex, so there are $5+1=6$ ways to get to $B$ from either of them.

From $C,$ we can get directly to $E$ and $1$ unlabeled vertex, giving $6+1=7$ ways to get from $C$ to $B.$ From $G,$ we can get directly to $E$ and $2$ unlabeled vertices, giving us $6+2=8$ ways to get to $B$ from $G.$ We can also get to $E$ from $D,$ but we need to hold off on that, since we can also get to the (as yet unnumbered) vertex $F$ from there.

Next, we can get directly from $F$ to $G$ and to $1$ unlabeled vertex, giving us $8+1=9$ ways to get from $F$ to $B.$

Then, from $D,$ we can get directly to $E$ or $F,$ giving us $6+9=15$ ways to get from $D$ to $B.$

Finally, from $A,$ we can get directly to $C$ and $D,$ giving us $7+15=22$ ways to get from $A$ to $B.$