Skip to main content
typo & upd ref
Source Link
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 §6§7.2.1 in Vic Reiner's and my Hopf Algebras in CombinatoricsVic 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 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)$.

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 -1} \left(-1\right)^k g\left(n,k\right)$$\left(-1\right)^{n-1} = \sum_{k\geq 0} \left(-1\right)^k g\left(n,k\right)$,

qed.

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 §6.2.1 in Vic Reiner's and my Hopf Algebras in Combinatorics, 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 -1} \left(-1\right)^k g\left(n,k\right)$,

qed.

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.

Source Link
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 §6.2.1 in Vic Reiner's and my Hopf Algebras in Combinatorics, 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 -1} \left(-1\right)^k g\left(n,k\right)$,

qed.