Hallar el número de grafos conexos etiquetados de 5 nodos mediante funciones generadoras

Question

Problema : Encuentre el número de maneras de conectar un gráfico que tiene 5 nodos etiquetados de manera que cada nodo sea alcanzable desde cualquier otro nodo.

He resuelto este problema utilizando el principio de inclusión y exclusión y he obtenido la respuesta 728. Pero quiero saber cómo resolver este problema utilizando la función generadora.

Answer 1

Queremos contar el número de grafos conectados etiquetados (no dirigidos) en $n = 5$ vértices. No hay una función generadora explícita "bonita" para esto, pero existe una implícita que puede utilizarse para calcular los coeficientes. (Sin embargo, no simplifica realmente el cálculo).

He aquí una solución, siguiendo el ejemplo II.15 (p. 138) en Combinatoria analítica por Flajolet y Sedgewick.

Dejemos que $\mathcal{G}$ sea la clase de todos los grafos etiquetados, y $\mathcal{K}$ la clase de todos conectado gráficos etiquetados. Tenemos $$\mathcal{G} = \text{Set}(\mathcal{K})$$ ("un gráfico es un conjunto de gráficos conectados"), por lo que, por la maquinaria desarrollada en el libro, las respectivas funciones generadoras (exponenciales) satisfacen $$G(z) = e^{K(z)}.$$

Esta es una famosa e importante identidad en combinatoria, conocida como la fórmula exponencial .

De todos modos, hay que tener en cuenta que conocemos la función generadora $G(z) = \sum_{n=0}^{\infty} g_n \frac{z^n}{n!}$ - el número de gráficos etiquetados en $n$ vértices es simplemente $g_n = 2^{\binom{n}{2}}$ porque para cada uno de los $\binom{n}{2}$ pares de vértices podemos elegir de forma independiente si elegir esa arista o no. Así que podemos encontrar $K(z)$ en términos de $G(z)$ Tenemos $$\begin{align} K(z) &= \log G(z) \\ &= \log \left(1 + z + 2\frac{z^2}{2!} + 8\frac{z^3}{3!} + 64\frac{z^4}{4!} + 1024\frac{z^5}{5!} + \dots\right) \\ &= z + \frac{z^2}{2!} + 4\frac{z^3}{3!} + 38\frac{z^4}{4!} + 728\frac{z^5}{5!} + \dots \end{align}$$

donde los coeficientes son OEIS A001187 y se puede calcular por ordenador o manualmente (con mucho esfuerzo) utilizando $\log(1+t) = t - \frac{t^2}{2} + \frac{t^3}{3} - \dots$ .

De hecho, hay una expresión complicada para ellos, que puedes derivar de la expresión de registro anterior, y que probablemente coincida con lo que obtuviste usando la inclusión-exclusión:

$$ k_n = 2^{\binom{n}{2}} - \frac12\sum\binom{n}{n_1, n_2}2^{\binom{n_1}2 + \binom{n_2}2} + \frac13\sum\binom{n}{n_1, n_2, n_3}2^{\binom{n_1}2 + \binom{n_2}2 + \binom{n_3}2} - \dots $$

[Aparte: Como puedes ver,

1. funciones generadoras no simplificaban la cantidad de cálculos necesarios para las pequeñas $n$ Aunque reducen la cantidad de pensamiento inteligente que se necesita,

2. podemos trabajar con funciones generadoras incluso cuando (como $G(z)$ arriba) son divergentes en todas partes].