Una identidad en el número de árboles

Question

Sea $T_n$ el número de árboles etiquetados en $n$ vértices, entonces

$$ T_n=\sum_kk\binom{n-2}{k-1}T_kT_{n-k} \tag{1}$$

Usando esta pregunta, pude probar que

$$ T_n= \frac{n}{2} \sum\binom{n-2}{k-1}T_kT_{n-k} .$$

Pero no sé cómo probar $(1)$. ¿Alguien me puede ayudar por favor?

Answer 1

Me encontré accidentalmente con esta publicación. El autor original iba por el camino correcto. Demostró que $$T_n=\frac{n}{2}\sum_k\binom{n-2}{k-1}T_kT_{n-k}.$$ Esto es equivalente a decir que $$\begin{eqnarray}2T_n&=&\sum_k(k+(n-k))\binom{n-2}{k-1}T_kT_{n-k}\\ &=&\sum_k\left(k\binom{n-2}{k-1}T_kT_{n-k}+(n-k)\binom{n-2}{n-k-1}T_{n-k}{T_k}\right)\\&=&\sum_kk\binom{n-2}{k-1}T_kT_{n-k}+\sum_jk\binom{n-2}{j-1}T_jT_{n-j}\\ &=&2\sum_kk\binom{n-2}{k-1}T_nT_{n-k}.\end{eqnarray}$$ De donde se sigue el resultado.

Answer 2

La ecuación bajo consideración puede demostrarse utilizando la especie de árboles etiquetados y enraizados y su ecuación funcional. (Nota: usaremos la letra $T$ para referirnos a árboles enraizados y etiquetados y su función generadora, y $Q$ para los no enraizados para adherirnos a la convención establecida.)

Ahora la especie $\mathcal{T}$ de árboles etiquetados y enraizados está dada por $$\mathcal{T} = \mathcal{Z} \times \mathfrak{P}(\mathcal{T}).$$ Esto nos da inmediatamente la clásica ecuación funcional $$T(z) = z e^{T(z)}$$ donde $$T(z) = \sum_{n\ge 1} T_n \frac{z^n}{n!}.$$

Diferenciamos para obtener una recurrencia, obteniendo $$T'(z) = e^{T(z)} + z e^{T(z)} T'(z) = \frac{T(z)}{z} + T(z) T'(z).$$ Ahora observamos que $$T'(z) = \sum_{n\ge 0} T_{n+1} \frac{z^n}{n!} \quad\text{y}\quad \frac{T(z)}{z} = \sum_{n\ge 0} \frac{T_{n+1}}{n+1} \frac{z^n}{n!}.$$

Comparando coeficientes en la ecuación funcional diferenciada y usando la convolución de funciones generadoras exponenciales encontramos que $$T_{n+1} = \frac{T_{n+1}}{n+1} + \sum_{k=0}^{n-1} {n\choose k} T_{k+1} T_{n-k}.$$

Ahora cambiamos a árboles no enraizados notando que para el conteo $Q_n$ de árboles etiquetados y no enraizados tenemos $$n \times Q_n = T_n$$ para obtener que

$$(n+1) Q_{n+1} = Q_{n+1} + \sum_{k=0}^{n-1} {n\choose k}\times (k+1) Q_{k+1}\times (n-k) Q_{n-k}.$$ Esto nos da $$Q_{n+1} = \frac{1}{n} \sum_{k=1}^n {n\choose k-1} \times k Q_k \times (n+1-k) Q_{n+1-k} \\= \sum_{k=1}^n \frac{(n-1)!}{(k-1)!(n-k)!} \times k Q_k \times Q_{n+1-k} \\ = \sum_{k=1}^n {n-1\choose k-1} \times k Q_k \times Q_{n+1-k}.$$ Esto es lo que estábamos tratando de demostrar (reemplazando $n+1$ por $n$), QED.