# 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
@F.M. The answer you accepted is not correct, and does accurately address your question. –  Eric Naslund May 5 at 15:28

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). –  F M 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
In this solution you can even use the same edge multiple times –  dREaM Jun 23 '14 at 2:06

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.

-
+1, this is the only correct answer here. –  Eric Naslund May 5 at 15:29

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

-
f(9) = 3 922 631 631 –  Gleno Jul 12 '14 at 17:20

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.

-