How many paths of length $7$ are there in a complete graph $K_{12}$ between vertices $A$ and $B$?

Question

I have following to solve: I have a $K_{12}$ complete graph and should find all possible paths (exactly with length equal to $7$) between graph vertices $A$ and $B$.

Answer 1

If $A, B$ are fixed vertices, then this is equivalent to finding a permutation of 6 vertices out of 10.

If the starting and ending vertices are not fixed, then this is equivalent to finding a permutation of 8 vertices out of 12.

Answer 2

Another approach considers the adjacency matrix of the graph: Given a graph $G$ with $n$ vertices, fix an enumeration, and define its adjacency matrix $A=A_G$ to be the $n\times n$ matrix with entries $1$ or $0$, whose $(i,j)$ entry is $1$ iff there is an edge in $G$ between the $i$th and the $j$th vertices. An easy induction verifies that the $(i,j)$ entry of $A^m$ is precisely the number of paths of length exactly $m$ between the $i$th and the $j$th vertices.

In the case that concerns us, $G=K_{12}$, so $A=J-I$ where $J$ is the $12\times 12$ matrix, all of whose entries are $1$, and $I$ is the identity. Since $J$ and $I$ commute, $(J-I)^7$ can be found via the binomial theorem, using that $J^m$ is the matrix all of whose entries equal $12^{m-1}$, as another easy induction verifies. Note the final answer is different depending on whether the two vertices coincide or not. Specifically, the $(i,j)$ entry of $A^7$ is $$ 12^6-7\times 12^5+\binom72 12^4-\binom73 12^3+\binom 74 12^2-\binom 75 12+7\times 1-c,$$ where $c=1$ if $i=j$ and $c=0$ otherwise. Note that this is just $$ \frac{(12-1)^7+1}{12}-c=\frac {11^7+1}{12}-c=1623931-c, $$ that is, if the two vertices $i$ and $j$ are the same, then there are exactly $1\,623\,930$ paths between them, and otherwise there are $1\,623\,931$ paths. Note that some of these paths may pass through some vertices more than once.