Csdrhrt

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

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$ $(0leq ileq5)$ 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&0cr
1&0&2&0&0&0cr
0&1&1&1&0&0cr
0&0&1&1&1&0cr
0&0&0&2&0&1cr
0&0&0&0&3&0cr}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.

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(-2right)^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&0cr
1&0&2&0&0&0cr
0&1&1&1&0&0cr
0&0&1&1&1&0cr
0&0&0&2&0&1cr
0&0&0&0&3&0cr}.$$
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.)