In the directed graph, shown below, how many directed paths exist that start at 1 and end at 6?

Question

I only counted five, but are there any others?

Answer 1

Use a backwards recursive count . . .

Let $x_n$ be the number of paths from $n$ to $6$ that start at $n$.

The goal is to find $x_1$.

Starting from $n=6$ and working backwards, \begin{align*} x_6 &=1\\[4pt] x_5 &= x_6 = 1\\[4pt] x_4 &= x_5 = 1\\[4pt] x_3 &= x_5 + x_6 = 1 + 1 = 2\\[4pt] x_2 &= x_3 + x_4 + x_5 = 1 + 2 + 1 = 4\\[4pt] x_1 &= x_2 + x_3 = 4 + 2 = 6 \end{align*}

so the answer is $6$.

Answer 2

There are 6:

12456

1256

12356

1236

1356

136

To find the answer of the number of paths systematically, work your way back from 6, anotating each node with the number of paths from it to 6.

Since there is only one way to get from 5 to 6, annotate 5 with 1

From 4 we can only go to 5, and since 5 was annotated with 1, we annotate 4 with 1 as well

From 3 we can go to 5, as well as straight to 6. Since 5 was annotated with 1, you get 1+1 =2 paths from 3 to 6

From 2 we can go to 3,4, or 5. Thus we annotate 2 with 2+1+1=4

Finally, from 1 we can go to 2 or 3, so we annotate 1 with 4+2=6