Combinatorics-how many paths

Question

How many paths with length 9 (1 is a length of 1 edge) you have in order to get from point A to B (you are allowed to trace back the edge you just walked) in the picture

Answer 1

Build the "adjacency matrix" of this graph. I'll call the middle two vertices $X$ and $Y$, and the bottom vertices (other than $B$) $Z$ and $W$. If we order the vertices: $\{A,B,X,Y,Z,W\}$, then the adjacency matrix is

$$ M = \left( \begin {array}{cccccc} 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 \end {array} \right) $$

This encodes which vertices are connected by an edge. For example, the first row means $A$ connects to $X$ and $Y$, but not to any other vertices. Taking powers of this matrix counts paths of certain lengths.

So in your case $M^9$ will be the matrix which counts the number of paths of length 9 between any two vertices. So you want the $(1,2)$ entry of $M^9$.

Answer 2

Another way to approach it is to make $10$ copies of the diagram. The first counts the number of ways to get to each vertex in $0$ moves, so has $1$ at vertex $A$ and $0$ everywhere else. The next has the number of ways to get to each vertex in $1$ move. It will have $1$s at the two vertices in the second layer, the one between $A$ and $B$. Each successive copy has the number of ways to get to each vertex in one move more than the one before. Each vertex in $k$ moves gets the sum of the numbers at all the vertices it is connected to from the $k-1$ move drawing because you could have gotten to each of those vertices in $k-1$ moves in the number of ways shown, then moved to the vertex in question with the $k^{th}$ move.

The adjacency matrix approach really encodes this thinking.