Skip to main content
2 of 2
typo & upd ref
darij grinberg
  • 33.8k
  • 4
  • 118
  • 253

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.

darij grinberg
  • 33.8k
  • 4
  • 118
  • 253