# Paths on a dodecahedron

Looking at this question, I misread "dodecagon" as "dodecahedron". I think the latter is a cool problem, so I'm posing it as a question of its own :)

Starting from one vertex of a dodecahedron, an ant wants to reach the opposite vertex of the dodecahedron, moving to adjacent vertices. If $p_n$ is the number of such paths with length $n$, compute $p_1+p_2+\dots+p_{12}$.

• $p_1=p_2=p_3=p_4=0$ – Alexander Burstein Dec 23 '17 at 4:37
• The dodecagon, expressed as a graph, is a cycle. Hence, walks of a specific length have very clear structure, and one can exploit that structure to solve the problem. In contrast, the dodecahedron graph is a big beautiful mess. Even calculating $p_5$ is not obvious (and would make a fine question on its own). Calculating larger and larger $p_k$ can only be done by computer. – vadim123 Dec 23 '17 at 16:01
• Paths or simple paths? – MJD Dec 23 '17 at 16:25
• @vadim123 $p_5=6$, $p_6=12$, and both take less than a minute to compute when you look at a picture of a dodecahedron. – Yly Dec 24 '17 at 19:26
• @MJD Paths, not simple paths. – Yly Dec 24 '17 at 19:27

Let $$A$$ be the adjacency matrix. Then $$A^k$$ gives you the number of paths of length $$k$$ between corresponding vertices. (This works for any graph.) This can computed very quickly, and you can also get asymptotics and so on, by computing eigenvalues.

For example, there are

171619248

such paths of length 20 (not too far from MJD's guess), and

25768876036573921452762172776956776774411837488

such paths of length 100.

It is not necessary to set up the full adjacency matrix of the dodecahedron. Drawing the edge graph with the starting vertex $$v_0$$ at the center and the opposite vertex at infinity one realizes that due to symmetry there are just six classes $$C_i$$ $$(0\leq i\leq5)$$ of vertices.

It is therefore sufficient to consider the numbers $$p_i(n)$$, whereby $$p_i(n)$$ denotes the number of ways to reach a vertex of class $$C_i$$ in exactly $$n$$ steps, starting at $$v_0$$. Looking at my drawing I then obtain the following equations: $${\bf p}(n+1)=\left[\matrix {0&3&0&0&0&0\cr 1&0&2&0&0&0\cr 0&1&1&1&0&0\cr 0&0&1&1&1&0\cr 0&0&0&2&0&1\cr 0&0&0&0&3&0\cr}\right]\>{\bf p}(n)\ ,$$ whereby $${\bf p}(n)$$ denotes the column vector of the $$p_i(n)$$.

Since there are so many treatments of the problem already I stop here.

• I hope it is all right with you that I added a diagram. If you want to change the design, the original SVG image is available for editing. – MJD Nov 14 '18 at 15:45
• @MJD: That's exactly the drawing I had. Thank you very much!! – Christian Blatter Nov 14 '18 at 16:09
• This is a nice observation! – Travis Nov 14 '18 at 21:24

One way to count paths on a graph $$\Gamma$$, say, with vertices $$v_i$$, is to use its adjacency matrix: This is the square matrix $$A_{\Gamma}$$ of size $$|\Gamma|$$ for which the $$(i, j)$$ entry $$(A_{\Gamma})_{ij}$$ is the number of edges with endpoints at vertices $$v_i$$ and $$v_j$$. An intuitive inductive argument then shows that the number of paths of length $$n$$ from $$v_i$$ to $$v_j$$ is exactly $$(A_{\Gamma}^n)_{ij}$$.

The SageMath code Delta = graphs.DodecahedralGraph(); Delta.plot() assigns the dodecahedral graph the name Delta and returns the following labeled plot of the graph, which we call $$\Delta$$. NB Sage starts indexing at $$0$$. A little visualization shows that, e.g., the vertex opposite $$v_0$$ is vertex $$v_{15}$$.

Next, the Sage command A = dodecahedral.adjacency_matrix() assigns to A the adjacency matrix $$A_{\Delta}$$ of $$\Delta$$; it has size $$|\Delta| = 20$$.

$$\small A_{\Delta} = \pmatrix{ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 } .$$

Using our above combinatorial interpretation of $$A_{\Delta}^n$$ gives that the number of paths of length $$n$$ from $$v_0$$ to the opposite vertex $$v_{15}$$ is $$\boxed{p_n = (A_{\Delta}^n)_{0, 15}}.$$ Asking Sage to compute $$p_1, \ldots, p_{12}$$ and add them, say, using the code n = var('n'); sum([(A^n)[0, 15] for n in range(1,13)]), gives that $$\color{#df0000}{\boxed{p_1 + \cdots + p_{12} = 34548}} ,$$ which agrees with MJD's count.

One can derive this in a more illuminating way. To compute $$A_{\Gamma}^n$$ efficiently, it is useful to use the Jordan decomposition $$A_{\Gamma} = Q J Q^{-1}$$. Then, $$A_{\Gamma}^n = (Q J Q^{-1})^n = Q J^n Q^{-1}$$. Since an adjacency matrix (of an undirected graph) is symmetric, $$A_{\Gamma}$$ is diagonalizable and thus $$J$$ is diagonal, say, $$J = \operatorname{diag}(\lambda_i)$$, and $$J^n = \operatorname{diag}(\lambda_i^n)$$.

Now, the number of paths of length $$n$$ from $$v_i$$ to $$v_j$$ is $$(A_{\Delta}^n)_{ij} = (Q J^n Q^{-1})_{ij} = \sum_{k, \ell} Q_{ik} (J^n)_{k \ell} Q^{-1}_{\ell j} ,$$ and since $$J^n$$ is diagonal with entries $$\lambda_a^n$$, terms only contribute to the sum when $$\ell = k$$, leaving $$(A_{\Delta}^n)_{ij} = \sum_k (Q_{ik} Q^{-1}_{kj}) \lambda_k^n .$$ The number of paths from $$v_i$$ to $$v_j$$ of length $$\leq m$$ is then the partial sum $$\sum_{n = 0}^m (A_{\Delta}^n)_{ij} =\sum_{n = 0}^m \sum_k (Q_{ik} Q^{-1}_{kj}) \lambda_k^n =\sum_k (Q_{ik} Q^{-1}_{kj}) \sum_{n = 0}^m \lambda_k^n =\sum_k (Q_{ik} Q^{-1}_{kj}) \frac{\lambda_k^{m + 1} - 1}{\lambda_k - 1},$$ where we interpret $$\frac{\lambda_k^{m + 1} - 1}{\lambda_k - 1}$$ as $$m + 1$$ if $$\lambda_k = 1$$.

For the dodecahedral graph $$\Delta$$, the Jordan decomposition (produced, for example, using A.change_ring(QQ[sqrt(5)]).jordan_form(transformation=True)), is given by

$$J = \operatorname{diag}(3, \sqrt{5}, \sqrt{5}, \sqrt{5}, -\sqrt{5}, -\sqrt{5}, -\sqrt{5}, 0, 0, 0, 0, -2, -2, -2, -2, 1, 1, 1, 1, 1) ,$$ $$\begin{multline*}Q \\ = \scriptsize \pmatrix{ 1 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 1 & 1 & -\phi & \phi & 1 & \phi^{-1} & -\phi & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 1 & \phi^{-1} & -2 & \phi & -\phi & -2 & -\phi & 1 & 1 & 0 & 1 & 1 & 1 & 0 & -1 & 0 & 0 & 0 & 0 & 1 \\ 1 & -\phi & -\phi & 1 & \phi & \phi & 1 & -1 & 0 & -1 & -1 & -1 & 0 & 1 & 1 & 1 & -1 & 1 & -1 & 1 \\ 1 & -1 & \phi^{-1} & \phi^{-1} & -1 & -\phi & -\phi & 0 & -1 & 0 & -1 & 0 & -1 & -2 & -1 & 0 & -1 & 1 & -1 & 0 \\ 1 & -\phi & 2 & -\phi & \phi^{-1} & 2 & \phi & 1 & 0 & 0 & 1 & 1 & 2 & 2 & 1 & -1 & 0 & -1 & 0 & -1 \\ 1 & -1 & \sqrt{5} & -1 & -1 & -\sqrt{5} & -1 & -1 & 0 & -1 & 0 & -1 & -2 & -1 & 0 & -1 & 1 & -1 & 0 & 0 \\ 1 & -\phi & 2 & -\phi & \phi & 2 & \phi^{-1} & -1 & -1 & 0 & -1 & 1 & 1 & 0 & -1 & 0 & 0 & 0 & 0 & 1 \\ 1 & \phi^{-1} & \phi^{-1} & -1 & -\phi & -\phi & -1 & 1 & 0 & 1 & 1 & -1 & 0 & 1 & 1 & 1 & -1 & 1 & -1 & 1 \\ 1 & 1 & -\phi & -\phi & 1 & \phi & \phi & 0 & 1 & 0 & 1 & 0 & -1 & -2 & -1 & 0 & -1 & 1 & -1 & 0 \\ 1 & 0 & 0 & -1 & 0 & 0 & -1 & 0 & 0 & -1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 1 & -1 & \phi & -\phi & -1 & -\phi & \phi^{-1} & 0 & 0 & 0 & -1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 1 & -\phi & \phi & -1 & \phi^{-1} & -\phi & -1 & 1 & 1 & 1 & 1 & -1 & -1 & -1 & -1 & 0 & 0 & -1 & 1 & -1 \\ 1 & -1 & 0 & 0 & -1 & 0 & 0 & -1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & -1 & 0 & 0 & -1 & 0 & 0 & -1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & -\sqrt{5} & 1 & 1 & \sqrt{5} & 1 & 1 & 0 & 1 & 0 & -1 & -2 & -1 & 0 & -1 & 1 & -1 & 0 & 0 \\ 1 & \phi & -2 & \phi^{-1} & -\phi & -2 & -\phi & -1 & 0 & 0 & -1 & 1 & 2 & 2 & 1 & -1 & 0 & -1 & 0 & -1 \\ 1 & \phi & -\phi & 1 & -\phi & \phi^{-1} & 1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & 0 & 0 & -1 & 1 & -1} .\end{multline*}$$ Here, $$\phi := \frac{1}{2}(1 + \sqrt{5})$$ is the Golden Ratio.

Taking $$i = 0, j = 15$$ and substituting (or just executing (A^n)[0, 15]) gives $$\boxed{p_n = (A_{\Delta}^n)_{0, 15} = \frac{1}{20} \cdot 3^n - \frac{3}{20} (1 + (-1)^n) (\sqrt{5})^n + \frac{1}{5} \, \left(-2\right)^n + \frac{1}{4}}.$$ (This agrees with the formula given in OEIS A054883, Number of walks of length n along the edges of a dodecahedron between two opposite vertices.) Then, the number of such paths of length $$\leq m$$ is the partial sum $$s_m = \sum_{n = 0}^m p_n$$, and indeed, $$s_{12} = 34548$$ as claimed.

For large $$n$$, the formula for $$p_n$$ is dominated by the first term, so $$p_n \sim \frac{1}{20} \cdot 3^n$$; so, for large $$m$$, $$s_m \sim \frac{1}{40} \cdot 3^{m + 1}$$.

Edit A Christian Blatter observed in his answer, exploiting the symmetry of the dodecahedron translates the problem into a path-counting problem on the digraph $$\Delta'$$ of classes $$C_0, \ldots, C_5$$ of vertices, where $$C_k$$ consists of the vertices of distance $$k$$ from $$v_0$$. This yields the adjacency matrix $$A_{\Delta'} = \pmatrix{ 0&3&0&0&0&0\cr 1&0&2&0&0&0\cr 0&1&1&1&0&0\cr 0&0&1&1&1&0\cr 0&0&0&2&0&1\cr 0&0&0&0&3&0\cr}.$$ The number of paths of length $$n$$ from $$C_0$$ (which contains only a single vertex) to $$C_5$$ (which contains its antipodal vertex) is then $$(A_{\Delta'}^n)_{05}$$. As before, we can compute this efficiently with the Jordan decomposition $$A_{\Delta'} = Q' J' (Q')^{-1}$$, where $$J' = \operatorname{diag}(3, \sqrt{5}, 1, 0, -2, -\sqrt{5}), \qquad Q' = \pmatrix{ 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & \frac{1}{3} \sqrt{5} & \frac{1}{3} & 0 & -\frac{2}{3} & -\frac{1}{3} \sqrt{5} \\ 1 & \frac{1}{3} & -\frac{1}{3} & -\frac{1}{2} & \frac{1}{6} & \frac{1}{3} \\ 1 & -\frac{1}{3} & -\frac{1}{3} & \frac{1}{2} & \frac{1}{6} & -\frac{1}{3} \\ 1 & -\frac{1}{3} \sqrt{5} & \frac{1}{3} & 0 & -\frac{2}{3} & \frac{1}{3} \sqrt{5} \\ 1 & -1 & 1 & -1 & 1 & -1 . } .$$

I'm still working out a combinatorial method of calculating the answer, and I may not be successful. In the meantime, here are the results from a computer enumeration of all paths: $$\begin{array}{rrr} \text{Length} & \text{Simple paths} & \text{All paths} \\ 5 & 6 & 6 \\ 6 & 12 & 12 \\ 7 & 6 & 84 \\ 8 & 12 & 192 \\ 9 & 30 & 882 \\ 10 & 24 & 2\;220 \\ 11 & 42 & 8\;448 \\ 12 & 84 & 22\;704 \\ 13 & 96 & 78\;078 \\ 14 & 132 & 218\;988 \\ 15 & 150 & 710\;892 \\ 16 & 72 & 2\;048\;256 \\ 17 & 48 & 6\;430\;794 \\ 18 & 60 & 18\;837\;516\\ 19 & 6 & 58\;008\;216\\ \hline \text{Total} & 780 & 86\;367\;288 \end{array}$$

The complete enumeration of paths took around half an hour on my laptop, and the output file is 5.3 GB raw, 0.25 GB compressed. For theoretical reasons as well as empirical, we can guess that there would be around 180 million paths of length 20, and that computing them would take around 55 minutes. (After computing the $1\;042\;506$ paths up to length 15, I guessed there would be around 81 times as many paths of length up to 19, or $84\;442\;986$, which is quite close to the correct result.)

• Out of curiosity, did you ever find a combinatoral method? – tox123 Nov 4 '18 at 21:56
• No, I moved on to other things. Thanks for the reminder; I might take it up again. I love thinking about dodecahedra. – MJD Nov 4 '18 at 23:15
• @tox123I took another shot at it this morning. I did find a method that works well for the tetrahedron and the cube. (For a cube, I think there are 6, 0, 60, 0, 546 paths of length 3, 4, 5, 6, 7 between a vertex and its antipode.) But the method I was using turns out to be more difficult for the dodecahedron. I will consider further. – MJD Nov 7 '18 at 15:10
• interestingly, the OEIS doesn't even have the cube sequence. – tox123 Nov 11 '18 at 4:39
• @tox123 oeis.org/A054880 – MJD Nov 11 '18 at 5:52