Relaciones recursivas del número de árboles de distribución de un grafo completo con un grado dado para un vértice fijo

Question

Dado un gráfico completo $K_n$ y algún vértice $v\in K_n$ , dejemos que $c_n(k)$ sea el número de árboles de extensión de $K_n$ con $\deg(v) = k$ . Demostrar que

$$c_n(k) = \frac{k(n-1)}{n-1-k}c_n(k+1)$$

Esto se utiliza en particular como una prueba alternativa para la fórmula de Cayley, por lo que estoy tratando de evitar el uso de la fórmula de Cayley y los códigos de Prüfer. He leído sobre la versión de la suma de la fórmula de Cayley:

Forma de suma de la fórmula de Cayley

Lo cual parece relevante, ya que para pasar de esto a la fórmula de Cayley probablemente sumaré todo $k$ que dará algunas expresiones similares, pero no estoy seguro de cómo relacionarlo exactamente.

La única dirección real que tenía hasta ahora es tratar de construir gráficos con $\deg(v)=k-1$ dado un gráfico con $\deg(v)=k$ pero el número de tales gráficos depende del gráfico particular que se nos dé, y aunque es posible contar las variaciones, se obtiene un cálculo directo de $c_n(k)$ más que una fórmula recursiva para $c_n(k-1)$ Así que no estoy muy seguro de cómo proceder.

Answer 1

Partimos de la clase combinatoria de árboles etiquetados enraizados que es

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

que da la ecuación funcional

$$T(z) = z \exp T(z).$$

Supongamos wlog que el nodo $v$ es $n$ . Por lo tanto, buscamos contar conjuntos (bosques) de cardinalidad $k$ de árboles en $n-1$ nodos. Esto tiene la clase

$$\textsc{SET}_{=k}(\mathcal{T})$$

con función generadora

$$S(z) = \frac{1}{k!} T(z)^k.$$

Buscamos

$$(n-1)! [z^{n-1}] S(z) = (n-2)! [z^{n-2}] S'(z) \\ = (n-2)! [z^{n-2}] \frac{1}{(k-1)!} T(z)^{k-1} T'(z).$$

Ahora la fórmula del coeficiente de Cauchy da como resultado

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

Ponemos $T(z) = w$ para que $z = w \exp(-w)$ y $T'(z) \; dz = dw$ y obtenemos

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

o

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

Encontramos que

$$c_n(k) \frac{n-1-k}{k(n-1)} = \frac{(n-2)!}{(k-1)!} \frac{(n-1)^{n-k-1}}{(n-k-1)!} \frac{n-1-k}{k(n-1)} \\ = \frac{(n-2)!}{k!} \frac{(n-1)^{n-k-2}}{(n-k-2)!} = c_n(k+1).$$

Este es el reclamo. Como comprobación de cordura verifiquemos que sí todos ellos:

$$\sum_{k=1}^{n-1} {n-2\choose k-1} (n-1)^{n-k-1} = \sum_{k=0}^{n-2} {n-2\choose k} (n-1)^{n-k-2} \\ = \sum_{k=0}^{n-2} {n-2\choose n-2-k} (n-1)^{k} = \sum_{k=0}^{n-2} {n-2\choose k} (n-1)^{k} = n^{n-2}$$

y la comprobación de la cordura pasa. Esto demuestra la fórmula de Cayley. En debemos observar, sin embargo, que la prueba más compacta extrae el coeficiente directamente de $T(z)$ , sin la suma intermedia.

La OEIS ha OEIS A061356 para $c_n(k)$ lo que confirma los datos anteriores (consultar la segunda interpretación combinatoria de la lista).