Número de árboles etiquetados con exactamente 3 hojas

Question

He visto algunas preguntas relevantes aquí acerca de que la materia [1], [2] pero estoy consiguiendo un resultado diferente y no entiendo si estoy equivocado. Así que la pregunta es:

Encontrar el número de marcado de árboles en $n\geq 4$ vértices que tienen exactamente $3$ hojas.

Este problema puede ser traducido de la siguiente manera: Desde el código de Prüfer queremos contar el número de codewords en el que exactamente $n-3$ diferentes aparecen los números. Sabemos que un código de Prüfer para $n$ vértices tendrá una longitud de $n-2$. Así que tenemos que poner $n$ artículos en $n-3$ posiciones sin repeticiones y esto se puede hacer en $\frac{n!}{(n-3)!}$ veces sus permutaciones ($(n-3)!$) y, a continuación, tenemos 1 posición para elegir a $n-3$ números (porque tenemos $3$ hojas) y, por tanto, $\binom{n-3}{1}$ formas para ocupar esa posición. Así que en total tenemos $\frac{n!(n-3)!(n-3)!}{(n-3)!(n-4)!}=n!(n-3)$ árboles con exactamente tres hojas.

Me estoy perdiendo de algo en mi enumeración?

Answer 1

Usted tiene el derecho Prufer códigos, pero ha cometido algunos errores en el conteo. Es fácil comprobar que su fórmula no funciona: para $n=4$ hay $4$ etiquetado de los árboles con esta propiedad, debido a que el árbol debe ser una estrella y la única opción que tiene es la etiqueta que va en el centro.

En primer lugar, para elegir a $n-3$ $n$ elementos en orden es $\binom n3\times (n-3)!=\frac{n!}{6}$.

En segundo lugar, cuando se selecciona un elemento para duplicar, usted no sólo tiene que elegir el elemento que se duplica ($n-3$ opciones), pero también donde poner el duplicado ($n-2$ lugares posibles). Sin embargo, esta realidad se contabiliza el código dos veces, porque distingue a la "original" y "duplicado" de la versión de la etiqueta que aparece dos veces, lo que significa que debe dividir por $2$.

Así que en general hay $\frac{n!}{6}\times\frac{(n-3)(n-2)}{2}=\frac{n!(n-2)(n-3)}{12}$ a este tipo de árboles.