Number of Paths from A to B

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?

• Is it assumed you can only move in the right and/or down direction? – Bram28 Nov 29 '17 at 23:45
• 'This is a timed test' ...; are you saying you are taking this test right now?!? – Bram28 Nov 29 '17 at 23:50
• What are the constraints? Not visiting the same point more than once? Differentiating between paths only based on what intersections they visit? I'm assuming going from A to B is one of the constraints. – Emil Nov 30 '17 at 0:03

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.

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.$

• Very simple and easy to understand, but because I saw Stuart Stevens first I had to give him the answered... – The Math Guy Dec 1 '17 at 0:19
• Of course! That's what I'd have done in your place. Unfortunately for me, I didn't see Stuart's answer until after I posted mine. :-p – Cameron Buie Dec 1 '17 at 1:55
• Feel free to give me an "upvote" (if you haven't already done so). Also, welcome to Math.SE! – Cameron Buie Dec 1 '17 at 1:56
• I already did give you an upvote... Thank You – The Math Guy Dec 1 '17 at 3:12