Primero una corrección con respecto a la conexión con los polinomios de Chebyshev. Citando de Chris Godsil respuesta a su pregunta anterior:
Observar que
$$
p_0(A)=I,\quad p_1(A) =A,\quad p_2(A) = A^2-\Delta,
$$
donde $\Delta$ es la matriz diagonal de valencies de $X$. Si $n\ge3$ tenemos la recurrencia
$$
Ap_n(A) = p_{n+1}(A) +(\Delta-I) p_{n-1}(A).
$$
(He cambiado de $r$ $n$en el citado texto.) Para cúbicos gráficos, $\Delta=3I$, que se traduce en la repetición
$$
p_{n+1}(t)=tp_n(t)−2p_{n−1}(t).
$$
Esto está relacionado con la recurrencia de los polinomios de Chebyshev por un cambio de variable,
$$
p_{n+1}(2^{3/2}t)=2^{3/2}tp_n(2^{3/2}t)−2p_{n−1}(2^{3/2}t),
$$
seguido por un reescalado,
$$
2^{−(n+1)/2}p_{n+1}(2^{3/2}t)=2t\cdot2^{−n/2}p_n(2^{3/2}t)-2^{−(n−1)/2}p_{n−1}(2^{3/2}t).
$$
Por lo tanto $q_n(t):=2^{−n/2}p_n(2^{3/2}t)$ satisface la Chebyshev recurrencia, $q_{n+1}(t)=2tq_n(t)-q_{n-1}(t)$. Esto puede ser usado para obtener el $q_n(t)$$n\ge3$. Para $n<3$,
$$
q_0(t)=1,\quad q_1(t)=2t,\quad q_2(t)=4t^2-3/2.
$$
Los polinomios de Chebyshev de la segunda clase son generados a partir de la misma recurrencia con las condiciones iniciales
$$
U_0(t)=1,\quad U_1(t)=2t,
$$
que se traducen en
$$
U_2(t)=4t^2-1
$$
en lugar de $4t^2-3/2$. La aparición de la $3/2$ plazo $q_2(t)$ puede atribuirse a la aparición de $\Delta$ en lugar de $\Delta-I$ en la expresión de $p_2(A)$. La recurrencia implica que $U_{-1}(t)=0$. Como consecuencia de ello,
$$
q_n(t)=U_n(t)-\frac{1}{2}U_{n-2}(t)
$$
tiene por $n=1$$n=2$. Por la linealidad de la recurrencia, esto se extiende a todos los $n\ge1$. No tiene por $n=0$, sin embargo, desde la $U_{-2}(t)=-1$.
De $p_n(t)=2^{n/2}q_n(2^{-3/2}t)$ se sigue que
$$
p_n(t)=2^{n/2}U_n(2^{-3/2}t)-2^{(n-2)/2}U_{n-2}(2^{-3/2}t)
$$
para $n\ge1$. El MathWorld expresión que se cita a continuación, implica que
$$
2^{n/2}U_n(2^{-3/2}t)=\sum_{i=0}^{\lfloor n/2\rfloor}(-2)^r\binom{n−r}{r}t^{n−2r},
$$
y, por tanto, que
$$
p_n(x)=\sum_{i=0}^{\lfloor n/2\rfloor}(-2)^r\binom{n-r}{r}x^{n-2r}-\sum_{i=0}^{\lfloor (n-2)/2\rfloor}(-2)^r\binom{n-2-r}{r}x^{n-2-2r}.
$$
Cambio de la suma de los índices de la segunda suma en la expresión anterior y llevar el signo menos en el interior de da
$$
p_n(x)=\sum_{i=0}^{\lfloor n/2\rfloor}(-2)^r\binom{n-r}{r}x^{n-2r}+\sum_{i=1}^{\lfloor n/2\rfloor}(-1)(-2)^{i-1}\binom{n-1-r}{r-1}x^{n-2r},
$$
que es una forma útil para el propósito de la interpretación.
Original respuesta: Esta fórmula puede ser entendido en términos de proceso de forma iterativa llevar a cabo la recurrencia a Chris Godsil respuesta, lo que da lugar a las sumas de los productos de $A$$\Delta$. Definir
$$
\Delta':=\begin{cases}\Delta & \text{if first factor in the product}\\ \Delta-I & \text{otherwise.}\end{casos}$$
Tenga en cuenta que para cúbicos gráficos,
$$
\Delta':=\begin{cases}3I& \text{if first factor in the product}\\ 2I & \text{otherwise.}\end{casos}$$
Comenzando con $p_1(A)=A$, $p_{n+1}(A)$ se obtiene a partir de a $p_n(A)$ por
- añadiendo un factor de $A$ a cada término de la suma;
- para cualquier término en la suma resultante que termina con dos consecutivos factores de $A$, restando el producto que resulta de la sustitución de estos dos últimos factores de $A$ con un solo factor de $\Delta'$.
La realización de esta en el caso de $n=1$, el Paso 1 da $AA$ y en el Paso 2 da $AA-\Delta'$, con el resultado de $$p_2(A)=AA-\Delta'.$$ Then for $n=2$, Step 1 gives $AAA-\Delta'A$, and Step 2 gives $-A\Delta'$, with the result $$p_3(A)=AAA-\Delta'A-A\Delta'.$$ One more time: Step 1 gives $AAAA-\Delta'AA-A\Delta'A$ and Step 2 gives $-AA\Delta'+\Delta'\Delta'$, with the result $$p_4(A)=AAAA-\Delta'AA-A\Delta'A-AA\Delta'+\Delta'\Delta'.$$
Debe quedar claro que el resultado de la repetición es que $p_n(A)$ es una suma con las siguientes características:
- cada cadena de peso $n$ consta de $A$ $\Delta'$ ocurre exactamente una vez; aquí el peso se calcula como: $$(\text{number of $$s})+2\cdot(\text{number of $\Delta'$s})$$
desde cada una de las $\Delta'$ sustituye a los dos $A$s;
- el signo es igual a $$(-1)^\text{number of $\Delta'$s}.$$
La suma puede tener en cualquier lugar entre el $0$ y $\lfloor n/2\rfloor$ $\Delta'$s. Una cadena que contiene $r$ $\Delta'$s consta de $n-r$ símbolos desde cada una de las $\Delta'$ peso $2$. Por lo tanto, hay $\binom{n-r}{r}$ cadenas con $r$ $\Delta'$s.
Estas observaciones pueden ser relacionados con la expresión de $p_n(x)$ dado anteriormente. Empezamos por la incorrecta colocación de cada una de las apariciones de $\Delta'$ en cada una de las cuerdas con $2I$. Esto le da a la fórmula incorrecta
$$
p_n(A)=\sum_{i=0}^{\lfloor n/2\rfloor}(-2)^r\binom{n-r}{r}^{n-2r}.
$$
La fórmula es incorrecta porque la primera $\Delta'$ en una cadena que debería haber sido reemplazado con $3I$ en lugar de $2I$ si $\Delta'$ fueron la primera letra de la cadena. Por lo tanto, corregir nuestros expresión mediante la adición de $(-1)\cdot(-2)^{r-1}A^{n-2r}$ para cada cadena con $r$ $\Delta'$s en la que $\Delta'$ es la primera letra. Hay $\binom{n-1-r}{r}$ tales cadenas. Como resultado, la expresión correcta es
$$
p_n(A)=\sum_{i=0}^{\lfloor n/2\rfloor}(-2)^r\binom{n-r}{r}^{n-2r}+\sum_{i=1}^{\lfloor n/2\rfloor}(-1)\cdot(-2)^{i-1}\binom{n-1-r}{r}^{n-2r}.
$$
Nueva respuesta (19 de Mayo de 2015): los poderes de La $-1$ sugieren que la suma surge desde el principio de inclusión-exclusión. En términos generales, dado un conjunto finito $S$ y un conjunto $T$, el tamaño de la dotación de $T$ está dado por
$$
\lvert T'\rvert=\lvert S\rvert-\sum_{i=1}^N S_i+\sum_{1\le i<j\le N}S_i\cap S_j-\sum_{1\le i<j<k\le N}S_i\cap S_j\cap S_k+\ldots,
$$
donde $S_1$, $S_2$, $\ldots$, $S_N$ son subconjuntos de a $S$ cuya unión es $T$. En su problema, el papel de la $S$ es interpretado por el conjunto de rutas de $a$ $b$de la longitud de la $n$, que denominaremos $P(a,b,n,\{\})$; el papel de la $T$ es desempeñado por el subconjunto de $P(a,b,n,\{\})$ compuesta por aquellas rutas que contienen al menos uno de revertir el paso, y el papel de la $T'$ es desempeñado por el subconjunto de $P(a,b,n,\{\})$ consta de los caminos por los que no contienen revertir el paso.
Para llevar a cabo una inclusión-exclusión en el cálculo, el primer paso es elegir los conjuntos de jugar el papel de $S_i$. Una elección natural es el uso de los conjuntos de
$$
P(a,b,n,\{j\})=\text{conjunto de rutas de $a$ $b$de la longitud de la $n$ en el que paso a $j$ invierte paso $j-1$,}
$$
donde $j$ rangos de$2$$n$. Está claro que la unión de estos conjuntos es el conjunto de rutas de $a$ $b$de la longitud de la $n$ que contiene uno o más de revertir los pasos. En la realización de la inclusión-exclusión suma que uno necesita para calcular los tamaños de las intersecciones de dos o más conjuntos—intersecciones como $P(a,b,n,\{j\})\cap P(a,b,n,\{k\})=:P(a,b,n,\{j,k\})$, por ejemplo. En este ejemplo, el tamaño de la intersección depende de si $k=j+1$ o $k>j+1$, y esto hace que el cálculo de un poco implicado. Se lleva a cabo en este post.
Ya que el único requisito en los conjuntos de $S_i$ es que su unión igualdad de $T$, muchas opciones son posibles. En este problema, la mejor opción para los conjuntos a jugar el papel de $S_i$ son los conjuntos de
$$
\begin{aligned}
R(a,b,n,\{j\})=\,&\text{set of paths from %#%#% to %#%#% of length %#%#% in which step %#%#% reverses step %#%#% and}\\
&\text{step %#%#% does not reverse step %#%#%,}
\end{aligned}
$$
donde de nuevo $a$ rangos de$b$$n$. (Al $j$ consideramos la condición de que el paso $j-1$ no paso hacia atrás $j-1$ a ser vacuously cierto como que no hay paso $j-2$.) De nuevo, la unión de estos conjuntos es el conjunto de todos los caminos de $j$ $2$de la longitud de la $n$ que contiene uno o más de revertir los pasos. Esto se deduce del hecho de que en cualquier ruta de acceso que contiene una reversión de paso, hay una revertir el paso de menor índice. Por lo tanto, si que menos índice de es $j=2$, entonces el camino está contenida en $1$.
Desde $0$, sólo tenemos que considerar el caso de $0$ $a$ y, de forma más general, las intersecciones como $b$ que $n$ para todos los distintos $j$, $R(a,b,n,\{j\})$ en $R(a,b,n,\{j\})\cap R(a,b,n,\{j+1\})=\emptyset$. Vamos a suponer que esta condición a partir de ahora.
El conjunto $R(a,b,n,\{j\})\cap R(a,b,n,\{k\})=:R(a,b,n,\{j,k\})$ de todas las rutas de $k>j+1$ $R(a,b,n,\{j_1\})\cap\ldots\cap R(a,b,n,\{j_r\})=:R(a,b,n,\{j_1,\ldots,j_r\})$de la longitud de la $\lvert j_k-j_i\rvert\ge2$ tiene un tamaño dado por el $i$ elemento $k$. Para controlar el caso de que una reversión de paso es necesario en una posición determinada, es necesario considerar los productos en los que un par de $\{1,2,\ldots,r\}$s ha sido sustituido por $R(a,b,n,\{\})$ o $a$. Se utiliza la definición de $b$ dado en la anterior respuesta. Desde una reversión en el paso $n$ implica que el mismo vértice es visitado después de la $(a,b)$ $A^n$ pasos, y ya si $A$ el vértice visitado después de la $\Delta$ paso no puede ser la misma que visitó inmediatamente antes de la $\Delta-I$ paso, $\Delta'$ $j$ elemento de
$$
A^{j−2}\Delta A^{n−j}=
\begin{cases}(3I)A^{n-2}=3A^{n-2} & \text{if %#%#%,}\\
A^{j−2}(2I)A^{n−j}=2A^{n−2} & \text{if %#%#%.}
\end{casos}
$$
En otras palabras, los dos factores de $(j−2)^\text{nd}$ en las posiciones $j^\text{th}$ $j>2$ $(j-1)^\text{st}$ han sido reemplazados con $(j-2)^\text{nd}$. Por el mismo argumento, $\lvert R(a,b,n,\{j\})\rvert$ $(a,b)$ elemento del producto en el que los dos $j=2$s en cada uno de los pares de posiciones $j>2$, $A$, $j-1$ en el producto $j$ reemplazados con $A^n$. Debido a la condición de $\Delta'$ para los distintos $\lvert R(a,b,n,\{j_1,\ldots,j_r\})\rvert$, $(a,b)$, estos reemplazos nunca se producen en la superposición de posiciones y por lo tanto se puede realizar de forma independiente el uno del otro. Denotar por $A$ el conjunto de los subconjuntos de a $(j_1-1, j_1)$ del tamaño de la $\ldots$ en el que esta "diferencia-$(j_r-1,j_r)$" condición se mantiene.
Por el principio de inclusión-exclusión, el número de caminos de $A^n$ $\Delta'$de la longitud de la $\lvert j_k-j_i\rvert\ge2$ sin invertir pasos está dada por
$$
\sum_{i=0}^{\lfloor n/2\rfloor}(-1)^r\sum_{Un\en D_r}\lvert R(a,b,n,A)\rvert.
$$
Este es igual al $i$ elemento de
$$
\sum_{i=0}^{\lfloor n/2\rfloor}(-1)^r\sum_{Un\en D_r}[2+\mathbf{1}_A(2)]2^{i-1}^{n-2r}=\sum_{i=0}^{\lfloor n/2\rfloor}(-1)^r\left[\sum_{Un\en D_r}2^rA^{n-2r}+\sum_{Un\en D_r,2\en A}2^{i-1}^{n-2r}\right],
$$
donde $k$ es el indicador de la función cuyo valor es $D_r$ si $\{2,3,\ldots,n\}$ $r$ si $2$. Hay una correspondencia uno a uno entre los elementos de las $a$ y las cadenas que contienen $b$ $n$s y $(a,b)$ $\mathbf{1}_A(x)$s. Hay una correspondencia uno a uno entre los elementos de las $1$ contiene $x\in A$ y las cadenas que contienen $0$ $x\notin A$s y $D_r$ $n-2r$s tales que el primer elemento de la cadena es una $A$. Esto implica que hay $r$ elementos en $\Delta'$ $D_r$ elementos en $s$ que contengan $n-2r$. La suma dada en mi anterior respuesta de los resultados.
