The number of paths of length $n$ that end at a specific vertex in a grid-like graph Suppose you have a graph consisting of nine vertices laid out in a $3\times3$ grid where each vertex is connected to each of its horizontal, vertical, and diagonal neighbors. So the corner vertices have degree three, the edge vertices have degree five, and the center vertex has degree eight. 
I want to count the number of paths of length $n$ that end at a given node $v$. You can make the observation that this number is simply the sum of the number of paths of length $n-1$ that end at each neighbor of $v$. With this in mind we can calculate this number iteratively for each vertex and for each $n$.
$$
\begin{matrix}
  1 & 1 & 1 \\
  1 & 1 & 1 \\
  1 & 1 & 1 \\
  & {n=1} & \\
\end{matrix}
\quad\longrightarrow\quad
\begin{matrix}
  3 & 5 & 3 \\
  5 & 8 & 5 \\
  3 & 5 & 3 \\
  & {n=2} & \\
\end{matrix}
\quad\longrightarrow\quad
\begin{matrix}
  18 & 24 & 18 \\
  24 & 32 & 24 \\
  18 & 24 & 18 \\
  & {n=3} &    \\
\end{matrix}
\quad\longrightarrow\quad\dotsb
$$
Is there a (nice) formula for the number of paths of length $n$ that end at a corner, edge, and center vertex?
 A: Instead of using normal $3\times 3$ matrix, write it out as a $9\times 1$ vector : $$\left[\begin{array}{c}1&2&3\\4&5&6\\7&8&9\end{array}\right] \to [1,2,3,4,5,6,7,8,9]^T$$
and use adjacency matrix for multiplication:
$$
\left[
  \begin{array}{c}
    0&1&0&1&1&0&0&0&0\\
    1&0&1&1&1&1&0&0&0\\
    0&1&0&0&1&1&0&0&0\\
    1&1&0&0&1&0&1&1&0\\
    1&1&1&1&0&1&1&1&1\\
    0&1&1&0&1&0&0&1&1\\
    0&0&0&1&1&0&0&1&0\\
    0&0&0&1&1&1&1&0&1\\
    0&0&0&0&1&1&0&1&0
  \end{array}
\right]$$
The matrix is symmetric, and according to Wolfram Alpha it has rather nice diagonal form.
All combined, that gives you a closed-form solution for any position in your matrix. 
To make it a bit easier, it's enough to have $3\times 1$ vector (corner, side, center), as all the other values are symmetric, and the simplified matrix also has a nice diagonal form, no surprises here. For example:
$$
\left[\begin{array}{c}0&2&1\\ 2&2&1 \\ 4&4&0\end{array}\right]^2 \left[\begin{array}{c}1\\1\\1\end{array}\right] = \left[\begin{array}{c}18\\24\\32\end{array}\right]
$$
I hope this helps $\ddot\smile$
