# Counting chains of inclusions

Let $g(n,k)$ be the number of chains

$$A_k \subset A_{k-1} \subset\dots\subset A_1 \subset A_0$$

of $k$ proper subset inclusions, where $A_k\neq\emptyset$ and $A_0$ is a standard $n$-element set. Then

$$\sum_{k\ge 0} (-1)^k g(n,k) = (-1)^{n-1}.$$

I can prove this by a fairly boring and unilluminating induction. (And also by a category-theoretic argument involving traces of geometric realizations in derivators, which is how I first noticed it.) Does it have a nicer combinatorial proof, by (say) bijections, generating functions, Mobius inversion, etc.?

• This not an answer to the question as you posed it, but I suspect that your "category-theoretic argument involving traces of geometric realizations in derivators" reduces to a (probably) simpler homotopy theoretic proof. Namely, $g(n,k)$ is the number of $(k-1)$-simplices in the barycentric subdivision of the boundary of the standard $(n-1)$-simplex. Hence your sum (up to the $k=0$ summand and up to sign) computes the Euler characteristic of the $(n-2)$-sphere. – Karol Szumiło May 30 '14 at 17:43
• Hall's formula for the Möbius function of a finite bounded ranked poset says that any such poset $P$ satisfies $\mu\left(P\right) = \sum_{k\geq 0} \left(-1\right)^k \left(\text{number of chains } 0 = x_0 < x_1 < \cdots < x_k = 1 \text{ in } P\right)$, where $0$ and $1$ denote the lower bound and the upper bound of $P$. In your case, the poset is the Boolean lattice, but notice that your $g\left(n,k\right)$ counts chains $0 = x_0 < x_1 < \cdots < x_{k+1} = 1$ rather than $0 = x_0 < x_1 < \cdots < x_k = 1$ so you are skipping the $k = 0$ addend of Hall's formula. – darij grinberg May 30 '14 at 17:55
• (The $k = 0$ addend, of course, is only relevant for $n = 0$. It is more important that your sign is different because of the $k$ shift.) The Möbius function of the Boolean lattice is easily computed, as it is multiplicative and the Boolean lattice is a product of $2$-chains. – darij grinberg May 30 '14 at 17:59
• @darijgrinberg, that looks like an answer; why don't you post it as one? – Mike Shulman May 31 '14 at 22:18
• @KarolSzumiło, you're probably right. – Mike Shulman May 31 '14 at 23:35

A chain $$A_k \subset A_{k-1} \subset\dots\subset A_1 \subset A_0$$ can be represented by the ordered partition $(B_1, B_2, \dots, B_{k+1})$ of the set $A_0=\{1, 2, \dots, n\}$ where $B_1=A_k$, $B_2=A_{k-1}-A_k$, $\dots,$ $B_{k+1}=A_0-A_1$.

First, a generating function proof. If we wanted to count such chains (or ordered partitions) without signs, the exponential generating function would be $\sum_{j=0}^\infty (e^x-1)^j = 1/(2-e^x)$ (http://oeis.org/A000670). With signs, the generating function is $$\sum_{j=0}^\infty (-1)^{j+1}(e^x-1)^j= -e^{-x} = \sum_{n=0}^\infty (-1)^{n+1} \frac{x^n}{n!}.$$

For a combinatorial proof using a sign reversing involution that changes the parity of the number of blocks, write the entries of each block in increasing order, with a bar between blocks, so $\{2,4,6\}\{1,3\}\{5\}$ would be written as $2\, 4\, 6 \,|\, 1\, 3 \,|\, 5$. Find the first position, if there is one, where a number is followed by a larger number. If there is a bar there, remove it, and if there is no bar there then put one in. So our example would be mapped to $2 \,|\, 4 \,6 \,|\, 1 \,3 \,|\, 5$ . As another example, $4 \,|\, 3 \,|\, 1 \,2\,|\,$ would map to $4 \,|\, 3\,|\, 1 \,|\, 2$ . The only ordered partitions not paired up are of the form $n \,|\, n-1\,|\, \cdots \,|\,2 \,|\, 1\,$ .

• Thank you! (As a helpful note to other readers, those are exponential generating functions.) – Mike Shulman Jun 1 '14 at 4:15
• I added the word "exponential". – Ira Gessel Jun 1 '14 at 4:47

There is quite direct proof from point of view of topological combinatorics.

Let $\Delta$ be the standard $(n-1)$-simplex with vertex set $A_0$. Considering the barycentric subdivision $\Delta'$ of $\Delta$, the vertices of $\Delta'$ are nonempty subsets of $A_0$ and faces of $\Delta'$ are subsets $\{A_k, \dots, A_1\}$ of vertices of $\Delta'$ such that $$\emptyset \neq A_k \subset A_{k-1} \subset \cdots \subset A_1 \subseteq A_0.$$ (Note that the last inclusion needn't be proper.)

In this correspondence, your chains correspond to $(k-1)$-faces of $\Delta'$ which do not contain the barycentre $A_0$. These are the faces of the barycentric subdivision of the boundary of $\Delta$, which is topologically an $(n-2)$-sphere. There, if you were summing in your sum for $k \geq 1$, the value you obtain is the minus Euler characteristic of the $(n-2)$-sphere, which is $-(1 + (-1)^{n-2})$. Since you sum for $k \geq 0$, you get $(-1)^{n-1}$.

• Well, this answer now only explains the comment of Karol S. (I did not refresh the comments before posting an answer.) – Martin Tancer May 30 '14 at 18:06
• That's okay; there is a distressing tendency on MO to post answers as comments, so I'm glad to have it here as an answer. – Mike Shulman May 31 '14 at 23:37

This can indeed be seen as a consequence of the properties of the Möbius function of a poset. We recall two important properties of this function (see §7.2.1 in Vic Reiner's and my Hopf Algebras in Combinatorics (arXiv:1409.8356v5), which is the first reference that comes into my mind because it is currently open in my editor):

Property P1. If $$P$$ is a finite bounded poset, then $$\mu\left(P\right) = \sum_{k\geq 0} \left(-1\right)^k \left(\text{number of chains } 0 = x_0 < x_1 < \cdots < x_k = 1 \text{ in } P\right)$$.

Property P2. If $$P$$ and $$Q$$ are two finite bounded posets, then the Cartesian product $$P \times Q$$ (with componentwise order) satisfies $$\mu\left(P \times Q\right) = \mu\left(P\right) \cdot \mu\left(Q\right)$$.

Now, let's return to the question at hand. We assume that $$n$$ is positive, because otherwise your claim is only valid under a very creative interpretation of the $$g\left(n,k\right)$$ and the sum. Let $$B_n$$ be the poset of all subsets of $$\left\{1,2,\ldots ,n\right\}$$, ordered by inclusion. Then, $$B_n$$ is the $$n$$-fold Cartesian product $$\underbrace{B_1 \times B_1 \times \cdots \times B_1}_{n \text{ times}}$$; thus, by iterated application of Property P2, we obtain $$\mu\left(B_n\right) = \mu\left(B_1\right)^n = \left(-1\right)^n$$ (since $$B_1$$ is a $$2$$-element chain and thus has $$\mu\left(B_1\right) = -1$$). Hence,

$$\left(-1\right)^n = \mu\left(B_n\right)$$

$$= \sum_{k\geq 0} \left(-1\right)^k \left(\text{number of chains } 0 = x_0 < x_1 < \cdots < x_k = 1 \text{ in } B_n\right)$$ (by Property P1)

$$= \sum_{k\geq 0} \left(-1\right)^k \left(\text{number of chains } \emptyset = A_0 \subsetneq A_1 \subsetneq \cdots \subsetneq A_k = \left\{1,2,\ldots,n\right\}\right)$$

$$= \sum_{k\geq 1} \left(-1\right)^k \underbrace{\left(\text{number of chains } \emptyset = A_0 \subsetneq A_1 \subsetneq \cdots \subsetneq A_k = \left\{1,2,\ldots,n\right\}\right)}_{\substack{=g\left(n,k-1\right) \\ \text{(not }g\left(n,k\right)\text{, since your chain does not start at }\emptyset\text{)}}}$$ (we got rid of the $$k = 0$$ addend here, since this addend is $$0$$)

$$= \sum_{k\geq 1} \left(-1\right)^k g\left(n,k-1\right) = \sum_{k\geq 0} \left(-1\right)^{k+1} g\left(n,k\right)$$.

Dividing by $$-1$$, we transform this into

$$\left(-1\right)^{n-1} = \sum_{k\geq 0} \left(-1\right)^k g\left(n,k\right)$$,

qed.