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.

While trying to derive some formula, I encountered the following problem. Consider the set $C_n$ of all connected graphs on $n$ vertices. What is $$ \sum_{G \in C_n} (-1)^{|G|} ? $$ In other words, if we give a graph with an even number of edges a weight of $+1$, and a graph with an odd number of edges a weight of $-1$, what is the total weight of all connected graphs?

Here is an example: when $n=3$, any two edges form a connected graph, and the complete graph is also connected, so the value of the sum is $3 - 1 = 2$.

Surprisingly, the answer is $$ \sum_{G \in C_n} (-1)^{|G|} = (-1)^{n-1} (n-1)!. $$ This can be proved using the "exponential formula" (see e.g. the freely-available generatingfunctionology). The exponential generating function of all graphs, counted according to their parity, is $1+x$ (since for $n \geq 2$, the even and odd graphs cancel). Hence the exponential generating function for all connected graphs (counted according to their parity) is $$ \log (1+x) = \sum_{n \geq 1} (-1)^{n+1}\frac{x^n}{n} = \sum_{n \geq 1} (-1)^{n+1}(n-1)!\frac{x^n}{n!}. $$

My question is:

Is there an enumerative proof of the formula $$ \sum_{G \in C_n} (-1)^{|G|} = (-1)^{n-1} (n-1)! \quad ? $$

share|improve this question
    
This is a really interesting question. Do you know of any other proofs besides the one that uses the exponential formula? –  Mike Spivey Sep 30 '11 at 3:16
    
Proof by scientific induction. That's how I found the formula in the first place. –  Yuval Filmus Sep 30 '11 at 7:26

3 Answers 3

up vote 6 down vote accepted

Here’s a proof by induction.

Let $w(n) = \sum\limits_{G\in C_n}(-1)^{e(G)}$, where $e(G)$ is the number of edges in $G$. I will assume that the vertex set of $G\in C_n$ is $[n] = [1,n]\cap\mathbb{Z}^+$. Suppose that $w(k) = (-1)^{k-1}(k-1)!$ for $1\le k \le n$.

Let $H$ be a labeled partition of $[n]$. Suppose that $H$ has components (parts) $H_1,\dots,H_k$. Denote $v_i = |H_i|$. Let $P(H)$ be the set of permutations whose cycles are exactly $H_1,\dots,H_k$ (in any internal order). Clearly $$\vert P(H)\vert = \prod_{i=1}^k(v_i-1)!,$$ and if $G_n$ is the set of all labeled partitions of $[n]$, $$\sum_{H\in G_n}\vert P(H)\vert = n!.$$

Let $C_{n+1}(H)$ be the set of $G\in C_{n+1}$ that decompose into connected components $H$ after deleting vertex $n+1$. Consider a component $H_i$ of $H$. If $G\in C_{n+1}(H)$, vertex $n+1$ must be adjacent in $G$ to at least one vertex of $H_i$. For $j=1,\dots,v_i$ there are $\dbinom{v_i}{j}$ ways to attach vertex $n+1$ to $j$ vertices of $H_i$. It follows that $$\begin{align*} \sum_{G\in C_{n+1}(H)}(-1)^{e(G)} &= \prod_{i=1}^k\sum_{j=1}^{v_i}\binom{v_i}{j}(-1)^jw(v_i)\\ &= \prod_{i=1}^k(-1)^{v_i-1}(v_i-1)!\sum_{j=1}^{v_i}\binom{v_i}{j}(-1)^j\\ &= \prod_{i=1}^k(-1)^{v_i-1}(v_i-1)!(-1)\\ &= \prod_{i=1}^k(-1)^{v_i}(v_i-1)!\\ &= (-1)^n\prod_{i=1}^k(v_i-1)!\\ &= (-1)^n\vert P(H)\vert \end{align*}$$

and hence that

$$\begin{align*} w(n+1) &= \sum_{H\in G_n}\quad\sum_{G\in C_{n+1}(H)}(-1)^{e(G)}\\ &= \sum_{H\in G_n}(-1)^n \vert P(H)\vert\\ &= (-1)^n\sum_{H\in G_n}\vert P(H)\vert\\ &= (-1)^n n!. \end{align*}$$

share|improve this answer
    
Sorry for the extensive rewrite. There was some confusion between labeled partitions and graphs. Nice proof! –  Yuval Filmus Sep 30 '11 at 13:10
    
A bijective interpretation appears in my own answer below. –  Yuval Filmus Oct 1 '11 at 23:02

Let me sketch a standard combinatorial proof. Denote by $f_n(t)$ the inversion polynomial, defined as the summation over all spanning trees $\tau \subset K_n$ of $t^{inv(\tau)}$. It is well known that $f_n(t)=T_{K_n}(1,t)$ the Tutte polynomial of a complete graph. This can be proved using recurrence relations (many possibilities) or bijectively (see this paper by Gessel and Wang). Therefore, $f_n(1+t)=T_{K_n}(1,1+t) = \sum_G t^{|G|}$ by definition of the Tutte polynomial, and $f_n(0)=\sum_G (-1)^{|G|}$ is the desired summation in the problem. By definition of tree inversions, the only trees with no inversions are increasing trees. There are exactly $(n-1)!$ of them. By induction: new leaf $n$ has $n-1$ places it can be attached to. For the definition of the inversion polynomial, connections to Tutte polynomial, and recurrence relations, see here and there.

P.S. Just noticed - increasing trees are called hierarchical trees in the previous answer.

share|improve this answer

Here's a different take on Brian's proof.

Let $H_n$ be the set of all rooted trees on $[n]$ such that the root of each subtree is the largest vertex in the tree. We call such trees hierarchical.

We construct a sign-changing involution $\sigma$ on $G_n \setminus H_n$, where $G_n$ is the set of all connected graphs on $n$ vertices. Take a graph $G \in G_n$. Removing vertex $n$ splits the graph into connected components $C_1,\ldots,C_m$.

Suppose first that there is some component $C_i$ such that $n$ is not connected only to $\max C_i$; let $C_i$ be the first such component. The involution $\sigma$ is defined by complementing the edge $(n,\max C_i)$.

Suppose now that for all components it is true that $n$ is connected only to $\max C_i$. Let $C_i$ be the first component which is not hierarchical. The involution $\sigma$ is defined by applying $\sigma$ recursively on $C_i$.

The existence of $\sigma$ shows that the sum in question is equal to $(-1)^{n-1}$ times the number of hierarchical trees on $n$ vertices (here $n-1$ is the number of edges in such a tree). We claim that this number is $(n-1)!$.

Proof 1 (Y.F.): We present a bijection between $H_n$ and the set of all permutations in $S_n$ starting with $n$.

The coding $c$ of trees is defined as follows. The code of a hierarchical tree $T \in H_n$ with subtrees $T_1,\ldots,T_m$ is $$c(T) = nc(T_1)\cdots c(T_m).$$ In other words, $c$ consists of the vertices in prefix order.

To decode a permutation, use the following algorithm. The permutation must start with $n$. Suppose the next symbol is $t_1$. The substring commencing at $t_1$ and terminating just before the first symbol $t_2$ larger than $t_1$ codes the first subtree, which is decoded recursively. The rest of the subtrees are decoded analogously.

Comment (Mike Spivey): The proof shows that the number of hierarchical forests with $k$ trees on $n$ vertices is equal to $\left[ n \atop k \right]$, a Stirling number of the first kind.

Proof 2 (Mike Spivey): All hierarchical trees on $n$ vertices can be constructed as follows. Start with the vertex $n$. Connect vertex $n-1$ to one of the existing vertices ($1$ possibility). Connect vertex $n-2$ to one of the existing vertices ($2$ possibilities). And so on. At the end, vertex $1$ can be connected to any of the $n-1$ preceding vertices. So in total, there are $(n-1)!$ hierarchical trees.

share|improve this answer
1  
Here's another proof that the number of hierarchical trees with $n$ vertices is $(n-1)!$. Clearly, the number is the same if we replace "largest" with "smallest" in the definition. Then, we can create a hierarchical tree on $n$ vertices by attaching the new vertex $n$ to any one of the $n-1$ vertices in a hierarchical tree on $n-1$ vertices. Applied recursively, this gives us $|H_n|=(n-1)(n-2)\cdots(1)! = (n-1)!$. –  Mike Spivey Sep 30 '11 at 14:37
1  
Also, if you take a hierarchical tree on $n+1$ vertices, and you remove vertex $n+1$, you obtain a hierarchical forest on $n$ vertices. Your bijection at the end shows that the number of hierarchical forests on $n$ vertices with $k$ trees is the Stirling cycle number $\left[ n \atop k \right]$. –  Mike Spivey Sep 30 '11 at 15:28

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.