Number of possibilities to cross a hexagonal lattice.

An ant walks along the line segments in the hexagonal lattice shown, from start to finish. The ant must go in the direction shown if there is an arrow, and never goes on the same line segment twice. How many different paths can the ant take?

I am not looking for an answer to this, just a hint on how to get started. I have an adjacency matrix setup, and know that I can use A^r to find possibilities for r number of lengths, but that includes retaking the same paths. How do I get over that bump?

Note: Original image here

Thanks for merico's crucial hint "4 coulmns of arrows going to the right", following is my answer.

By collapsing some of the vertices and edges, the honey comb is equivalent to following ladder graph:

Forget about the matrix expression in above figure first. Some of the edges in this ladder graph has been labeled by a number. It means that edge in the ladder graph corresponds to multiple edges in the original honey comb.

It is clear the ladder graph is composed of 3 repeating units. Figure 2 below shows the correspondence between the leftmost portion of the honey comb with the first building unit.

Each unit is composed of 2 inputs on the left, 2 outputs on the right, $2m$ forward arrows and $1$ backward arrow in the middle. One can connect the input of an unit, say $A$, to the outputs $B$ or $C$ in 3 possible manners.

As depicted in the figure 3, there are

• (figure 3a) $m + m = 2m$ ways connect to $B$ without using the backward arrow.
• (figure 3b) $m + m = 2m$ ways connect to $C$ without the backward arrow.
• (figure 3c) $m \times m = m^2$ ways connect to $C$ using the backward arrow.

For each building unit, we can summarize the number of possibilities of joining the input with the output using a $2\times 2$ matrix: $$A(m) = \begin{pmatrix}2m & 2m+m^2\\2m+m^2 & 2m\end{pmatrix}$$

In particular, for the building units $A(1)$ and $A(2)$ appear in the honey comb, we have:

$$A(1) = \begin{pmatrix}2 & 3\\3 & 2\end{pmatrix}\;\;\text{ and }\;\; A(2) = \begin{pmatrix}4 & 8\\8 & 4\end{pmatrix} $$

The purposes of these matrices and the usefulness of merico's hint boils down to a simple fact. Once one can break down a directed graph into a chain of subgraphs with output of one subgraph feeding into input of next subgraph. The counting of all possible paths from start to finish is simplified. It turns into a condition sum of number of paths conditional to what edges are taken between the subgraphs.

The computation of total number of paths $\mathcal{N}_{path}$ becomes evaluation of a matrix product of corresponding matrices and the matrix expression can be written down by inspection of the graph! This is what the mysterious matrix expression in Figure 1 for and the final result is:

$$\mathcal{N}_{path} = \begin{pmatrix}1\\1\end{pmatrix}^T \begin{pmatrix}2 & 3\\3 & 2\end{pmatrix} \begin{pmatrix}2 & 0\\0 &2\end{pmatrix} \begin{pmatrix}4 & 8\\8 & 4\end{pmatrix} \begin{pmatrix}2 & 0\\0 &2\end{pmatrix} \begin{pmatrix}2 & 3\\3 & 2\end{pmatrix} \begin{pmatrix}1\\1\end{pmatrix} = 2400 $$

UPDATE

This question has been asked before on MSE but not answered. It has also been posted to artofproblemsolving and identified as 2012 AMC 10B Problems/Problem 25. According to the answer on artofproblemsolving, $\mathcal{N}_{path}\;$ is 2400.

You can see that since there are $4$ columns in which all arrows are going to the right, once you use one of them, you cannot go back to the left of this column. So that any path will go through exactly one arrow from each column, and between two of those, it must stay between those two columns.

Then it is not too hard to count, for any possible "consecutive" pair of those arrows, how many path there are between them.

For example, look at the paths between the $2$nd and $3$rd columns. Each one has $4$ arrows. If $N(i,j)$ is the number of path from the $i$th arrow of the $2$nd column to the $j$th arrow of the $3$rd, column, $N(1,1) = N(1,2) = 4, N(1,3) = N(1,4) = 8$ and so on (so you never have to count very far).

Then you gather these results, which allows you to easily count the number of paths from the start to any of those arrows, and finally, the number of paths from start to end.