Sea $V=\{1,2,...,n\}$ un conjunto de vértices. ¿Cuántos árboles dirigidos hay sobre $V$ de modo que hay exactamente 2 vértices con grado de salida 0?

Question

Sea V=$\{1,2,...,n\}$ un conjunto de vértices. ¿Cuántos árboles dirigidos hay sobre V tal que hay exactamente 2 vértices con grado de salida de 0?

Mi primer pensamiento fue usar la simetría, y que después de encontrar el número de árboles dirigidos sobre $V$ tal que $d_{out}(1)=d_{out}(2)=0$, y luego multiplicar la respuesta por ${n \choose 2}$.

Usar la matriz laplaciana me parece inútil porque no tengo control sobre otros vértices que tendrán grado de salida de $0$.

Sé que sobre un número finito de vértices, es suficiente asegurarse de que hay un $r\in V$ tal que $d_{in}(r)=0$, y que para todo $u\neq r$, $d_{in}(u)=1$, además de que el gráfico no debe tener ciclos en él.

Ahora, intenté usar la simetría de nuevo. 1 y 2 nunca serán raíces, y por simetría si elijo un vértice al azar para que sea raíz, necesitaré multiplicar el resultado por $n-2$ para obtener todas las posibilidades.

Sin embargo, esto también es bastante complicado, lo mejor que descubrí es que este número es igual a palabras sobre $V$, con una longitud de $n-1$ con estas condiciones:

1. 1 y 2 no aparecen en la palabra.

2. Todos los demás vértices aparecen al menos una vez.

3. Todos los vértices excepto la raíz (y 1 y 2) tienen un único lugar en la palabra donde no pueden aparecer.

4. La raíz debe aparecer al menos una vez después de las dos primeras letras.

Ahora estoy bastante atascado, ¿hay una forma más simple de resolver este problema que me haya perdido?

Answer 1

Aquí hay una forma más fácil de llegar a la respuesta de Marko Riedel.

Dado que estamos tratando con grafos dirigidos etiquetados, necesitamos elegir una raíz. Hay $n$ formas de hacer esto.

Ahora debemos elegir dos nodos de los restantes $n-1$ nodos que servirán como nuestras hojas. Hay $$n-1 \choose 2$$ formas de hacer esto.

Finalmente debemos averiguar qué hacer con el resto de los nodos. Sea P el camino de la raíz a una de las hojas y Q el camino de la raíz a la otra hoja. Dado que solo hay dos hojas, cada uno de los nodos restantes está contenido en ambos P y Q, solo en P, o solo en Q.

Así que debemos contar cuántas formas hay de colocar $n-3$ nodos en $3$ conjuntos teniendo en cuenta el orden. Nota que este es un problema clásico de estrellas y barras con $n-3$ estrellas etiquetadas y $2$ barras. El número de formas de hacer esto es $$\frac{(n-3+2)!}{2!} = \frac{(n-1)!}{2}$$

Combinando estas tres partes nos da: $$n \cdot {n -1 \choose 2} \cdot \frac{(n-1)!}{2} = \frac{n!(n-1)(n-2)}{4}$$

Answer 2

La clase combinatoria de árboles etiquetados enraizados con hojas marcadas es

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \mathcal{T} = \mathcal{U} \times \mathcal{Z} + \mathcal{Z} \times \textsc{SET}_{\ge 1}(\mathcal{T})$$

Lo cual nos da la ecuación funcional (EGF)

$$T(z) = uz + z \times (\exp T(z) - 1)$$

así que

$$z = \frac{T(z)}{\exp T(z)-1+u}$$

Luego tenemos (esto es una OGF en $u$)

$$T_n = (n-1)! [z^{n-1}] T'(z)$$

y a partir de la Fórmula de Coeficiente de Cauchy

$$(n-1)! [z^{n-1}] T'(z) = \frac{(n-1)!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^n} T'(z) \; dz.$$

Ahora pon $T(z) = w$ para que $T'(z) \; dz = dw$

y obtenemos

$$\frac{(n-1)!}{2\pi i} \int_{|w|=\gamma} \frac{(\exp(w)-1+u)^n}{w^n} \; dw.$$

Extrayendo el conteo de $k$ hojas donde $1\le k\le n-1$ encontramos

$${n\choose k} \frac{(n-1)!}{2\pi i} \int_{|w|=\gamma} \frac{(\exp(w)-1)^{n-k}}{w^n} \; dw \\ = {n\choose k} \frac{(n-1)!}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^n} \sum_{q=0}^{n-k} {n-k\choose q} (-1)^{n-k-q} \exp(qw) \; dw \\ = {n\choose k} (n-1)! \sum_{q=0}^{n-k} {n-k\choose q} (-1)^{n-k-q} \frac{q^{n-1}}{(n-1)!} \; dw.$$

Por lo tanto, para la respuesta tenemos

$$\bbox[5px,border:2px solid #00A000]{ {n\choose k} \sum_{q=0}^{n-k} {n-k\choose q} (-1)^{n-k-q} q^{n-1}.}$$

Esto nos lleva a OEIS A055302 donde estos datos son confirmados. Observa que esto se simplifica por inspección a

$$\frac{n!}{k!} \frac{1}{(n-k)!} \sum_{q=0}^{n-k} {n-k\choose q} (-1)^{n-k-q} q^{n-1} = \frac{n!}{k!} {n-1\brace n-k}.$$

Como una revisión de cordura deberíamos haber obtenido todos ellos. La suma puede incluir $k=0$ y $k=n$ porque los números de Stirling correspondientes son cero:

$$\sum_{k=0}^{n} \frac{n!}{k!} {n-1\brace n-k} = \sum_{k=0}^{n} \frac{n!}{k!} (n-1)! [z^{n-1}] \frac{(\exp(z)-1)^{n-k}}{(n-k)!} \\ = (n-1)! [z^{n-1}] \sum_{k=0}^{n} {n\choose k} (\exp(z)-1)^{n-k} \\ = (n-1)! [z^{n-1}] \exp(nz) = (n-1)! \frac{n^{n-1}}{(n-1)!} = n^{n-1}$$

y la verificación es exitosa. Obtenemos para el caso de dos hojas el resultado

$$\frac{1}{2} n! {n-1\brace n-2} = \frac{1}{2} n! {n-1\choose 2} $$

o

$$\bbox[5px,border:2px solid #00A000]{ \frac{1}{4} n! \times (n-1) \times (n-2).}$$

Esto producirá comenzando en tres:

$$3, 36, 360, 3600, 37800, 423360, 5080320, 65318400, \ldots$$

lo cual lleva a OEIS A055303.

Answer 3

Los vértices con grado de salida = 0 son hojas.

Por lo tanto, tienes exactamente dos hojas en un árbol dirigido. Recorre las aristas de regreso desde esas hojas hasta la raíz (para ver cómo se ve).

Por lo tanto, ordenas tus vértices en una cadena, luego decides quién es la raíz - y obtienes un árbol con dos hojas. Y las hojas no pueden ser raíces.

Al final, divide entre 2, para contar la simetría.

Tipo de $\frac{(n-2)\cdot n!}{2}$ árboles diferentes.