Una oruga es un árbol con la propiedad de que si se quitan todas las hojas lo que queda es un camino. ¿Podría ayudarme a demostrar que hay $2^{n-4}+2^{\lfloor n/2\rfloor-2}$ oruga en $n$ vértices, $n\geq3$ ?
(Debería utilizar el teorema de Polya)
Respuestas
¿Demasiados anuncios?
user8269
Puntos
46
Marko Riedel
Puntos
19255
Las ideas del documento de Harary al que se hace referencia en los comentarios no son no son en absoluto difíciles, así que intentaré hacer un resumen aquí.
Comience por considerar el esqueleto de la oruga, que es un camino / columna vertebral con dos nodos finales especiales unidos en cada extremo por una arista. A los nodos de la trayectoria, excluyendo los nodos finales, que actúan como hojas, se les adjuntarán patas/hojas (cualquier número de ellas). camino, excluyendo los nodos finales, que actúan como hojas, asegurando que la longitud del camino se mantiene cuando se eliminan las hojas.
Ahora supongamos que tenemos $m$ ranuras disponibles en el lomo. Las simetrías aquí son muy simples y la aplicación del Teorema de Enumeración de Polya es bastante sencilla. Las únicas simetrías aparecen cuando la oruga es volteada, mapeando su extremo inferior al superior y viceversa. Por lo tanto, el índice de ciclo $Z(Q_m)$ del grupo de permutación de dos elementos grupo de permutación $Q_m$ actuando en las ranuras de la columna vertebral es $$Z(Q_m) = \frac{1}{2} (a_1^m + a_2^{m/2})$$ cuando $m$ es par y $$Z(Q_m) = \frac{1}{2} (a_1^m + a_1 a_2^{(m-1)/2})$$ cuando $m$ es impar.
La función generadora $Q(z)$ del conjunto de orugas es entonces dado por $$\frac{z}{1-z} + \sum_{m\ge 2} Z(Q_m)\left(\frac{z}{1-z}\right)$$ donde el segundo paréntesis denota la sustitución del índice del ciclo.
Obsérvese que uno de los nodos colocados en una ranura de la columna vertebral se incorpora a la columna, mientras que el resto forma hojas. Esta es la razón por la que el repertorio comienza en $z$ y no en $1.$ El primer término representa la contribución de los gráficos en estrella, que pueden considerarse orugas con una columna vertebral formada por un solo nodo (y, por tanto, un camino).
Recogida de las contribuciones de impar $m$ e incluso $m$ así como el caso especial $m=1$ obtenemos $$Q(z) = \frac{z}{1-z} + \sum_{k\ge 1} Z(Q_{2k})\left(\frac{z}{1-z}\right) + \sum_{k\ge 1} Z(Q_{2k+1})\left(\frac{z}{1-z}\right).$$ La primera suma es $$\frac{1}{2} \sum_{k\ge 1} \left(\left(\frac{z}{1-z}\right)^{2k} + \left(\frac{z^2}{1-z^2}\right)^k\right)$$ y se simplifica a $$\frac{1}{2} \frac{z^2}{1-2z} + \frac{1}{2} \frac{z^2}{1-2z^2}.$$ La segunda suma es $$\frac{1}{2} \sum_{k\ge 1} \left(\left(\frac{z}{1-z}\right)^{2k+1} + \frac{z}{1-z} \left(\frac{z^2}{1-z^2}\right)^k\right)$$ y se simplifica a $$\frac{1}{2} \frac{z^3}{(1-z)(1-2z)} + \frac{1}{2}\frac{z^3}{(1-z)(1-2z^2)}.$$
Sumando las dos contribuciones y la contribución de los gráficos en estrella obtenemos $$Q(z) = \frac{z(1-3z^2)}{(1-2z)(1-2z^2)}.$$ Queda por extraer los coeficientes, lo que puede hacerse, por ejemplo por fracciones parciales, lo que da la fórmula $$2^{n-2} + 2^{\lfloor n/2 \rfloor -1}.$$
Por último, recordemos esos dos nodos extra en los extremos del camino, que hay que tener en cuenta, para que la fórmula anterior se desplace a $$2^{n-4} + 2^{\lfloor n/2 \rfloor -2}$$ que es el resultado del trabajo de Harary.
Se trata de la siguiente secuencia (a partir de $n=3$ ): $$1, 2, 3, 6, 10, 20, 36, 72, 136, 272, 528, 1056, 2080,\ldots$$ que es OEIS A005418 .
