Cuántos gráficos conectados y simples hay en n vértices

Question

Estoy tratando de encontrar una fórmula que me dará el número de conectados, gráficas sencillas sobre n vértices, no tomando en consideración isomorfismo.

Yo, sin embargo, que se puede hacer tomando la diferencia entre el número total de posibles gráficos y desconectado de los gráficos. Tendremos :

$2^{\binom{n}{2}}$ donde $\binom{n}{2}$ va a determinar el número posible de aristas(esto nos dará el número total de posibles gráficos)

Desconectado gráficos consistirá $n-2, n-3 ...$ bordes(desde $n-1$ es un árbol). El número de desconectados gráficos dependerá del número de vértices, así que he pensado que sería igual a $\sum_{i=2}^{n-1}(2^{\binom{n}{2} -i})$.

En total : $2^{\binom{n}{2}}-\sum_{i=2}^{n-1}(2^{\binom{n}{2} -i})$ . Y yo estoy atrapado aquí. Lo que sería una correcta aproximación a este problema?

Answer 1

Vamos a reducir el problema de contar el número de la etiqueta de gráficas sencillas en $n$ vértices a enumerar las particiones de $n$. Nuestra principal estrategia es el uso de Mobius inversión en la partición de celosía.

Deje $G=(V,E)$ un gráfico en $n$ vértices. Para cualquier subgrafo $G'=(V,E')$ donde $E'\subseteq E$, denotamos $C_{G'}$ a ser la partición de los vértices correspondientes a los componentes conectados de $G'$. Ahora nos definen $g: \Pi_n \to \mathbb{Z}$ $f: \Pi_n \to \mathbb{Z}$ como sigue. Deje $g(B)$ el número de simple subdiagramas $G'=(V,E')$ tal que $C_{G'}=B$, y deje $f(B)$ el número de simple subdiagramas $G'=(V,E')$ tal que $C_{G'}\le B$. Entonces $$ f(B)= \sum_{A\le B} g(A) $$

Llamamos a una partición de $n$ tipo $(k_1,k_2,\dots,k_n)$ si la partición contiene $k_i$ bloques de tamaño $i$. Ahora si $B\in \Pi_n$ tipo $(k_1,k_2,\dots,k_n)$, luego $$ f(B)= 2^{\sum_{i=2}^n k\dbinom{i}{2}}$$ Por Mobius Inversión, tenemos $$ g(\widehat{1})=\sum_{A\le B}\mu_{\Pi_n}(A,\widehat{1})f(A)$$ Deje $\sum_{i=1}^n k_i=k$. A continuación,$|A|=k$, e $[A,\widehat{1}]\cong \Pi_k$. Por lo tanto $$\mu_{\Pi_n}(A,\widehat{1})=\mu_{\Pi_k}(\widehat{0},\widehat{1})=(-1)^{k-1}(k-1)!$$ Nota que hay $$ \frac{n!}{\prod_{i=1}^n k_i!i!^{k_i}}$$ particiones de $n$ tipo $(k_1,k_2,\dots,k_n)$. Por tanto, el número de la etiqueta de gráficas sencillas en $n$ vértices es $$ g(\widehat{1})=\sum_{\substack{(k_1,k_2,\dots,k_n) \\ \sum_{i=1}^n ik_i=n}} \left[2^{\sum_{i=2}^n k\dbinom{i}{2}}\right]\left[(-1)^{-1+\sum_{i=1}^n k_i}\right]\left(-1+\sum_{i=1}^n k_i\right)!\left(\frac{n!}{\prod_{i=1}^n k_i!i!^{k_i}}\right) $$