証明募集（補足2:Philip Hallの定理）

半順序集合の理論とPhilip Hallの定理

私が最初の記事の(1)式が正しいと思った理由を説明します。
以下の記述はRechard P. Stanley, "Enumerative Combinatorics Volume I"のChapter 3の内容の抜粋です。

半順序集合

$${(P, \leq)}$$を有限半順序集合とします。
ここで$${(P, \leq)}$$が有限半順序集合とは、有限集合$${P}$$上の二項関係$${\leq }$$が以下の3条件を満たすことを言います。

1. 反射律：任意の$${s\in P}$$に対し$${s\leq s}$$が成り立つ。

2. 推移律：$${s,t,u\in P}$$が$${s\leq t, t\leq u}$$を満たすならば、$${s\leq u}$$が成り立つ。

3. 反対称律：$${s,t\in P}$$が$${s\leq t, s\geq t}$$を満たすならば、$${s=t}$$が成り立つ。

2つの有限半順序集合$${(P,\leq),(Q\leq)}$$が同型であるとは、全単射$${f:P\rightarrow Q}$$が存在して$${s\leq t \Leftrightarrow f(s)\leq f(t)}$$となることを言い、このとき$${P\cong Q}$$と書きます。
要するに、$${P}$$と$${Q}$$が実質的に同じ半順序集合であるということです。

$${s_0<\cdots < s_k}$$なる$${P}$$の元の列を、長さ$${k}$$のチェインと呼びます。
$${P}$$のチェインの長さの最大値を$${P}$$の長さといい、$${\ell(P)}$$と書きます。

2つの有限半順序集合$${(P,\leq),(Q\leq)}$$に対し、積集合$${P\times Q}$$上の順序関係を、「$${(s,s'),(t,t')\in P\times Q}$$が順序関係$${(s,s')\leq (t,t')}$$を満たすとは、$${s\leq t}$$かつ$${s'\leq t'}$$であることである」として定義することにより、これらの積$${(P\times Q, \leq)}$$を定義できます。

積の例を紹介します。
$${[2]}$$を通常の大小関係で半順序集合と思ったものを$${\mathbf{2}}$$と書きます。
$${[n]}$$のベキ集合（部分集合全ての集合）を通常の包含関係で半順序集合と思ったものを、$${B_n}$$と書きます。
このとき、$${B_n\cong \mathbf{2}\times \cdots \times \mathbf{2}=:\mathbf{2}^n}$$となります。

Möbius関数

$${(P, \leq)}$$を有限半順序集合とします。
$${s\leq t}$$となる$${s,t\in P}$$に対し、$${\mu_P(s,t)}$$を次のように帰納的に定義し、$${\mu_P}$$を$${P}$$のMöbius関数と呼びます。

$$
\begin{align*}
\mu_P(s, s) & :=1  (s \in P),\\
\mu_P(s,u) &: =-\sum_{s\leq t<u}\mu_P(s,t)  (s<t).
\end{align*}
$$

2つの有限半順序集合$${P,Q}$$があったとき、$${P\times Q}$$のMöbius関数は以下の積公式を満たします。

$${\mu_{P\times Q}((s,s'),(t,t'))=\mu_P(s,t)\mu_Q(s',t')}$$

1つ具体例を紹介します。
$${\mu_{B_n} (\emptyset , [n])}$$は次のように計算できます。

$$
\mu_{B_n} (\emptyset , [n])=\mu_{\mathbf{2}^n} ((0,\ldots ,0) , (1,\ldots ,1))=\mu_{\mathbf{2}}(0,1)^n=(-1)^n.
$$

Philip Hallの定理

有限半順序集合について、次の定理が成り立ちます。

定理（Philip Hall）
$${P}$$を有限半順序集合とする。$${\^{P}}$$を、$${P}$$に最小元$${\^{0}}$$と最大元$${\^{1}}$$を添加して得られる半順序集合とする。$${\^P}$$の$${\^{0}=s_0<\cdots < s_k=\^{1}}$$となる長さ$${k}$$のチェインの個数を$${c_k}$$と書く。このとき次の式が成り立つ。

$$
\mu_{\^{P}}(\^{0}, \^{1})=\sum_{k=1}^{\ell(\^{P})} (-1)^k c_k
$$

証明は別記事に譲ろうと思います。
この定理を$${P=B_n\setminus \{\emptyset ,[n]\}}$$に適用すれば、$${\^{P}\cong B_n}$$となって、先ほどの例から前回の記事で書いた(3)式が従い、よって最初の記事で書いた(1)式が示されたことになります。