Generando la función para el número de gráficos con $k$ componentes conectados

Question

Hay $$b_n = \frac{(n-1)!}{2}$$ formas de formar un ciclo en $n$ vértices etiquetados, para $n\geq 3$. La función generadora exponencial para esta secuencia es $$ f(x) = \frac{1}{2}\sum_{n\geq 3} (n-1)! \frac{x^n}{n!} =\frac{1}{2}\sum_{n\geq 3} \frac{x^n}{n},$$ y si queremos el número de gráficos en $n$ vértices, cuyos componentes son ciclos, el EGF es $$ g(x) = \exp(f(x)) = \exp \left(\frac{1}{2}\sum_{n\geq 1} \frac{x^n}{n} - \frac{x}{2} - \frac{x^2}{4}\right)$$ $$ =\exp \left( - \frac{x}{2} - \frac{x^2}{4}\right) (1-x)^{-1/2}.$$ (Este es el ejemplo 5.2.8 en Combinatoria Enumerativa de Stanley, Vol II)

Me gustaría hacer algo similar con el número de componentes conectados en un grafo.

Fijar $n$ y $m$, y considerar los gráficos en $n$ vértices etiquetados, con $m$ bordes. (Podemos asumir que $m\ll n$.) Supongamos que sabemos que hay $C_{j,l}$ formas de obtener un grafo conectado en $j$ vértices y $l$ bordes. Entonces, en particular, $C_{j,l}=0$ en el caso de $l, o $l>\binom{j}{2}$.

Pregunta: ¿Es factible obtener un EGF para la secuencia $a_k$ del número de gráficos con $k$ componentes conectados?

Aclaración: Utilicemos el término $(n,m)$-grafo, para un grafo con $n$ vértices y $m$ bordes. Fijamos $n$ y $m$, y podemos asumir que $m\ll n$. Ahora, hay $\binom{\binom{n}{2}}{m}$ tales $(n,m)$-gráficos. Sea $a_k$ la cantidad de $(n,m)$-gráficos con $k$ componentes conectados. Claramente, $\sum_{k=1}^n a_k = \binom{\binom{n}{2}}{m}$. Estoy interesado en el EGF $$ \sum_{k=1}^n \frac{a_k}{k!} x^k.$$

Answer 1

OP está solicitando fuentes creíbles y/o oficiales. Citamos el Lema de Conteo Etiquetado establecido en Enumeración Gráfica por F. Harary y E.M. Palmer. Este lema es importante ya que aclara el uso de las funciones generadoras exponenciales y los autores solo utilizan gráficos conectados y etiquetados con $n$ componentes como demostración de este lema.

Un teorema en la sección 1.2 Gráficos conectados establece: El número $C_k$ de gráficos conectados y etiquetados con $k$ nodos es \begin{align*} \color{blue}{C_k=2^{\binom{k}{2}}-\frac{1}{k}\sum_{j=1}^{k-1}\binom{k}{j}j2^{\binom{k-j}{2}}C_j}\tag{1} \end{align*}

Sea $C(x)$ la función generadora exponencial para los gráficos conectados y etiquetados. Encontramos la secuencia $(C_k)_{k\geq 0}$ en OEIS como A001187 con la función generadora \begin{align*} \sum_{k=0}^\infty C_k\frac{x^k}{k!}&=1+\log\left(\sum_{j=0}^\infty 2^{\binom{j}{2}}\frac{x^j}{j!}\right)\\ &=1+x + \frac{x^2}{2!} + 4\frac{x^3}{3!} + 38\frac{x^4}{4!} + 728\frac{x^5}{5!}\\ &\qquad + 26\,704\frac{x^6}{6!} + 1\,866\,256\frac{x^7}{7!} + \cdots \end{align*}

Comenzamos con una motivación para las funciones generadoras exponenciales seguido por el lema de conteo etiquetado.

Harary, Palmer: sección 1.2

• Es importante tener en cuenta el concepto de la función generadora exponencial y algunas de sus propiedades asociadas. Por lo tanto, presentaremos estas funciones ahora ...

• Para cada $k=1,2,3,\ldots$, sea $a_k$ el número de formas de etiquetar todos los gráficos de orden $k$ que tienen alguna propiedad $P(a)$. Entonces la serie de potencias formal \begin{align*} a(x)=\sum_{k=1}^\infty a_kx^k/k! \end{align*} se llama la función generadora exponencial para la clase de gráficos en cuestión. Supongamos también que \begin{align*} b(x)=\sum_{k=1}^\infty b_kx^k/k! \end{align*} es otra función generadora exponencial para una clase de gráficos con la propiedad $P(b)$.

• El siguiente lema proporciona una interpretación útil de los coeficientes del producto $a(x)b(x)$ de estas dos funciones generadoras.

Lema de Conteo Etiquetado: El coeficiente de $x^k/k!$ en $a(x)b(x)$ es el número de pares ordenados $(G_1,G_2)$ de dos gráficos disjuntos, donde $G_1$ tiene la propiedad $P(a)$, $G_2$ tiene la propiedad $P(b)$, $k$ es el número de puntos en $G_1\cup G_2$ y las etiquetas $1$ a través de $k$ han sido distribuidas sobre $G_1\cup G_2$.

• Para ilustrar, sea $C(x)$ la función generadora exponencial para gráficos etiquetados y conectados,

\begin{align*} C(x)=\sum_{k=1}^\infty C_k x^k/k! \end{align*}

• Entonces $C(x)C(x)$ es la función generadora para pares ordenados de gráficos etiquetados y conectados. Al dividir esta serie por $2$, tenemos la función generadora para gráficos etiquetados que tienen exactamente dos componentes. De manera similar, $C^n(x)/n!$ tiene como coeficiente de $x^k/k!$, el número de gráficos etiquetados de orden $k$ con exactamente $n$ componentes. Si permitimos que $G(x)$ sea la función generadora exponencial para gráficos etiquetados, entonces tenemos

\begin{align*} \color{blue}{G(x)=\sum_{n=1}^\infty C^n(x)/n!}\tag{2} \end{align*}

El último párrafo junto con (2) revela la conexión entre gráficos conectados y etiquetados y gráficos etiquetados que consisten en $n$ componentes. Los autores cierran esta sección presentando la ecuación funcional que conecta $G(x)$ con $C(x)$.

Así que tenemos la siguiente relación exponencial para $G(x)$ y $C(x)$ encontrada por R.J. Riddel [Contribuciones a la teoría de la condensación, Tesis, 1951].

• Teorema: La función generadora exponencial $G(x)$ y $C(x)$ para gráficos etiquetados y gráficos conectados etiquetados llegan a un acuerdo en la siguiente relación

\begin{align*} 1+G(x)=e^{C(x)} \end{align*}

Answer 2

Calculamos una recurrencia para el número de gráficos etiquetados con $k$ componentes. Con $G(z)$ la EGF de los gráficos etiquetados tenemos

$$G(z) = \sum_{n\ge 0} 2^{n\choose 2} \frac{z^n}{n!}.$$

Aquí hemos incluido el gráfico vacío en cero nodos. Ahora la clase de gráficos $\mathcal{G}$ está en una relación de conjunto con la clase $\mathcal{C}$ de componentes conectados, es decir

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \bbox[5px,border:2px solid #00A000]{ \mathcal{G} = \textsc{SET}(\mathcal{C}).}$$

La clase de gráficos $\mathcal{C}_k$ con $k$ componentes conectados es entonces dada por

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

Traducido a funciones generadoras tenemos entonces

$$G(z) = \exp C(z) \quad\text{o}\quad C(z) = \log G(z)$$

y

$$\bbox[5px,border:2px solid #00A000]{ C_k(z) = \frac{\log^k G(z)}{k!}.}$$

Diferenciando (aquí $k\ge 1$) tenemos

$$C_k(z)' = C_{k-1}(z) \frac{G'(z)}{G(z)} \quad\text{o}\quad C_k(z)' G(z) = C_{k-1}(z) G'(z).$$

Escribiendo $$C_k(z) = \sum_{n\ge 0} C_{n,k} \frac{z^n}{n!}$$

y extrayendo coeficientes tenemos

$$[z^{n-1}] C_k(z)' G(z) = [z^{n-1}] C_{k-1}(z) G'(z)$$

lo cual es

$$\sum_{q=0}^{n-1} C_{q+1, k} \frac{1}{q!} 2^{n-1-q\choose 2} \frac{1}{(n-1-q)!} = \sum_{q=0}^{n-1} C_{q, k-1} \frac{1}{q!} 2^{n-q\choose 2} \frac{1}{(n-1-q)!}.$$

o

$$\sum_{q=0}^{n-1} {n-1\choose q} C_{q+1, k} 2^{n-1-q\choose 2} = \sum_{q=0}^{n-1} {n-1\choose q} C_{q, k-1} 2^{n-q\choose 2}.$$

Esto nos da la recurrencia

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

El caso base es cuando $k=0$ y $n=0$ obtenemos el gráfico vacío, cuando $k=0$ o $n=0$ pero no ambos obtenemos cero. Esto nos lleva a la secuencia para un componente

$$1, 1, 4, 38, 728, 26704, 1866256, 251548592, \\ 66296291072, 34496488594816, 35641657548953344, \\ 73354596206766622208, 301272202649664088951808, \ldots $$

lo cual apunta a OEIS A001187 donde los datos son confirmados. Listando los $C_{n,k}$ en orden con $k$ creciente para un $n$ fijo y con $n$ creciente (array triangular) obtenemos

$$1, 1, 1, 4, 3, 1, 38, 19, 6, 1, 728, 230, 55, 10, 1, 26704, \\ 5098, 825, 125, 15, 1, 1866256, 207536, 20818, 2275, 245, \\ 21, 1, 251548592, 15891372, 925036, 64673, 5320, 434, 28, 1, \ldots $$

lo cual apunta a OEIS A143543, donde obtenemos una vez más confirmación. El lector que quiera experimentar con estas funciones generadoras exponenciales está invitado a consultar el siguiente código de Maple.

CGF :=
proc(n, k)
option remember;
local G;

    G := add(2^binomial(q,2)\*z^q/q!, q=0..n);
    n!\*coeftayl(log(G)^k/k!, z=0, n);
end;

C :=
proc(n, k)
option remember;

    if k = 0 and n = 0 then return 1 fi;
    if k = 0 or n = 0 then return 0 fi;

    add(binomial(n-1,q)\*C(q,k-1)\*2^binomial(n-q,2),
        q=0..n-1)
    - add(binomial(n-1,q)\*C(q+1,k)\*2^binomial(n-1-q,2),
          q=0..n-2);
end;

OEIS := mx -> seq(seq(C(n,k), k=1..n), n=1..mx);

Como una verificación de cordura cuando calculamos $\sum_{k=1}^n C_{n,k}$ usando los valores de la recurrencia realmente obtenemos $2^{n\choose 2}.$

Answer 3

Es posible reducir el problema a encontrar una función generadora exponencial para el número de grafos conectados.

Sea $C(j,l,k)$ el número de grafos en $j$ vértices etiquetados y $l$ aristas con $k$ componentes. Use la convención de que un grafo vacío tiene cero componentes, por lo que $C(0,0,0)=1$ y $C(0,l,k)=0$ para todos los otros $l,k$.

Considere el componente que contiene al vértice $1$ en un grafo de $n$ vértices, $m$ aristas y $k$ componentes. Si ese componente tiene $j$ vértices y $l$ aristas, quedan $n-j$ vértices y $m-l$ aristas para las restantes $k-1$ componentes, entonces \begin{align*}C(n,m,k) &= \sum_{1\in S\subset [n]}\sum_l C(|S|,l,1)\cdot C(n-|S|,m-l,k-1)\\ &= \sum_j\sum_l\binom{n}{j}C(j,l,1)\cdot C(n-j,m-l,k-1)\end{align*} Nuestra elección de poner el $1$ en el primer componente significa que $j\ge 1$ - pero como $C(0,l,1)=0$, podemos agregar $j=0$ de vuelta y simplemente sumar sobre todos los $j$. Volviendo al problema - sí, eso parece una convolución tipo exponencial. Definimos $B(n,m,k)=\frac1{n!}C(n,m,k)$, y se convierte en $$B(n,m,k)=\sum_j\sum_l B(j,l,1)\cdot B(n-j,m-l,k-1)$$ Ahora definimos $f_k(x,y)=\sum_n\sum_mB(n,m,k)x^ny^m$. Nuestra relación para el $B$ se convierte en $$f_k(x,y)=f_1(x,y)\cdot f_{k-1}(x,y)$$ entonces $f_k(x,y)=\left(f_1(x,y)\right)^k$. Sea cual sea la función generadora exponencial para grafos conectados, la elevamos a la potencia $k$ para obtener la función generadora exponencial para grafos de $k$ componentes.

OK, una cosa más. Dado que todo grafo tiene cierto número de componentes conectadas, podemos sumar sobre $k$: $$\frac1{1-f(x,y)} = \sum_k f^k(x,y) = \sum_{m,n}\frac1{n!}\binom{\binom{n}{2}}{m}x^ny^m = \sum_n\frac{x^n}{n!}(1+y)^{n(n-1)/2}$$ donde $f$ es la EGF para el número de grafos conectados y el lado derecho es la EGF para el número total de grafos. Dudo que este último tenga una forma cerrada elemental, así que hasta ahí llegamos. Podríamos resolver para $f$, escribiendo el otro lado como una serie de potencias de esa función generadora (menos su término constante $1$), pero eso es más complicado sin ningún beneficio claro.