Caminos en un dodecaedro

Dejar$A$Sea la matriz de adyacencia. Entonces$A^k$te da el número de caminos de longitud$k$entre vértices correspondientes. (Esto funciona para cualquier gráfico). Esto se puede calcular muy rápidamente, y también se pueden obtener asintóticas, etc., calculando los valores propios.

por ejemplo, hay

171619248

tales caminos de longitud 20 (no muy lejos de la conjetura de MJD), y

25768876036573921452762172776956776774411837488

caminos de longitud 100.

No es necesario configurar la matriz de adyacencia completa del dodecaedro. Dibujar el gráfico de borde con el vértice inicial$v_0$en el centro y el vértice opuesto en el infinito uno se da cuenta de que debido a la simetría solo hay seis clases$C_i$ $(0\leq i\leq5)$de vértices.

Por lo tanto, es suficiente considerar los números$p_i(n)$, por lo que$p_i(n)$denota el número de formas de llegar a un vértice de clase$C_i$exactamente$n$pasos, a partir de$v_0$. Mirando mi dibujo, obtengo las siguientes ecuaciones:

$${\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)\ ,$$ por lo cual${\bf p}(n)$denota el vector columna del$p_i(n)$.

Dado que ya existen tantos tratamientos para el problema, me detengo aquí.

Una forma de contar caminos en un gráfico$\Gamma$, digamos, con vértices$v_i$, es usar su matriz de adyacencia : Esta es la matriz cuadrada$A_{\Gamma}$de tamaño$|\Gamma|$para el cual el$(i, j)$entrada$(A_{\Gamma})_{ij}$es el número de aristas con extremos en los vértices$v_i$y$v_j$. Un argumento inductivo intuitivo muestra entonces que el número de caminos de longitud$n$de$v_i$a$v_j$es exactamente$(A_{\Gamma}^n)_{ij}$.

El código de SageMathDelta = graphs.DodecahedralGraph(); Delta.plot() asigna el nombre al gráfico dodecaédrico Deltay devuelve el siguiente diagrama etiquetado del gráfico, al que llamamos$\Delta$. NB Sage comienza a indexar en$0$. Una pequeña visualización muestra que, por ejemplo, el vértice opuesto$v_0$es vértice$v_{15}$.

A continuación, el comando Sage A = dodecahedral.adjacency_matrix()asigna a Ala matriz de adyacencia$A_{\Delta}$de$\Delta$; tiene tamaño$|\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 } .$$

Usando nuestra interpretación combinatoria anterior de$A_{\Delta}^n$da que el número de caminos de longitud$n$de$v_0$al vértice opuesto$v_{15}$es

$$\boxed{p_n = (A_{\Delta}^n)_{0, 15}}.$$ Pedirle a Sage que calcule$p_1, \ldots, p_{12}$y agregarlos, digamos, usando el código n = var('n'); sum([(A^n)[0, 15] for n in range(1,13)]), da eso $$\color{#df0000}{\boxed{p_1 + \cdots + p_{12} = 34548}} ,$$ lo que concuerda con el conteo de MJD.

Uno puede derivar esto de una manera más esclarecedora. Computar$A_{\Gamma}^n$eficientemente, es útil utilizar la descomposición de Jordan$A_{\Gamma} = Q J Q^{-1}$. Entonces,$A_{\Gamma}^n = (Q J Q^{-1})^n = Q J^n Q^{-1}$. Dado que una matriz de adyacencia (de un gráfico no dirigido) es simétrica,$A_{\Gamma}$es diagonalizable y por lo tanto$J$es diagonal, digamos,$J = \operatorname{diag}(\lambda_i)$, y$J^n = \operatorname{diag}(\lambda_i^n)$.

Ahora, el número de caminos de longitud$n$de$v_i$a$v_j$es

$$(A_{\Delta}^n)_{ij} = (Q J^n Q^{-1})_{ij} = \sum_{k, \ell} Q_{ik} (J^n)_{k \ell} Q^{-1}_{\ell j} ,$$ y desde$J^n$es diagonal con entradas$\lambda_a^n$, los términos sólo contribuyen a la suma cuando$\ell = k$, partida $$(A_{\Delta}^n)_{ij} = \sum_k (Q_{ik} Q^{-1}_{kj}) \lambda_k^n .$$ El número de caminos desde$v_i$a$v_j$de longitud$\leq m$es entonces la suma parcial $$\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},$$ donde interpretamos$\frac{\lambda_k^{m + 1} - 1}{\lambda_k - 1}$como$m + 1$si$\lambda_k = 1$.

Para el gráfico dodecaédrico$\Delta$, la descomposición de Jordan (producida, por ejemplo, utilizando A.change_ring(QQ[sqrt(5)]).jordan_form(transformation=True)), viene dada por

$$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*}$$ Aquí,$\phi := \frac{1}{2}(1 + \sqrt{5})$es la proporción áurea.

Tomando$i = 0, j = 15$y sustituyendo (o simplemente ejecutando (A^n)[0, 15]) da

$$\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}}.$$ (Esto concuerda con la fórmula dada en OEIS A054883 , Número de caminos de longitud n a lo largo de los bordes de un dodecaedro entre dos vértices opuestos ). Entonces, el número de tales caminos de longitud$\leq m$es la suma parcial$s_m = \sum_{n = 0}^m p_n$, y de hecho,$s_{12} = 34548$como se afirma.

Para grande$n$, la fórmula para$p_n$está dominada por el primer término, por lo que$p_n \sim \frac{1}{20} \cdot 3^n$; así, para grandes$m$,$s_m \sim \frac{1}{40} \cdot 3^{m + 1}$.

Editar Un Christian Blatter observó en su respuesta, explotar la simetría del dodecaedro traduce el problema en un problema de conteo de caminos en el dígrafo$\Delta'$de clases$C_0, \ldots, C_5$de vértices, donde$C_k$consta de los vértices de la distancia$k$de$v_0$. Esto produce la matriz de adyacencia

$$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}.$$ El número de caminos de longitud$n$de$C_0$(que contiene un solo vértice) a$C_5$(que contiene su vértice antípoda) es entonces$(A_{\Delta'}^n)_{05}$. Como antes, podemos calcular esto eficientemente con la descomposición de Jordan$A_{\Delta'} = Q' J' (Q')^{-1}$, dónde $$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 . } .$$

Todavía estoy trabajando en un método combinatorio para calcular la respuesta y es posible que no tenga éxito. Mientras tanto, aquí están los resultados de una enumeración por computadora de todas las rutas:

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

La enumeración completa de rutas tomó alrededor de media hora en mi computadora portátil, y el archivo de salida es de 5,3 GB sin formato, 0,25 GB comprimido. Por razones tanto teóricas como empíricas, podemos suponer que habría alrededor de 180 millones de caminos de longitud 20, y que calcularlos tomaría alrededor de 55 minutos. (Después de calcular el$1\;042\;506$caminos de longitud hasta 15, supuse que habría alrededor de 81 veces más caminos de longitud hasta 19, o$84\;442\;986$, que está bastante cerca del resultado correcto.)