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?

Solution 1:

Two of the other answer, including the accepted one, use matrix powers which is wrong again because this includes paths which allow passing more than once in the same node. The third answer gives a formula lacking a proof whatsoever (we used to have them in math when I was young), I don't understand why it is wrong, and why it should be correct in the first place, but the result is too big to be correct.

For an estimation of the upper bound we can assume that the graph is complete. This is not completely true because Android does not allow connecting nodes when their path goes over a node which isn't already in the path (this strange restriction means that we can't really represent Android combinations as path in a graph, because edges would become available or not depending on which nodes we already included, a property which no graph have). Let's count the choices you can make while choosing your password: first you have to choose the starting node, then you have to choose the second node among the remaining eight, then you choose the third node among the remaining seven. Also, since Android requires your path to be at least 4 nodes long, not three, you need to choose another one among the remaining six. This gives you, so far $$9 \times 8 \times 7\times 6\times\dots$$ possible choices. Here you can choose between stopping or continuing by choosing a fifth node: $$9 \times 8 \times 7\times 6\times (1 + 5 \times\dots)$$ same for the following choices, each time you can choose between stopping and choosing one of the remaining nodes to continue: $$9 \times 8 \times 7\times 6 \times(1 + 5\times(1 + 4\times\dots))$$ $$9 \times 8 \times 7\times 6 \times(1 + 5\times(1 + 4\times(1+3\times\dots)))$$ when all nodes are used you don't have any more choices: $$9 \times 8 \times 7\times 6 \times(1 + 5\times(1 + 4\times(1+3\times(1+2\times(1+1)))))$$

putting this all in a calculator the final result becomes $$985824$$ which is fairly a small number compared to other answers. As the number is pretty small, it is possible to count directly using a brute force algorithm. This has been done by a google engineer in here, and the result found by him for android unlock combination ($389112$) is less than half the value I computed.

Solution 2:

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.

Solution 3:

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)$.