¿Cuántos árboles sobre ${1,2,3,...n}$ con condiciones

Question

Estoy atascado en esta pregunta de la teoría de grafos. La pregunta es:

¿Cuántos árboles etiquetados hay sobre $V={0,1,2,...n}$ con los que los vértices 1,2,3 son hojas, y la distancia entre dos cualesquiera de estas hojas es 3 o más.

He intentado utilizar el teorema de Cayley pero no sé cómo aplicarlo en esta pregunta concreta.

Answer 1

Como cualquier otra pregunta sobre el recuento de árboles, se puede responder con Códigos Prüfer .

Cada árbol con conjunto de vértices $\{1,2,\dots,n\}$ corresponde a un único código Prüfer, que es una secuencia de $n-2$ elementos de $\{1,2,\dots,n\}$ . Además, un vértice de grado $k$ en el árbol aparece $k-1$ veces en el código Prüfer.

Así que para contar los árboles que tienen $1$ , $2$ y $3$ como hojas, basta con contar los códigos de Prüfer que no incluyen los elementos $1$ , $2$ y $3$ . Hay $(n-3)^{n-2}$ de estos.

Para hacer frente a la condición de que estas hojas son la distancia $3$ aparte, lo más fácil es utilizar la inclusión-exclusión. Empezando por la cantidad $(n-3)^{n-2}$ ,

• restar el número de árboles que tienen $1$ , $2$ y $3$ como hojas, con $1$ y $2$ sólo la distancia $2$ aparte.
• restar el número de árboles que tienen $1$ , $2$ y $3$ como hojas, con $1$ y $3$ sólo la distancia $2$ aparte.
• restar el número de árboles que tienen $1$ , $2$ y $3$ como hojas, con $2$ y $3$ sólo la distancia $2$ aparte.
• sumar de nuevo, dos veces, el número de árboles que han $1$ , $2$ y $3$ como las hojas, con los tres de ellos sólo la distancia $2$ aparte.

Podemos calcularlos observando que cualquier árbol en el que los vértices $1$ , $2$ y $3$ son hojas, y $1$ y $2$ son la distancia $2$ aparte, puede construirse partiendo de un árbol en el conjunto de vértices $\{1,3,\dots,n\}$ en el que $1$ y $3$ son hojas, y añadiendo el vértice $2$ al único vecino de $1$ . Así que hay $(n-3)^{n-3}$ tales árboles. Los otros dos casos son similares (salvo que en el último caso añadimos dos vértices), por lo que obtenemos una respuesta final de $$ (n-3)^{n-2} - 3(n-3)^{n-3} + 2(n-3)^{n-4}. $$

---

También podemos razonar de forma más directa, aunque esto requiere hacer uso de más detalles del código de Prüfer. A partir del algoritmo para convertir un árbol en un código Prüfer (véase el artículo de Wikipedia para más detalles) está claro que cuando los vértices $1$ , $2$ y $3$ son todas hojas, el primer número del código es el padre del vértice $1$ el segundo número es el padre del vértice $2$ y el tercer número es el padre del vértice $3$ .

Estos tres números deben ser diferentes para garantizar que los tres vértices no estén demasiado juntos. Por lo tanto, el número de formas de elegir un código de Prüfer para dicho árbol es el producto de:

• $n-3$ formas de elegir el primer número de $\{4,5,\dots,n\}$ ;
• $n-4$ formas de elegir el segundo número de $\{4,5,\dots,n\}$ , diferente de la primera;
• $n-5$ formas de elegir el tercer número de $\{4,5,\dots,n\}$ , diferente de la primera y de la segunda;
• $(n-3)^{n-5}$ formas de elegir el resto $n-5$ números de $\{4,5,\dots,n\}$ .

El producto de estos es $(n-3)^{n-4}(n-4)(n-5)$ que es equivalente a la fórmula anterior.