Enumeración de árboles etiquetados con raíces sin fórmula de inversión de Lagrange

Question

Me pregunto cómo enumerar árboles etiquetados enraizados sin la fórmula de inversión de Langrange. Como cada árbol es una colección de otros árboles, la función generadora recursiva se convierte en $$C(x) = x + xC(x) + xC(x)^2 ... = \sum_n x[C(x)]^n/{n!} = xe^{C(x)}$$

Según mis notas, me dicen que podemos utilizar la función $G(x)$ que cuenta el número de bosques en n vértices => $xG(x) = C(x)$ Puedo estar tratando de juguetear con estas funciones, así como la toma de derivados / registro de ambos, pero me parece que no puede aislar $C(x)$ para obtener una ecuación funcional para extraer los coeficientes. Se agradece cualquier ayuda.

Answer 1

Aquí hay otra prueba, creo que debida a Jim Pitman.

Un bosque rooteado es una unión disjunta de árboles enraizados, que consideraremos como un dígrafo con aristas siempre dirigidas hacia las raíces. Dado un bosque rooteado $F$ en $n$ vértices con $k$ nos gustaría añadir un borde sin dejar de tener un bosque. Para ello, elija cualquier vértice $x$ y cualquiera de los $k-1$ raíces $y$ no en el mismo componente que $x$ y añadir el borde $y \rightarrow x$ . Por lo tanto, hay $n(k-1)$ formas de hacerlo, y el bosque resultante tiene ahora $k-1$ componentes. Si partimos del bosque con $n$ vértices aislados, vemos que podemos añadir $n-1$ bordes en

$$n(n-1)\cdot n(n-2) \cdot \ldots \cdot n(1) = (n-1)! \cdot n^{n-1}$$ maneras. En esta expresión se ha contado cada árbol $(n-1)!$ ya que el orden en el que añadimos las aristas no importa, así que dividiendo esto se obtiene la fórmula deseada.

Answer 2

Normalmente, se utiliza la fórmula de inversión de Lagrange junto con la ecuación funcional $C(x)=x e^{C(x)}$ para extraer los coeficientes de $C(x)$ . Pero si no quieres hacerlo, aquí tienes un argumento combinatorio para contar árboles enraizados etiquetados, de Joyal (1981), p. 16:

Llama a vertebrado un árbol etiquetado sin raíz con dos puntos distinguidos (posiblemente coincidentes), uno rojo y otro negro. Siguiendo un camino desde el punto rojo hasta el punto negro, eliminando todas las aristas a lo largo del camino, de modo que el árbol se convierta en un bosque; y luego enraizando cada componente conectado de este bosque en su único vértice que se encontraba en el camino previamente formado por las aristas eliminadas, se puede convertir el vertebrado en una secuencia no vacía de árboles etiquetados enraizados. Se trata de una correspondencia biyectiva, por lo que $V_n$ el número de vertebrados en $n$ vértices que están etiquetados $\{1,\ldots,n\}$ es el mismo que el número de secuencias no vacías de árboles enraizados disjuntos en vértices etiquetados $\{1,\ldots,n\}$ .

Dejemos que $n\ge 1$ . El número de formas de ordenar las raíces de $k$ árboles enraizados en una secuencia es $k!$ que es el mismo que el número de formas de ordenar las raíces de $k$ árboles enraizados en una permutación. Así que, $V_n$ es también el número de conjuntos de árboles enraizados en vértices etiquetados $\{1,\ldots,n\}$ junto con una permutación que actúa sobre sus raíces. Pero cada auto-mapa en $\{1,\ldots,n\}$ da una estructura de este tipo (compuesta por árboles de elementos que se unen bajo la acción del automapa y acaban cayendo en ciclos), y a la inversa. Se trata de una correspondencia biyectiva, por lo que $V_n$ es igual al número de auto-mapas en $\{1,\ldots,n\}$ que es $n^n$ .

Cada árbol rooteado en vértices etiquetados $\{1,\ldots,n\}$ da $n$ diferentes vertebrados, coloreando la raíz de negro y cualquiera de $\{1,\ldots,n\}$ rojo. Este es un $n$ -a- $1$ correspondencia, por lo que, si $n\ge 1$ el número de árboles enraizados en $n$ vértices es $n^n/n=n^{n-1}$ .

Joyal también utiliza un razonamiento similar para dar una prueba combinatoria de la fórmula de inversión de Lagrange (pp. 21-24.)

Answer 3

Pitman dio una solución maravillosa.

Hablando del "punto de vista de Joyal" se podría renunciar a esos vertebrados y hablar sólo de funciones y árboles etiquetados . Y en caso de que no hayamos arraigada árboles habrá $n^2$ para cada árbol. En caso contrario, si el problema se refiere a árboles enraizados etiquetados Entonces, tendremos $n$ funciones asociadas a cada uno de esos árboles.

(Así que hay $n^{n-2}$ árboles etiquetados y $n^{n-1}$ árboles enraizados etiquetados )

Hablar sobre el conjunto base $[n]={1,2,...,n}$

No es tan obvio cómo se construye la(s) función(es) partiendo de un árbol etiquetado (rooteado o no). Pero es similar. Por ejemplo, en el caso de árboles etiquetados "sin raíz" tendremos "n X n" = $n^2$ caminos únicos, de cada vértice a cada vértice (incluyendo de un vértice a sí mismo). Un camino de este tipo, con los vértices M = { $v_1, ..., v_k$ } así $v_1$ -> $v_2$ ->...-> $v_k$ construirá parcialmente una función $f(v_i)=v_{i+1}$ , donde $v_{k+1}$ es $v_1$ . Para los "subárboles" (teniendo la RAÍZ en los vértices de los caminos es sencillo).

A la inversa, teniendo una función, hay que construir un árbol ... Hay un único conjunto (no vacío) $M$ con elementos máximos como $f$ es biyectiva en $M$ ... Si escribimos los elementos de $M$ cada vez más $M = \{i_1, i_2,...,i_2\}$ entonces $f(i_1)$ -> $f(i_2)$ -> ... -> $f(i_k)$ será el camino .. para el resto es mucho más simple ... (y tendremos finalmente $n^2$ funciones que dan el mismo árbol). Las operaciones son inversas entre sí...

En el caso de árboles etiquetados enraizados tendremos $n$ caminos únicos que unen la raíz con todos los demás vértices (incluida la propia raíz). El resto es igual.

De todos modos, aquí sólo están los principales PASOS. Una demostración rigurosa es mucho más larga que esto, porque hay que justificar todos, mayores o menores "trucos" o declaraciones.

---

Lo interesante en mi caso (lo que busco) es la posibilidad de seguir pasos similares (al "estilo Joyal", utilizando funciones) para demostrar el teorema de la Luna, es decir enumerar árboles etiquetados con grados (fijos) determinados Así que $d(x_i)= d_i$ para $i \in [n]$ Por supuesto, con $\sum d_i = 2(n-1)$ ...

... y encontrar el conocido coeficiente multinomial $\binom{n-2}{d_1 -1 \; d_2 -1 \; ... \; d_n -1}$