Generating function for the number of graphs with $k$ connected components

Question

There are $$b_n = \frac{(n-1)!}{2}$$ ways to form a cycle on $n$ labelled vertices, for $n\geq 3$. The exponential generating function for this sequence is $$ 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},$$ and if we want the number of graphs on $n$ vertices, the components of which are cycles, the EGF is $$ 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}.$$ (This is example 5.2.8 in Stanley's Enumerative Combinatorics, Vol II)

I'd like to do a similar thing with the number of connected components in a graph.

Fix $n$ and $m$, and consider the graphs on $n$ labelled vertices, with $m$ edges. (We may assume $m\ll n$.) Suppose we know there are $C_{j,l}$ ways to get a connected graph on $j$ vertices and $l$ edges. So, in particular, $C_{j,l}=0$ in case $l<j-1$, or $l>\binom{j}{2}$.

Question: Is it feasible to get an EGF for the sequence $a_k$ of the number of graphs with $k$ connected components ?

Clarification: Let us use the term $(n,m)$-graph, for a graph with $n$ vertices and $m$ edges. We fix $n$ and $m$, and may assume that $m\ll n$. Now, there are $\binom{\binom{n}{2}}{m}$ such $(n,m)$-graphs. Let $a_k$ be the number of $(n,m)$-graphs with $k$ connected components. Clearly, $\sum_{k=1}^n a_k = \binom{\binom{n}{2}}{m}$. I'm interested in the EGF $$ \sum_{k=1}^n \frac{a_k}{k!} x^k.$$

Answer 1

It's feasible to reduce the problem to finding an exponential generating function for the number of connected graphs.

Let $C(j,l,k)$ be the number of graphs on $j$ labeled vertices and $l$ edges with $k$ components. Use the convention that an empty graph has zero components, so $C(0,0,0)=1$ and $C(0,l,k)=0$ for all other $l,k$.

Consider the component containing vertex $1$ in a graph of $n$ vertices, $m$ edges, and $k$ components. If that component has $j$ vertices and $l$ edges, there are $n-j$ vertices and $m-l$ edges left for the remaining $k-1$ components, so \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*} Our choice to put $1$ in the first component means $j\ge 1$ - but since $C(0,l,1)=0$, we can add $j=0$ back in and just sum over all $j$. Back to the issue at hand - yeah, that looks like an exponential-type convolution. Define $B(n,m,k)=\frac1{n!}C(n,m,k)$, and it becomes $$B(n,m,k)=\sum_j\sum_l B(j,l,1)\cdot B(n-j,m-l,k-1)$$ Now define $f_k(x,y)=\sum_n\sum_mB(n,m,k)x^ny^m$. Our relation for the $B$ becomes $$f_k(x,y)=f_1(x,y)\cdot f_{k-1}(x,y)$$ so $f_k(x,y)=\left(f_1(x,y)\right)^k$. Whatever the exponential generating function for connected graphs is, we raise it to the $k$th power to get the exponential generating function for $k$-component graphs.

OK, one more thing. Since every graph has some number of connected components, we can sum over $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}$$ where $f$ is the EGF for the number of connected graphs and the right hand side is the EGF for the number of total graphs. I doubt the latter has an elementary closed form, so that's as far as it goes. We could solve for $f$, writing the other side as a series of powers of that generating function (minus its constant term $1$), but that's messier without any clear benefit.

Answer 2

OP is asking for credible and/or official sources. We cite the Labeled Counting Lemma stated in Graphical Enumeration by F. Harary and E.M. Palmer. This lemma is important since it clarifies the usage of exponential generating functions and the authors just use connected, labeled graphs with $n$ components as demonstration of this lemma.

A theorem in section 1.2 Connected graphs states: The number $C_k$ of connected, labeled graphs with $k$ nodes is \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*}

Let $C(x)$ denote the exponential generating function for the connected, labeled graphs. We find the sequence $(C_k)_{k\geq 0}$ in OEIS as A001187 with generating function \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*}

We start with a motivation for exponential generating functions followed by the labeled counting lemma.

Harary, Palmer: section 1.2

• It is important to have at hand the concept of the exponential generating function and some of its associated properties. We shall therefore introduce these functions now ...

• For each $k=1,2,3,\ldots$, let $a_k$ be the number of ways of labeling all graphs of order $k$ which have some property $P(a)$. Then the formal power series \begin{align*} a(x)=\sum_{k=1}^\infty a_kx^k/k! \end{align*} is called the exponential generating function for the class of graphs at hand. Suppose also that \begin{align*} b(x)=\sum_{k=1}^\infty b_kx^k/k! \end{align*} is another exponential generating function for a class of graphs with property $P(b)$.

• The next lemma provides a useful interpretation of the coefficients of the product $a(x)b(x)$ of these two generating functions.

Labeled Counting Lemma: The coefficient of $x^k/k!$ in $a(x)b(x)$ is the number of ordered pairs $(G_1,G_2)$ of two disjoint graphs, where $G_1$ has property $P(a)$, $G_2$ has property $P(b)$, $k$ is the number of points in $G_1\cup G_2$ and the labels $1$ through $k$ have been distributed over $G_1\cup G_2$.

• To illustrate, let $C(x)$ be the exponential generating functions for labeled, connected graphs,

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

• Then $C(x)C(x)$ is the generating function for ordered pairs of labeled, connected graphs. On dividing this series by $2$, we have the generating function for labeled graphs which have exactly two components. Similarly $C^n(x)/n!$ has as the coefficient of $x^k/k!$, the number of labeled graphs of order $k$ with exactly $n$ components. If we let $G(x)$ be the exponential generating function for labeled graphs, we then have

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

The last paragraph together with (2) reveals the connection between labeled, connected graphs and labeled graphs consisting of $n$ components. The authors close this section by presenting the functional equation connecting $G(x)$ with $C(x)$.

Thus we have the following exponential relationship for $G(x)$ and $C(x)$ found by R.J. Riddel [Contributions to the theory of condensation, Dissertation, 1951].

• Theorem: The exponential generating function $G(x)$ and $C(x)$ for labeled graphs and labeled connected graphs come to terms in the following relation

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

Answer 3

We compute a recurrence for the number of labeled graphs with $k$ components. With $G(z)$ the EGF of labeled graphs we have

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

Here we have included the empty graph on zero nodes. Now the class of graphs $\mathcal{G}$ is in a set-of relationship with the class $\mathcal{C}$ of connected components, namely

$$\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}).}$$

The class of graphs $\mathcal{C}_k$ with $k$ connected components is then given by

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

Translating to generating functions we thus have

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

and

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

Differentiating (here $k\ge 1$) we have

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

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

and extracting coefficients we have

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

which is

$$\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)!}.$$

or

$$\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}.$$

This yields the recurrence

$$\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}.}$$

The base case is that when $k=0$ and $n=0$ we get the empty graph, when $k=0$ or $n=0$ but not both we have zero. This yields for one component the sequence

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

which points to OEIS A001187 where the data are confirmed. Listing the $C_{n,k}$ in order with increasing $k$ for fixed $n$ and increasing $n$ (triangular array) we find

$$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 $$

which points to OEIS A143543, where we get confirmation once more. The reader who wants to experiment with these exponential generating functions is invited to consult the following Maple code.

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);

As a sanity check when we compute $\sum_{k=1}^n C_{n,k}$ using the values from the recurrence we really do obtain $2^{n\choose 2}.$