# Counting the number of paths on a graph

I was wondering how many different possible combinations are there for unlocking an Android phone. In order to do this, you have to choose a path from a graph:

The graph is not regular: the nodes at the corners are linked to 5 nodes only, the nodes at the sides are linked to 7 nodes and the central node is connected to every other.

The unlocking paths can have any length between 3 and 9. Is there a simple way to count the possibilities?

-
Actually, the graph is complete (and regular); you can go from any node to any other, because you don't have to move between them in a straight line. (Tested w/ Android 2.3.6.) –  Kevin Reid Dec 20 '11 at 0:59

If $A$ is the adjacency matrix of the graph, then the $ij$ entry of $A^n$ is the number of paths from vertex $i$ to vertex $j$ of length $n$ (why?). $A^n$ can be computed quickly by diagonalizing.

-
Would you mind explaining why? I'm not studying graph theory nor well versed in the subject (this problem came up while discussing Android, not graph theory). –  Fernando Martin Dec 21 '11 at 23:48
This can be proven inductively. If $p(i,j,n)$ is the number of paths of length $n$ from $i$ to $j$, then $p(i,j,n)=\sum_{\mbox{k a neighbor of j}}p(i,k,n-1)$. –  Perce Dec 23 '11 at 21:47
In your solution it's possible to walk throug a vertex more than one times, but n Android you can't. How modify your solution for excluding incorrect paths? –  Corvus Feb 6 '13 at 17:05

Let's define $v(n)$ as the number of $n$-step paths to a particular corner, $e(n)$ to a particular side and $f(n)$ to the centre node. Then you have

$$v(n)=4e(n-1)+f(n-1)$$ $$e(n)= 4v(n-1)+2e(n-1)+f(n-1)$$ $$f(n)= 4v(n-1)+4e(n-1)$$

starting with $v(0)=e(0)=f(0)=1$. Your desired result is $$\sum_{n=3}^{n=9} 4v(n)+4e(n)+f(n)$$ which I think may be 179,966,424.

There may be shortcuts: it is also $f(3)+f(10)+2\sum_{n=4}^{n=9} f(n)$; for large $n$, the number of paths of length $n$ is about $8.860423 \times 6.36388667^n$, i.e. close to a geometric progression.

-
Actually in this case the adjacency matrix and its powers can be trivially computed. For a full graph, in fact, we have $A^m=n^{m-1}J$ where $n$ is the number of nodes in the graph and $J$ is the matrix of all ones. Therefore the number $f(n)$ of possible paths of length $3, 4, \dots, n$ is exactly $$f(n)=\sum_{k=3}^n\sum_{ij=1}^n (A^k)_{ij}=n^4\sum_{k=0}^{n-3}n^k=\frac{n^4(1-n^{n-2})}{1-n}$$ The number you are looking for is $f(9)$.