Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Problem: Find the number of ways to connect a graph having 5 labeled nodes so that each node is reachable from every other node.

I have solved this problem using principle of inclusion and exclusion and I got answer 728. But I want to know how to solve this problem using generating function.

share|improve this question
    
See oeis.org/A001187 especially reference to Wilf (math.upenn.edu/~wilf/DownldGF.html) –  Jean-Claude Arbaut Mar 14 '13 at 14:57

1 Answer 1

We want to count the number of labelled connected (undirected) graphs on $n = 5$ vertices. There is no "nice" explicit generating function for this, but an implicit one exists that can be used to compute the coefficients. (It doesn't really simplify the calculation though.)

Here is a solution, following Example II.15 (p. 138) in Analytic Combinatorics by Flajolet and Sedgewick.

Let $\mathcal{G}$ be the class of all labelled graphs, and $\mathcal{K}$ the class of all connected labelled graphs. We have $$\mathcal{G} = \text{Set}(\mathcal{K})$$ ("a graph is a set of connected graphs"), so, by the machinery developed in the book, the respective (exponential) generating functions satisfy $$G(z) = e^{K(z)}.$$

This is a famous and important identity in combinatorics, known as the exponential formula.

Anyway, note that we know the generating function $G(z) = \sum_{n=0}^{\infty} g_n \frac{z^n}{n!}$ — the number of labelled graphs on $n$ vertices is simply $g_n = 2^{\binom{n}{2}}$, because for each of the $\binom{n}{2}$ pairs of vertices we can independently choose whether to pick that edge or not. So we can find $K(z)$ in terms of $G(z)$: we have $$\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}$$

where the coefficients are OEIS A001187, and can be calculated by computer, or manually (with a lot of effort) using $\log(1+t) = t - \frac{t^2}{2} + \frac{t^3}{3} - \dots$.

There is in fact a complicated expression for them, that you can derive from the log expression above, and which probably matches what you got using inclusion-exclusion:

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

[Aside: As you can see,

  1. generating functions didn't simplify the amount of calculation required for small $n$, though they do reduce the amount of clever thinking needed,

  2. we can work with generating functions even when they (like $G(z)$ above) are divergent everywhere.]

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.