¿Cómo justificar la fórmula de unicyclic gráficos conectados?

Question

He leído esta fórmula en un libro $c(k,k)$, el número de unicyclic gráficos conectados en $k$ vértices, es decir, $n=m=k$.

¿Cómo puede uno demostrar? Parece que está iterando en la longitud del ciclo. ¿Además cómo probar la aproximación?

$$c(k,k)=\sum_{r=3}^n {n\choose r}\frac{(r-1)!}{2}rk^{k-r-1} \sim \frac{\pi}8k^{k-0.5}$$

Answer 1

Este es el número de conectados unicyclic etiquetado de los gráficos. Por lo tanto, si $r$ es la longitud de un ciclo tenemos $\binom{n}{r}$ formas de seleccionar $r$ vértices de ciclo, $\frac{(r - 1)!}2$ formas de construir un ciclo sobre estos vértices.

Todo lo que necesitamos ahora es el número de los bosques en la $n$ vértices con $r$ árboles de raíces con raíces. Puede ser calculada de la misma manera como la fórmula de Cayley fue confirmado con código de Prüfer. Por lo que podemos etiquetar los vértices de modo que $r$ raíces tienen números de $n, n - 1, \ldots, n - r + 1$. A continuación, calculamos el código de Prüfer de bosque, mientras que hay al menos uno de los bordes. (Tenga en cuenta que en el caso de árbol nos detenemos un paso antes, yo. e. calculamos el código, mientras que hay al menos dos bordes). Entonces es fácil ver que cada bosque puede ser única asignada a su código de Prüfer. Cada una de las $n - r - 1$ hojas pueden ser adyacentes a cualquiera de $n$ vértices y el último, $n - r$th hoja es adyacente a una de $r$ raíces. También de la raíz se eliminará de la hoja con un mínimo de etiqueta, debido a que siempre hay al menos otro de la hoja. Así que hay $rn^{n - r - 1}$ deseado bosques. Así $$c(k, k) = \sum_{r = 3}^n \binom{n}{r} \frac{(r - 1)!}2 rn^{n - r - 1} = \sum_{r = 3}^n \binom{n}{r} \frac{(r - 1)!}2 rk^{k - r - 1} = \sum_{r = 3}^k \frac{k!}{2(k - r)!} k^{k - r - 1}.$$

Prueba de asymptotics voy a dar más adelante.