Number of spanning subgraphs of $K_n$ with given number of edges and connected components

Question

Given some positive integers $n,e$ and $c$, I would like to know the number of spanning subgraphs of $K_n$ having $e$ edges and $c$ connected components.

Essentially, what I am asking for here is the coefficient of $v^eq^c$ in $Z_{K_n}(q,v)$ (the form of the Tutte polynomial of $K_n$ which is obtained by setting all "edge variables" in the multivariate version to the same variable $v$). I would be happy with any information about the coefficients of Tutte polynomials of complete graphs in general though.

What is known about these numbers? Is finding an arbitrary one as hard as computing the whole Tutte polynomial of the corresponding complete graph? In some sense there seems to be quite a lot known about them, such as the link with Stirling numbers of the first kind (via the chromatic polynomial) and the fact that for a given $n$ they must sum to the total number of subgraphs $2^{n(n-1)/2}$. But the closest I have found in the literature to an actual formula or even approximation is an exponential generating function for the whole family of polynomials, from which it is does not seem to be possible to extract any specific numbers.

What about if we forget about numbers of edges, and just ask how many spanning subgraphs of $K_n$ with a given number of connected components there are?

Answer 1

It seems like, even if you are only interested in that second answer, you're going to running up against the problem of computing the number of connected graphs on $a_i$ vertices. There might be a better way to count them that this, but here's one possible formula:

Let $P_c(n)$ be the set of partitions of $n$ with $c$ parts. For a partition $P=a_1+a_2+\cdots+a_c$, define the following numbers. Let $m_r(P)$ be the number of parts of $P$ of size $r$, i.e. $$m_r(P)=\\#\{a_i : a_i=r\}.$$ Let $\omega(P)=\prod_{r=1}^{n}\bigl(m_r(P)!\bigr)$. Finally, let ${\mathcal C}(a_i)$ be the number of connected graphs on $a_i$ vertices.

One formula for the number of graphs on $n$ vertices with $c$ connected components then is $$\sum_{P\in P_c(n), P=a_1+a_2+\cdots a_c} \binom{n}{a_1,a_2,...,a_c}\frac{1}{\omega(P)}\cdot\prod_{i=1}^c {\mathcal C}(a_i).$$ The multichoose coefficient $\binom{n}{a_1,a_2,...,a_c}$ comes from the number of partitions of the vertices into $c$ groups, with $\omega(P)$ correcting for the overcount factor for multiple groups of vertices of the same size. The product comes from, for a fixed partition of vertices into pieces of size $a_i$, how many connected graphs are possible on each piece.

I don't believe there are explicit formulas for these $C(a_i)$, and I'm not sure that there's a way to generalize this to answer your original question (outside of in a painful fashion summing across ways divvying up the $e$ edges across these $c$ components.)

While this doesn't say that your question is as hard as computing the Tutte polynomial itself, it makes me suspect that there isn't a closed formula. I looked for a bit as well at Stirling numbers of the second kind (which counted the number of set partitions of the vertices into $c$ pieces), but didn't see a nice way to pull those apart to count the number of connected graphs possible given a set partition. That might give you a different formula though with an approach like that.