4
$\begingroup$

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.?

$\endgroup$
6
  • 5
    $\begingroup$ 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. $\endgroup$ May 30, 2014 at 17:43
  • 3
    $\begingroup$ 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. $\endgroup$ May 30, 2014 at 17:55
  • $\begingroup$ (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. $\endgroup$ May 30, 2014 at 17:59
  • 1
    $\begingroup$ @darijgrinberg, that looks like an answer; why don't you post it as one? $\endgroup$ May 31, 2014 at 22:18
  • $\begingroup$ @KarolSzumiło, you're probably right. $\endgroup$ May 31, 2014 at 23:35

3 Answers 3

7
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Thank you! (As a helpful note to other readers, those are exponential generating functions.) $\endgroup$ Jun 1, 2014 at 4:15
  • $\begingroup$ I added the word "exponential". $\endgroup$
    – Ira Gessel
    Jun 1, 2014 at 4:47
6
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Well, this answer now only explains the comment of Karol S. (I did not refresh the comments before posting an answer.) $\endgroup$ May 30, 2014 at 18:06
  • 1
    $\begingroup$ 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. $\endgroup$ May 31, 2014 at 23:37
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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