# 半順序集合と Möbius 反転：包除原理・分割束・キュムラントから、束・Dilworth の定理・Whitney 数まで

> 接続代数で Möbius 関数を定義して反転公式・包除原理・分割束の Möbius 関数を証明し、キュムラントへ応用する。束と分配束・連続束、Dilworth の定理、Whitney 数も扱う。
> https://rikai.mugen-giken.com/mathematics/combinatorics/posets-mobius

## 0. この記事の要点

「重なりのある集まりの個数を、重複を数えすぎずに求めるにはどうするか」という素朴な問いから始まる記事です。三つの集合の和集合の大きさを求めるときの「足して、重なりを引いて、また足す」という手順を、集合の包含だけでなく、約数の関係や分け方の細かさの関係といった一般の「順序」に広げると、その足し引きの係数がひとつの統一した仕組みで決まります。読み終えると、この仕組みを使って包除原理を一行で示し、さらに確率変数の積の期待値から「連結な部分」だけを取り出す公式を導けるようになります。

- 有限半順序集合 $P$ の上の「区間の関数」は、畳み込み（二つの関数から新しい関数を作る和の操作）で環（**接続代数**）をなします。定数関数 $1$（ゼータ関数 $\zeta$）の逆元が **Möbius 関数** $\mu$ です。
- **Möbius 反転**: $g(x)=\sum_{y\le x}f(y)$ なら $f(x)=\sum_{y\le x}\mu(y,x)g(y)$。証明は $\zeta*\mu=\delta$ の一行です。
- 直積の Möbius 関数は成分の積になります。ブール束では $\mu(S,T)=(-1)^{|T\setminus S|}$ で、これが**包除原理**そのものです。約数の束では数論の Möbius 関数が出ます。
- 集合 $[n]$ の分割全体のなす**分割束**では $\mu(\hat0,\hat1)=(-1)^{n-1}(n-1)!$ です。証明は前章の exp 公式に帰着します。
- 積の[期待値](/mathematics/probability/random-variables#def-expectation) $E[X_{i_1}\cdots X_{i_k}]$（モーメント）と**キュムラント**は、分割束上の和 $m(S)=\sum_\pi\prod_{B\in\pi}\kappa(B)$ で結ばれ、その反転が分割束の Möbius 関数で与えられます。独立な変数の間の混合キュムラントが $0$ になることも、この枠組みで証明できます。
- 補遺として、**束**（分配束・完備束・連続束、Knaster–Tarski の不動点定理）、有限半順序集合の幅と鎖分割を結ぶ **Dilworth の定理**（と Erdős–Szekeres の定理）、階数ごとの元の数と Möbius 関数の和である **Whitney 数**（分割束では Stirling 数）を扱います。

<Aside type="tip" title="この記事で使う事前知識">

- **半順序**: 反射律・反対称律・推移律を満たす大小関係。全ての 2 元が比べられるとは限りません。→ [半順序](/mathematics/foundations/axiom-of-choice-zorn#def-poset)
- **行列の積**: 行と列の成分を掛けて足す演算。接続代数の畳み込みは上三角行列の積と同じものです。→ [行列の積](/mathematics/linear-algebra/matrices-and-linear-systems#def-product)
- **集合の分割**: 集合を空でない互いに素な部分（ブロック）に分けること。→ [集合の分割](/mathematics/foundations/equivalence-relations#def-partition)
- **期待値**: 確率変数の値を確率で重みづけして足した平均。→ [期待値](/mathematics/probability/random-variables#def-expectation)
- **exp 公式**: 前章の、全体の指数型母関数と連結なものの母関数を $\exp$ で結ぶ公式。→ [exp 公式](/mathematics/combinatorics/enumeration-generating-functions#thm-exp-formula)

</Aside>

## 1. 動機

三つの集合 $A,B,C$ の和集合の大きさは $|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$ です。この符号つきの足し引きは、「どの集合に属するか」という情報をもつ要素を、集合の包含関係の上で整理し直しているだけです。同じ操作は、整数の約数関係（Euler の $\varphi$ や Möbius の $\mu$）、集合の分割の細分関係（モーメントとキュムラント）にも現れます。**包含関係の代わりに一般の半順序を置いたとき、符号つきの足し引きを担う係数が Möbius 関数**です。

確率論や統計力学では、積の期待値（モーメント、相関関数）から「連結な部分」（キュムラント、打ち切り相関関数）を取り出す操作が基本になります。前章で見たとおり、全体の指数型母関数と連結なものの母関数は $\exp$/$\log$ で結ばれます。この章は、それを任意の多変数に拡張したときの、母関数を使わない形が分割束の Möbius 反転であることを示します。

## 2. 半順序集合と接続代数

<Definition id="def-poset" title="半順序集合・区間">
集合 $P$ 上の関係 $\le$ が、反射律（$x\le x$）、反対称律（$x\le y$ かつ $y\le x$ なら $x=y$）、推移律（$x\le y\le z$ なら $x\le z$）を満たすとき、組 $(P,\le)$ を**半順序集合**という。以下 $P$ は有限とする。$x\le y$ のとき**区間** $[x,y]=\{z\in P:x\le z\le y\}$ を定め、$\mathrm{Int}(P)=\{(x,y):x\le y\}$ とおく。$P$ に最小元 $\hat0$ や最大元 $\hat1$ があるとき、それぞれ $\hat0,\hat1$ と書く。
</Definition>

<Example id="ex-posets" title="三つの基本的な半順序集合">
(a) 集合 $[n]=\{1,\dots,n\}$ の部分集合全体 $B_n$ を包含 $\subseteq$ で順序づけたもの（**ブール束**）。最小元は $\varnothing$、最大元は $[n]$ です。(b) 正の整数 $n$ の約数全体 $D_n$ を、整除 $d\mid d'$ で順序づけたもの。(c) 全順序集合（鎖） $\{0\lt 1\lt \dots\lt e\}$。(d) 二つの半順序集合 $P,Q$ の**直積** $P\times Q$ は、成分ごとの順序 $(p,q)\le(p',q')\iff p\le p'$ かつ $q\le q'$ で定める。
</Example>

足し引きの係数を「順序の中の二点 $x\le y$ ごとに決まる数」として一括して扱いたいので、$P$ 上の「区間の関数」の全体を考え、そこに掛け算（畳み込み）を入れます。逆元を取るという代数的な操作が、符号つきの足し引きの係数を与えることになります。

<Definition id="def-incidence-algebra" title="接続代数・ゼータ関数・Möbius 関数">
$I(P)$ を、$f:\mathrm{Int}(P)\to\mathbb{C}$ の全体とする。$f,g\in I(P)$ の**畳み込み**を
$$
(f*g)(x,y)=\sum_{x\le z\le y}f(x,z)\,g(z,y)
$$
で定める。$\delta(x,y)=[x=y]$（$x=y$ のとき $1$、そうでなければ $0$）と $\zeta(x,y)=1$ をそれぞれ**単位関数**・**ゼータ関数**という。
</Definition>

<Lemma id="lem-incidence-ring" title="接続代数は環で、可逆性は対角成分で決まる">
1. $(I(P),+,*)$ は $\delta$ を単位元とする結合的な環である。
2. $f\in I(P)$ が（両側）可逆であるための必要十分条件は、全ての $x$ について $f(x,x)\neq0$ である。
</Lemma>

<Proof of="lem-incidence-ring">
1: $((f*g)*h)(x,y)=\sum_{x\le z\le w\le y}f(x,z)g(z,w)h(w,y)=(f*(g*h))(x,y)$ で、どちらも同じ有限和です。$\delta$ が単位元であることも定義から明らかです。

2: $fg'=\delta$ なら $x=y$ で $f(x,x)g'(x,x)=1$ なので必要です。十分性は、区間の長さ（$[x,y]$ の元の個数）に関する帰納法で $f*h=\delta$ を満たす $h$ を作ります。$h(x,x)=1/f(x,x)$ とし、$x\lt y$ では $\sum_{x\le z\le y}f(x,z)h(z,y)=0$ より
$$
h(x,y)=-\frac1{f(x,x)}\sum_{x\lt z\le y}f(x,z)\,h(z,y)
$$
とします。右辺には $[z,y]\subsetneq[x,y]$ の $h$ しか現れないので帰納的に定まります。同様に $h'*f=\delta$ を満たす $h'$ が作れます。結合律から $h'=h'*(f*h)=(h'*f)*h=h$ です。
</Proof>

<Definition id="def-mobius-function" title="Möbius 関数">
$\zeta$ は対角成分が $1$ なので <Ref to="lem-incidence-ring" /> により可逆である。その逆元 $\mu=\zeta^{-1}$ を $P$ の **Möbius 関数**という。定義式は $\zeta*\mu=\mu*\zeta=\delta$、すなわち
$$
\mu(x,x)=1,\qquad \sum_{x\le z\le y}\mu(z,y)=\sum_{x\le z\le y}\mu(x,z)=0\quad(x\lt y)
$$
である。とくに $\mu(x,y)=-\sum_{x\le z\lt y}\mu(x,z)$ という漸化式で計算できる。
</Definition>

$\mu(x,y)$ は区間 $[x,y]$ の構造だけで決まります（漸化式が区間の内部しか使わないからです）。区間として同型な（順序を保つ全単射がある）二つの区間は同じ $\mu$ の値をもちます。

**行列としての見方。** $P$ の元を、$x\le y$ なら $x$ が $y$ より先に来るように一列に並べます（線形拡張）。すると $f\in I(P)$ は、$f(x,y)$ を $(x,y)$ 成分、$x\not\le y$ の成分を $0$ とする上三角行列と同一視でき、畳み込みは[行列の積](/mathematics/linear-algebra/matrices-and-linear-systems#def-product)に一致します。$\zeta$ は対角成分が全て $1$ の上三角行列で、$\mu$ はその逆行列です。<Ref to="lem-incidence-ring" /> の 2 の「対角成分が $0$ でない上三角行列は可逆」は線形代数でおなじみの事実で、証明で作った漸化式は後退代入そのものです。ただし $\mu$ を求めるときは、行列全体ではなく一つの区間の中だけを見れば足りる、という局所性が大事です。

<Example id="ex-mobius-d12" title="12 の約数の束で μ(1, d) を計算する">
$D_{12}=\{1,2,3,4,6,12\}$ で、漸化式 $\mu(1,d)=-\sum_{z\mid d,\ z\ne d}\mu(1,z)$ を小さい方から使います。$\mu(1,1)=1$、$\mu(1,2)=-1$、$\mu(1,3)=-1$、$\mu(1,4)=-(1-1)=0$、$\mu(1,6)=-(1-1-1)=1$、$\mu(1,12)=-(1-1-1+0+1)=0$ です（$6$ の約数 $1,2,3$ と $12$ の約数 $1,2,3,4,6$ を足している）。後で見るとおり、これは数論の Möbius 関数の値 $\mu_{\mathbb N}(1),\dots,\mu_{\mathbb N}(12)$ と一致します。
</Example>

<Example id="ex-mobius-chain" title="鎖の Möbius 関数">
鎖 $\{0\lt 1\lt \dots\lt e\}$ では、$\mu(i,i)=1$、$\mu(i,i+1)=-1$、$j-i\ge2$ なら $\mu(i,j)=0$ です。実際 $\mu(i,i+1)=-\mu(i,i)=-1$ で、$j=i+2$ のとき $\mu(i,i+2)=-(1-1)=0$、以下 $\mu(i,j)=-\sum_{i\le z\lt j}\mu(i,z)=-(1-1+0+\cdots)=0$ です。
</Example>

## 3. Möbius 反転

<Theorem id="thm-mobius-inversion" title="Möbius 反転公式">
$P$ を有限半順序集合、$f,g:P\to\mathbb{C}$ とする。

1. 全ての $x$ について $g(x)=\sum_{y\le x}f(y)$ であることと、全ての $x$ について $f(x)=\sum_{y\le x}\mu(y,x)\,g(y)$ であることは同値である。
2. 全ての $x$ について $g(x)=\sum_{y\ge x}f(y)$ であることと、全ての $x$ について $f(x)=\sum_{y\ge x}\mu(x,y)\,g(y)$ であることは同値である。
</Theorem>

<Proof of="thm-mobius-inversion">
1 の（$\Rightarrow$）: $g$ の式を代入すると、
$$
\sum_{y\le x}\mu(y,x)g(y)=\sum_{y\le x}\mu(y,x)\sum_{z\le y}f(z)=\sum_{z\le x}f(z)\sum_{z\le y\le x}\zeta(z,y)\mu(y,x)=\sum_{z\le x}f(z)\delta(z,x)=f(x)
$$
です。（$\Leftarrow$）: $f$ の式を $\sum_{y\le x}f(y)$ に代入すると、同様に $\sum_{y\le x}\sum_{z\le y}\mu(z,y)g(z)=\sum_{z\le x}g(z)\sum_{z\le y\le x}\mu(z,y)\zeta(y,x)=g(x)$ です。

2: $\sum_{y\ge x}\mu(x,y)g(y)=\sum_{y\ge x}\mu(x,y)\sum_{z\ge y}f(z)=\sum_{z\ge x}f(z)\sum_{x\le y\le z}\mu(x,y)\zeta(y,z)=f(x)$、逆向きも $\mu*\zeta$ と $\zeta*\mu$ を入れ替えて同様です。
</Proof>

<Proposition id="prop-mobius-product" title="直積の Möbius 関数">
有限半順序集合 $P,Q$ の Möbius 関数を $\mu_P,\mu_Q$ とすると、$P\times Q$ の Möbius 関数は
$$
\mu_{P\times Q}\bigl((p,q),(p',q')\bigr)=\mu_P(p,p')\,\mu_Q(q,q')
$$
である。
</Proposition>

<Proof of="prop-mobius-product">
右辺を $\nu$ とおきます。区間 $[(p,q),(p',q')]$ は $[p,p']\times[q,q']$ なので、
$$
\sum_{(p'',q'')}\zeta\bigl((p,q),(p'',q'')\bigr)\nu\bigl((p'',q''),(p',q')\bigr)=\Bigl(\sum_{p\le p''\le p'}\mu_P(p'',p')\Bigr)\Bigl(\sum_{q\le q''\le q'}\mu_Q(q'',q')\Bigr)=\delta(p,p')\delta(q,q')
$$
です。$\zeta_{P\times Q}*\nu=\delta$ なので、<Ref to="lem-incidence-ring" /> の逆元の一意性から $\nu=\mu_{P\times Q}$ です。
</Proof>

<Proposition id="prop-mobius-boolean-divisor" title="ブール束と約数の束の Möbius 関数">
(1) ブール束 $B_n$（$[n]$ の部分集合全体を包含で順序づけたもの）では $\mu(S,T)=(-1)^{|T\setminus S|}$（$S\subseteq T$）である。

(2) 正整数 $n$ の約数の束 $D_n$（整除で順序づけたもの）では $\mu(d,d')=\mu_{\mathbb N}(d'/d)$ である。ここで $\mu_{\mathbb N}(m)$ は $m$ が平方因子をもたなければ $(-1)^{k}$（$k$ は $m$ の素因数の個数）、そうでなければ $0$ とする。
</Proposition>

<Proof of="prop-mobius-boolean-divisor">
まず鎖 $\{0\lt 1\lt\dots\lt e\}$ の Möbius 関数を求めます。$\mu(i,i)=1$ で、<Ref to="def-mobius-function" /> の漸化式から $\mu(i,i+1)=-\mu(i,i)=-1$、$j=i+2$ では $\mu(i,i+2)=-(1-1)=0$、以下帰納的に $j-i\ge2$ なら $\mu(i,j)=-\sum_{i\le z\lt j}\mu(i,z)=-(1-1+0+\cdots+0)=0$ です。

(1) $B_n$ は 2 点の鎖 $\{0\lt 1\}$ の $n$ 個の直積と順序同型です（部分集合を指示ベクトルに対応させる）。2 点の鎖では $\mu(0,1)=-1$ なので、<Ref to="prop-mobius-product" /> を繰り返し使って $\mu(S,T)=(-1)^{|T\setminus S|}$ を得ます。

(2) $n=p_1^{e_1}\cdots p_r^{e_r}$ とすると、約数 $d=\prod p_i^{a_i}$ に指数のベクトル $(a_i)$ を対応させて $D_n\cong\prod_i\{0\lt 1\lt \dots\lt e_i\}$ です。区間 $[d,d']$ は $D_{d'/d}$ と同型なので $\mu(d,d')=\mu(1,d'/d)$ で、$m=d'/d=\prod p_i^{b_i}$ とすれば、鎖の結果と <Ref to="prop-mobius-product" /> から $\mu(1,m)=\prod_i\mu_i(0,b_i)$ は、すべての $b_i\le1$ なら $(-1)^{\sum b_i}$、ある $b_i\ge2$ なら $0$ です。これが $\mu_{\mathbb N}(m)$ です。
</Proof>

<Example id="ex-mobius-boolean" title="ブール束と約数の束">
**ブール束** $B_n$ は 2 点の鎖 $\{0\lt 1\}$ の $n$ 個の直積と順序同型です（部分集合 $S$ を指示ベクトルに対応させます）。2 点の鎖では <Ref to="ex-mobius-chain" /> より $\mu(0,1)=-1$ なので、<Ref to="prop-mobius-product" /> から
$$
\mu(S,T)=(-1)^{|T\setminus S|}\qquad(S\subseteq T).
$$
**約数の束** $D_n$ では、$n=p_1^{e_1}\cdots p_r^{e_r}$ とすると $D_n\cong\prod_i\{0\lt 1\lt \dots\lt e_i\}$ です（約数 $d=\prod p_i^{a_i}$ を指数のベクトル $(a_i)$ に対応させる）。<Ref to="ex-mobius-chain" /> と <Ref to="prop-mobius-product" /> より、$\mu(1,d)$ は $d$ が平方因子をもたなければ $(-1)^{k}$（$k$ は $d$ の素因数の個数）、そうでなければ $0$ です。これは数論の **Möbius 関数** $\mu_{\mathbb N}(d)$ にほかなりません。また区間 $[d,d']$ は $D_{d'/d}$ と同型なので $\mu(d,d')=\mu_{\mathbb N}(d'/d)$ です。
</Example>

## 4. 包除原理

<Theorem id="thm-inclusion-exclusion" title="包除原理">
$X$ を有限集合、$A_1,\dots,A_n\subseteq X$ とし、$S\subseteq[n]$ に対し $A_S=\bigcap_{i\in S}A_i$ （$A_\varnothing=X$）とおく。このとき
$$
\Bigl|X\setminus\bigcup_{i=1}^nA_i\Bigr|=\sum_{S\subseteq[n]}(-1)^{|S|}\,|A_S|.
$$
したがって $\bigl|\bigcup_iA_i\bigr|=\sum_{S\neq\varnothing}(-1)^{|S|-1}|A_S|$ である。
</Theorem>

<Proof of="thm-inclusion-exclusion">
$x\in X$ に対し $E(x)=\{i:x\in A_i\}\subseteq[n]$ とし、$T\subseteq[n]$ について $f(T)=\#\{x:E(x)=T\}$、$g(S)=|A_S|$ とおきます。$x\in A_S$ であることは $E(x)\supseteq S$ と同値なので
$$
g(S)=\sum_{T\supseteq S}f(T).
$$
ブール束 $B_n$ に <Ref to="thm-mobius-inversion" /> の 2 を適用し、<Ref to="prop-mobius-boolean-divisor" /> の $\mu(\varnothing,S)=(-1)^{|S|}$ を使うと
$$
f(\varnothing)=\sum_{S}\mu(\varnothing,S)g(S)=\sum_S(-1)^{|S|}|A_S|
$$
です。左辺はどの $A_i$ にも属さない要素の個数です。後半は $|X|-|X\setminus\bigcup A_i|$ に前半を代入すると得られます。
</Proof>

<Example id="ex-ie-applications" title="乱列・Euler の関数・全射の個数">
(a) **乱列**。$X$ を $[n]$ の置換全体、$A_i$ を $i$ を固定する置換の集合とします。$|A_S|=(n-|S|)!$ で $|S|=k$ となる $S$ は $\binom nk$ 個なので、乱列の個数は $d_n=\sum_{k=0}^n(-1)^k\binom nk(n-k)!=n!\sum_k\frac{(-1)^k}{k!}$ です。前章の exp 公式から得た値と一致します。

(b) **Euler の関数**。$n$ の相異なる素因数を $p_1,\dots,p_r$ とし、$X=\{1,\dots,n\}$、$A_i$ を $p_i$ の倍数の集合とします。$|A_S|=n/\prod_{i\in S}p_i$ なので $\varphi(n)=\sum_S(-1)^{|S|}\frac n{\prod_Sp_i}=n\prod_{i=1}^r\Bigl(1-\frac1{p_i}\Bigr)$ です。

(c) **全射の個数**。$[n]$ から $[k]$ への写像のうち全射であるものは、$A_i$ を「値 $i$ をとらない写像」として $\sum_{j=0}^k(-1)^j\binom kj(k-j)^n$ 個です。これを $k!$ で割ったものが第 2 種 Stirling 数 $S(n,k)$（$[n]$ の $k$ ブロックへの分割の個数）です。
</Example>

## 5. 分割束

有限集合 $S$ の[分割](/mathematics/foundations/equivalence-relations#def-partition)（空でない互いに素なブロックへの分解）の全体を $\Pi(S)$ と書き、$\Pi_n=\Pi([n])$ とします。$\pi,\sigma\in\Pi(S)$ に対し、$\pi$ の各ブロックが $\sigma$ のあるブロックに含まれるとき $\pi\le\sigma$（$\pi$ は $\sigma$ の**細分**）と定めます。これは半順序で、最小元 $\hat0$ は全ての元が単独のブロックの分割、最大元 $\hat1=\{S\}$ は一つのブロックだけの分割です。$|\pi|$ でブロックの個数を表します。$\Pi(S)$ は $S$ 上の同値関係全体と同じものです（同値関係の同値類が分割）。

<Figure caption="分割束 Π₃ のハッセ図（下が細かい分割）。各頂点の下の数は μ(0̂, ·) の値で、総和が 1 − 3 + 2 = 0 になる。">
<svg viewBox="0 0 330 250" width="100%" role="img" aria-label="三元集合の分割束のハッセ図とメビウス関数の値">
  <g stroke="currentColor" stroke-width="1.5">
    <line x1="165" y1="40" x2="70" y2="110" /><line x1="165" y1="40" x2="165" y2="110" /><line x1="165" y1="40" x2="260" y2="110" />
    <line x1="70" y1="110" x2="165" y2="180" /><line x1="165" y1="110" x2="165" y2="180" /><line x1="260" y1="110" x2="165" y2="180" />
  </g>
  <g fill="var(--sl-color-accent)">
    <circle cx="165" cy="40" r="6" /><circle cx="70" cy="110" r="6" /><circle cx="165" cy="110" r="6" /><circle cx="260" cy="110" r="6" /><circle cx="165" cy="180" r="6" />
  </g>
  <g fill="currentColor" font-size="13" text-anchor="middle">
    <text x="165" y="26">123</text>
    <text x="70" y="96">12|3</text><text x="165" y="96">13|2</text><text x="260" y="96">1|23</text>
    <text x="165" y="206">1|2|3</text>
    <text x="190" y="44" text-anchor="start">μ = 2</text>
    <text x="48" y="132">μ = −1</text><text x="165" y="132" dx="32">μ = −1</text><text x="282" y="132">μ = −1</text>
    <text x="165" y="226">μ = 1</text>
  </g>
</svg>
</Figure>

<Proposition id="prop-partition-interval" title="分割束の区間の構造">
$\Pi(S)$ の元 $\pi\le\sigma$ をとり、$\sigma$ のブロックを $C_1,\dots,C_r$、$C_i$ に含まれる $\pi$ のブロックの個数を $k_i$ とする。このとき区間 $[\pi,\sigma]$ は直積 $\Pi_{k_1}\times\cdots\times\Pi_{k_r}$ と順序同型である。とくに $[\hat0,\pi]\cong\prod_{B\in\pi}\Pi_{|B|}$、$[\pi,\hat1]\cong\Pi_{|\pi|}$。
</Proposition>

<Proof of="prop-partition-interval">
$\tau\in[\pi,\sigma]$ とします。$\tau$ の各ブロックは $\pi$ のブロックの和集合で、かつ $\sigma$ のあるブロック $C_i$ に含まれます。したがって $\tau$ は、各 $i$ について「$C_i$ に含まれる $\pi$ のブロック（$k_i$ 個）の分割」$\tau_i$ を選ぶことと同じです。逆に任意の $(\tau_i)$ から $\tau\in[\pi,\sigma]$ が定まります。$\tau\le\tau'$ は、各 $i$ で $\tau_i\le\tau'_i$ と同値なので、対応は順序同型です。
</Proof>

次の定理のねらいは、一見複雑な分割束の Möbius 関数が、実は $(-1)^{n-1}(n-1)!$ という単純な形になることを示すことです。方針は、区間が小さい分割束の直積になること（上の命題）から値を未知数 $m_n$ の関係式にまとめ、前章の exp 公式で $m_n$ を決めることです。

<Theorem id="thm-partition-mobius" title="分割束の Möbius 関数">
$n\ge1$ のとき、$\Pi_n$ の Möbius 関数について
$$
\mu(\hat0,\hat1)=(-1)^{n-1}(n-1)!
$$
である。一般に $\pi\le\sigma$ で、$\sigma$ のブロック $C_i$ が $\pi$ の $k_i$ 個のブロックを含むなら $\mu(\pi,\sigma)=\prod_i(-1)^{k_i-1}(k_i-1)!$ である。
</Theorem>

<Proof of="thm-partition-mobius">
$m_n=\mu(\hat0,\hat1)$（$\Pi_n$ において）とおきます。$m_1=1$ です。$\sum_{\hat0\le\pi\le\hat1}\mu(\hat0,\pi)=\delta(\hat0,\hat1)$ より、$n\ge1$ について
$$
\sum_{\pi\in\Pi_n}\mu(\hat0,\pi)=[n=1].
$$
<Ref to="prop-partition-interval" /> により $[\hat0,\pi]\cong\prod_{B\in\pi}\Pi_{|B|}$ なので、<Ref to="prop-mobius-product" /> から $\mu(\hat0,\pi)=\prod_{B\in\pi}m_{|B|}$ です。したがって
$$
\sum_{\pi\in\Pi_n}\prod_{B\in\pi}m_{|B|}=[n=1]\qquad(n\ge1).
$$
左辺は前章の <Ref to="mathematics/combinatorics/enumeration-generating-functions#thm-exp-formula" /> の $a_n$ で $c_k=m_k$ としたものです。$a_0=1$ と合わせて、$M(x)=\sum_{k\ge1}m_k\frac{x^k}{k!}$ に対し $\exp(M(x))=1+x$ が成り立ちます。<Ref to="mathematics/combinatorics/enumeration-generating-functions#prop-fps-exp" /> の 4 により $M(x)=\log(1+x)=\sum_{k\ge1}\frac{(-1)^{k-1}}kx^k$ です。係数を比べて $\frac{m_k}{k!}=\frac{(-1)^{k-1}}k$、つまり $m_k=(-1)^{k-1}(k-1)!$ です。

一般の主張は、<Ref to="prop-partition-interval" /> で $[\pi,\sigma]\cong\prod_i\Pi_{k_i}$ となることと、<Ref to="prop-mobius-product" /> から従います。
</Proof>

たとえば $n=3$ では $\mu(\hat0,\hat1)=2$ で、上の図の値と一致します。$n=4$ では $-6$ です（<Ref to="exr-pi4" />）。

## 6. モーメントとキュムラント

確率変数 $X_1,\dots,X_n$ は実数値で、全ての次数のモーメントが有限とします。空でない $S\subseteq[n]$ に対し
$$
m(S)=E\Bigl[\prod_{i\in S}X_i\Bigr]
$$
を**混合モーメント**とします。$\pi\in\Pi(S)$ に対し $m_\pi=\prod_{B\in\pi}m(B)$ とおきます。

定義の考え方を、変数が 2 個の場合で先に見ておきます。$E[XY]$ は「$X$ と $Y$ が結びついた部分」と「$X$ と $Y$ が別々に動く部分 $E[X]E[Y]$」の和に分けられるはずで、前者を $\kappa(X,Y)$ と名づけたものが共分散です。変数が増えても、「どの変数どうしが結びついているか」の分け方は集合の分割で表され、その全ての分け方について足し合わせたものがモーメントになる、というのが次の定義です。

<Definition id="def-cumulant" title="混合キュムラント">
$S$ の部分集合に対する数 $\kappa(S)$ を、再帰的に次で定める。
$$
m(S)=\sum_{\pi\in\Pi(S)}\ \prod_{B\in\pi}\kappa(B).
$$
右辺で $\pi=\hat1=\{S\}$ の項が $\kappa(S)$、それ以外の項は $|S|$ より小さい集合の $\kappa$ だけで書かれるので、$\kappa(S)$ は $|S|$ に関する帰納法で一意に定まる。$\kappa(S)$ を $X_i$ $(i\in S)$ の**混合キュムラント**といい、$\kappa(X_{i_1},\dots,X_{i_k})$ とも書く。$\kappa_\pi=\prod_{B\in\pi}\kappa(B)$ とおく。
</Definition>

$|S|=1$ では $\kappa(X)=E[X]$、$|S|=2$ では $m(\{1,2\})=\kappa(\{1,2\})+\kappa(1)\kappa(2)$ より $\kappa(X,Y)=E[XY]-E[X]E[Y]$（共分散）です。

<Theorem id="thm-moment-cumulant" title="キュムラントの反転公式">
任意の空でない $S$ について
$$
\kappa(S)=\sum_{\pi\in\Pi(S)}(-1)^{|\pi|-1}(|\pi|-1)!\ \prod_{B\in\pi}m(B).
$$
</Theorem>

<Proof of="thm-moment-cumulant">
$\pi\in\Pi(S)$ の各ブロック $B$ に <Ref to="def-cumulant" /> を適用し、積を展開します。$B$ ごとに $B$ の分割 $\rho_B$ を一つ選ぶことは、$\pi$ の細分 $\sigma=\bigcup_B\rho_B$ を一つ選ぶことと同じなので
$$
m_\pi=\prod_{B\in\pi}\sum_{\rho_B\in\Pi(B)}\kappa_{\rho_B}=\sum_{\sigma\le\pi}\kappa_\sigma.
$$
これは分割束 $\Pi(S)$ の上の関係 $g(\pi)=\sum_{\sigma\le\pi}f(\sigma)$（$g=m_\bullet$、$f=\kappa_\bullet$）です。<Ref to="thm-mobius-inversion" /> の 1 により $\kappa_\pi=\sum_{\sigma\le\pi}\mu(\sigma,\pi)m_\sigma$ で、$\pi=\hat1$ とすると $\kappa(S)=\sum_\sigma\mu(\sigma,\hat1)m_\sigma$ です。<Ref to="prop-partition-interval" /> より $[\sigma,\hat1]\cong\Pi_{|\sigma|}$ なので、<Ref to="thm-partition-mobius" /> から $\mu(\sigma,\hat1)=(-1)^{|\sigma|-1}(|\sigma|-1)!$ です。
</Proof>

<Example id="ex-cumulants-low" title="低次のキュムラント">
<Ref to="thm-moment-cumulant" /> から、$S=\{1,2,3\}$ で
$$
\kappa(X_1,X_2,X_3)=m_{123}-m_1m_{23}-m_2m_{13}-m_3m_{12}+2m_1m_2m_3
$$
です（ブロックが 2 個の分割 3 通りは符号 $-1$、3 個の分割は $+2$）。一つの変数 $X$ の $4$ 次では、ブロック型が $(4)$ が 1 個、$(3,1)$ が 4 個、$(2,2)$ が 3 個、$(2,1,1)$ が 6 個、$(1,1,1,1)$ が 1 個なので
$$
\kappa_4=m_4-4m_3m_1-3m_2^2+12m_2m_1^2-6m_1^4
$$
です。平均 $0$、分散 $\sigma^2$ の正規分布では $m_4=3\sigma^4$、$m_2=\sigma^2$、$m_1=m_3=0$ なので $\kappa_4=3\sigma^4-3\sigma^4=0$ です。
</Example>

この公式の読み方を補足しておきます。<Ref to="def-cumulant" /> は「積の期待値は、変数を"連結な塊"にグループ分けする全ての仕方について、塊ごとの寄与 $\kappa(B)$ を掛けて足したもの」と読めます。グラフの連結成分への分割と同じ構図で、$\kappa$ が"連結な部分"、$m$ が"連結とは限らない全体"に当たります。<Ref to="thm-moment-cumulant" /> は、全体から連結な部分を取り出す操作が、分割束の Möbius 関数を係数とする符号つきの足し引きだとわかるものです。

<Example id="ex-connected-mobius" title="連結グラフの個数を Möbius 反転で求める">
前章の <Ref to="mathematics/combinatorics/enumeration-generating-functions#ex-connected-graphs" /> では、$[n]$ 上の連結グラフの個数 $c_n$ を、全グラフの個数 $g_n=2^{\binom n2}$ から漸化式で求めました。同じ量が <Ref to="thm-moment-cumulant" /> と同じ形の公式で直接求まります。分割 $\pi\in\Pi_n$ に対し、$f(\pi)$ を「連結成分の分割がちょうど $\pi$ であるグラフ」の個数、$g(\pi)$ を「各連結成分が $\pi$ のいずれかのブロックに含まれるグラフ」の個数とします。前者は $\prod_{B\in\pi}c_{|B|}$、後者は各ブロックの中で辺を自由に選ぶので $\prod_{B\in\pi}g_{|B|}$ です。連結成分の分割は $\pi$ の細分なので $g(\pi)=\sum_{\sigma\le\pi}f(\sigma)$ で、<Ref to="thm-mobius-inversion" /> の 1 を $\pi=\hat1$ に使うと
$$
c_n=\sum_{\sigma\in\Pi_n}(-1)^{|\sigma|-1}(|\sigma|-1)!\prod_{B\in\sigma}g_{|B|}
$$
です。$n=3$ では $c_3=g_3-3g_2g_1+2g_1^3=8-6+2=4$、$n=4$ では <Ref to="ex-cumulants-low" /> の係数を使って $c_4=g_4-4g_3g_1-3g_2^2+12g_2g_1^2-6g_1^4=64-32-12+24-6=38$ です。漸化式から得た値 $4,38$ と一致します。
</Example>

<Example id="ex-uncorrelated" title="無相関でも独立ではない：3 次の混合キュムラント">
$X\sim N(0,1)$、$Y=X^2$ とします。$\kappa(X,Y)=E[X^3]-E[X]E[X^2]=0$ なので $X,Y$ は無相関ですが、$Y$ は $X$ の関数なので独立ではありません。実際 $\kappa(X,X,Y)$ を <Ref to="ex-cumulants-low" /> の 3 変数の式で計算すると、$m_{123}=E[X^4]=3$、$m_1=m_2=0$、$m_3=E[Y]=1$、$m_{12}=E[X^2]=1$ なので $\kappa(X,X,Y)=3-m_3m_{12}=2\neq0$ です。<Ref to="thm-independence-cumulants" /> の対偶により、独立なら起こらない非零の混合キュムラントが検出されます。2 次の（共分散の）情報だけでは独立性は判定できないことを、高次の混合キュムラントが補っている例です。
</Example>

### 6.1. 一変数の場合：モーメント母関数の対数

$\kappa_n=\kappa(X,\dots,X)$（$n$ 個）と書きます。分割の重み $\prod_B\kappa(B)$ は、全ての変数が同じなのでブロックの大きさだけで決まります。

<Proposition id="prop-cumulant-generating" title="キュムラントは母関数の対数の係数">
一つの確率変数 $X$（全ての次数のモーメントが有限）について、形式的冪級数として
$$
\sum_{n\ge0}E[X^n]\frac{t^n}{n!}=\exp\Bigl(\sum_{n\ge1}\kappa_n\frac{t^n}{n!}\Bigr)
$$
が成り立つ。
</Proposition>

<Proof of="prop-cumulant-generating">
<Ref to="def-cumulant" /> の定義式で全ての $X_i$ を $X$ とすると $E[X^n]=\sum_{\pi\in\Pi_n}\prod_{B\in\pi}\kappa_{|B|}$ です。これは前章の <Ref to="mathematics/combinatorics/enumeration-generating-functions#thm-exp-formula" /> の $a_n$ で $c_k=\kappa_k$ とした場合なので、結論が従います。
</Proof>

$E[e^{tX}]$ が $0$ の近くで有限なら、左辺はモーメント母関数で、$\kappa_n$ は**キュムラント母関数** $\log E[e^{tX}]$ の Taylor 係数です。統計や物理で「キュムラント」と呼ばれるものと、この記事の定義が一致することが、これで確かめられました。

<Example id="ex-normal-poisson" title="正規分布・Poisson 分布">
$X\sim N(0,\sigma^2)$ なら $E[e^{tX}]=e^{\sigma^2t^2/2}$ です。<Ref to="prop-cumulant-generating" /> の両辺で $\exp$ の中身を比べると（$\exp(h)=1$ なら $h'=0$、$h_0=0$ より $h=0$ なので、$\exp$ は単射です）$\kappa_2=\sigma^2$ で他の $\kappa_n=0$ です。よって $E[X^{2k}]$ では大きさ 2 のブロックだけからなる分割（完全マッチング）の個数 $(2k-1)!!$ が効いて、$E[X^{2k}]=(2k-1)!!\,\sigma^{2k}$ です。

平均 $\lambda$ の Poisson 分布では $E[e^{tX}]=\exp(\lambda(e^t-1))$ で、キュムラント母関数は $\lambda(e^t-1)$ なので全ての $\kappa_n=\lambda$ です。$E[X^n]=\sum_{\pi\in\Pi_n}\lambda^{|\pi|}$ で、$\lambda=1$ なら Bell 数 $|\Pi_n|$ です。
</Example>

### 6.2. 多変数：独立性と加法性

<Proposition id="prop-cumulant-multilinear" title="キュムラントの多重線形性">
$\kappa(X_1,\dots,X_n)$ は各変数について線形である：$X_i$ を $aY+bZ$ で置き換えると、$a\kappa(\dots,Y,\dots)+b\kappa(\dots,Z,\dots)$ になる。
</Proposition>

<Proof of="prop-cumulant-multilinear">
<Ref to="thm-moment-cumulant" /> の右辺の各項 $\prod_{B\in\pi}m(B)$ では、各 $X_i$ がちょうど一つのブロックのモーメントに一度だけ現れます。期待値と積は各変数について線形なので、各項が線形で、したがって和も線形です。
</Proof>

<Theorem id="thm-independence-cumulants" title="独立な変数の混合キュムラント">
$[n]=I\sqcup J$ として、確率変数の族 $(X_i)_{i\in I}$ と $(X_j)_{j\in J}$ が独立とする。$S\subseteq[n]$ が $I$ と $J$ の両方と交わるなら $\kappa(S)=0$ である。
</Theorem>

<Proof of="thm-independence-cumulants">
$|S|$ に関する帰納法で示します。$S\cap I$ と $S\cap J$ がともに空でない $S$ をとり、真部分集合では主張が成り立つと仮定します。$m(S)=\sum_{\pi\in\Pi(S)}\prod_{B\in\pi}\kappa(B)$ の項を分類します。$\pi$ が $I$ と $J$ の両方と交わるブロック $B$ を含むなら、$B\ne S$ のとき帰納法の仮定で $\kappa(B)=0$ です。残るのは (i) $\pi=\hat1$（項は $\kappa(S)$）と (ii) 全てのブロックが $S\cap I$ か $S\cap J$ の中に入る $\pi$ です。(ii) の $\pi$ は、$S\cap I$ の分割 $\pi_I$ と $S\cap J$ の分割 $\pi_J$ の組と一対一に対応するので、これらの項の和は
$$
\sum_{\pi_I}\prod_{B\in\pi_I}\kappa(B)\cdot\sum_{\pi_J}\prod_{B\in\pi_J}\kappa(B)=m(S\cap I)\,m(S\cap J)
$$
です。独立性から $m(S)=m(S\cap I)\,m(S\cap J)$ なので、$m(S)=\kappa(S)+m(S\cap I)m(S\cap J)$ より $\kappa(S)=0$ です。
</Proof>

<Corollary id="cor-cumulant-additive" title="独立な確率変数の和のキュムラント">
$X,Y$ が独立なら、全ての $n\ge1$ で $\kappa_n(X+Y)=\kappa_n(X)+\kappa_n(Y)$ である。
</Corollary>

<Proof of="cor-cumulant-additive">
<Ref to="prop-cumulant-multilinear" /> により $\kappa_n(X+Y)=\kappa(X+Y,\dots,X+Y)$ を各スロットで展開すると、$2^n$ 個の項 $\kappa(Z_1,\dots,Z_n)$（$Z_i\in\{X,Y\}$）の和になります。$X$ と $Y$ の両方を含む項は <Ref to="thm-independence-cumulants" /> により $0$ で、残るのは全て $X$ の項と全て $Y$ の項です。
</Proof>

> 統計力学や場の理論では、確率変数の積の期待値の代わりに場の相関関数 $E[\varphi(x_1)\cdots\varphi(x_n)]$ を考え、同じ公式で定まるものを**打ち切り相関関数**（Ursell 関数）と呼びます。<Ref to="thm-independence-cumulants" /> は、系が二つの独立な部分に分かれるなら、両方にまたがる打ち切り相関が消える、という事実の組合せ論的な骨格です。

## 7. 束

半順序集合のうち、任意の 2 元に「ちょうど合う上界」と「ちょうど合う下界」がある、という強い性質をもつものを束といいます。ブール束・約数の束・分割束は、どれもこの性質をもちます。この節の $L$ は有限とは限りません。

<Definition id="def-lattice" title="束・完備束・分配束">
半順序集合 $(L,\le)$ の 2 元 $x,y$ の**上限** $x\vee y$ とは、$\{x,y\}$ の上界のうち最小のもの、**下限** $x\wedge y$ とは下界のうち最大のものである。任意の 2 元が上限と下限をもつ半順序集合を**束**という。任意の部分集合が上限をもつ束を**完備束**という（空集合の上限は最小元、$L$ 全体の上限は最大元である。部分集合の下限は、その下界全体の上限として得られる）。束 $L$ が**分配束**であるとは、すべての $x,y,z$ について
$$
x\wedge(y\vee z)=(x\wedge y)\vee(x\wedge z)
$$
が成り立つことをいう。
</Definition>

<Proposition id="prop-lattice-laws" title="束の演算の基本法則">
$L$ を束とする。

1. $\vee,\wedge$ は可換・結合的・冪等で、吸収則 $x\wedge(x\vee y)=x$、$x\vee(x\wedge y)=x$ が成り立つ。
2. $x\le y$ と $x\wedge y=x$ と $x\vee y=y$ は同値である。
3. $L$ が分配束なら、双対の分配則 $x\vee(y\wedge z)=(x\vee y)\wedge(x\vee z)$ も成り立つ。
4. $L$ が分配束で $x\wedge z=y\wedge z$ かつ $x\vee z=y\vee z$ ならば $x=y$ である（相殺律）。
</Proposition>

<Proof of="prop-lattice-laws">
1: 可換性は $\{x,y\}=\{y,x\}$ から明らかです。結合性：$(x\vee y)\vee z$ は $x,y,z$ の上界です（$x,y\le x\vee y\le(x\vee y)\vee z$）。$u$ が $x,y,z$ の上界なら $u\ge x\vee y$ で、したがって $u\ge(x\vee y)\vee z$ です。よって $(x\vee y)\vee z=\sup\{x,y,z\}$ で、同様に $x\vee(y\vee z)=\sup\{x,y,z\}$ です。$\wedge$ も双対です。冪等性は $\sup\{x\}=x$。吸収則：$x$ は $\{x,x\vee y\}$ の下界で、下界は $x$ 以下なので $x\wedge(x\vee y)=x$ です。もう一つも双対です。

2: $x\le y$ なら $x$ は $\{x,y\}$ の最大の下界で $x\wedge y=x$、また $y$ は最小の上界で $x\vee y=y$ です。$x\wedge y=x$ なら $x\le y$、$x\vee y=y$ なら $x\le y$ です。

3: 分配則（$\wedge$ が $\vee$ に分配）を仮定する。
$$
\begin{aligned}
(x\vee y)\wedge(x\vee z)&=\bigl((x\vee y)\wedge x\bigr)\vee\bigl((x\vee y)\wedge z\bigr)&&\text{（分配則）}\\
&=x\vee\bigl((x\wedge z)\vee(y\wedge z)\bigr)&&\text{（吸収則と分配則）}\\
&=\bigl(x\vee(x\wedge z)\bigr)\vee(y\wedge z)=x\vee(y\wedge z)&&\text{（結合性と吸収則）}
\end{aligned}
$$
です。

4: 吸収則と分配則、仮定を順に使うと
$$
x=x\wedge(x\vee z)=x\wedge(y\vee z)=(x\wedge y)\vee(x\wedge z)=(x\wedge y)\vee(y\wedge z)=y\wedge(x\vee z)=y\wedge(y\vee z)=y
$$
です（$y\wedge(x\vee z)=(y\wedge x)\vee(y\wedge z)$ は分配則）。
</Proof>

<Proposition id="prop-finite-lattice" title="最大元と下限があれば束になる">
有限半順序集合 $P$ が最大元 $\hat1$ をもち、任意の 2 元が下限をもつならば、$P$ は束である。とくに、有限集合 $S$ の分割束 $\Pi(S)$ は束で、$\pi\wedge\sigma=\{B\cap C\ne\varnothing:B\in\pi,\ C\in\sigma\}$ である。
</Proposition>

<Proof of="prop-finite-lattice">
$x,y\in P$ に対し、上界の集合 $U$ は $\hat1\in U$ で空でなく有限です。下限は <Ref to="prop-lattice-laws" /> の 1 の結合性の議論（下限の存在しか使わない）により、有限個の元に対して $\bigwedge$ が定まります。ここで $U$ の下限を $m=\bigwedge U$ と定められます。$U$ の各元は $x$ 以上なので $x$ は $U$ の下界で、$x\le m$、同様に $y\le m$ です。したがって $m$ は $x,y$ の上界、すなわち $m\in U$ で、$U$ の最小元（$m\le u$ がすべての $u\in U$ で成り立つ）ですから $m=x\vee y$ です。

分割束：$\pi\wedge\sigma$ の候補 $\rho=\{B\cap C\ne\varnothing\}$ は分割で、$\pi$ と $\sigma$ の細分です。$\tau$ が $\pi$ と $\sigma$ の共通の細分なら、$\tau$ の各ブロック $D$ はある $B\in\pi$ とある $C\in\sigma$ に含まれ、$D\subseteq B\cap C\in\rho$ なので $\tau\le\rho$ です。よって $\rho$ が最大の下界で、最大元は $\hat1=\{S\}$ です。
</Proof>

<Example id="ex-lattices" title="分配束であるものとないもの">
(a) 全順序集合は束で、$x\wedge y=\min$、$x\vee y=\max$ です。$\min(x,\max(y,z))=\max(\min(x,y),\min(x,z))$ は、$y\le z$ の場合と $z\le y$ の場合に分けて確かめられます（$y\le z$ なら左辺は $\min(x,z)$、右辺は $\min(x,y)\le\min(x,z)$ から $\max$ が $\min(x,z)$ になる。$z\le y$ は $y,z$ の入れ替え）。したがって全順序集合は分配束です。束の直積（成分ごとの $\vee,\wedge$）は分配束なので、<Ref to="prop-mobius-boolean-divisor" /> の同型により、ブール束 $B_n$ と約数の束 $D_n$ は分配束です。ブール束では $\vee=\cup$、$\wedge=\cap$ で、分配則は <Ref to="mathematics/foundations/sets-and-logic#thm-distributive" /> そのものです。$D_n$ では $\vee=\mathrm{lcm}$、$\wedge=\gcd$ です。

(b) 分割束 $\Pi(S)$ は、$|S|\ge3$ なら分配束ではありません。相異なる $a,b,c\in S$ をとり、$\alpha=\{a,b\}$ を 1 ブロックとし他は単独のブロックにした分割、同様に $\beta$（$\{a,c\}$）、$\gamma$（$\{b,c\}$）をとります。$\beta\vee\gamma$ は $\{a,b,c\}$ が 1 ブロックの分割で $\alpha\le\beta\vee\gamma$ なので、$\alpha\wedge(\beta\vee\gamma)=\alpha$ です。一方 $\alpha\wedge\beta=\alpha\wedge\gamma=\hat0$ で、$(\alpha\wedge\beta)\vee(\alpha\wedge\gamma)=\hat0\ne\alpha$ です。<Ref to="prop-lattice-laws" /> の 4 も破れています。実際、$\alpha\wedge\gamma=\beta\wedge\gamma=\hat0$ で、$\alpha\vee\gamma=\beta\vee\gamma$（$\{a,b,c\}$ が 1 ブロックの分割）ですが、$\alpha\ne\beta$ です。
</Example>

<Figure caption="分配束でない最小の例（五角形の束 N₅）のハッセ図。0 < a < c < 1 と 0 < b < 1 で、b は a, c と比較できない。c ∧ (a ∨ b) = c だが (c ∧ a) ∨ (c ∧ b) = a で、分配則が破れる（演習の例）。">
<svg viewBox="0 0 300 250" width="100%" role="img" aria-label="五角形の束 N5 のハッセ図">
  <g stroke="currentColor" stroke-width="1.5">
    <line x1="150" y1="200" x2="90" y2="150" /><line x1="90" y1="150" x2="90" y2="90" /><line x1="90" y1="90" x2="150" y2="40" />
    <line x1="150" y1="200" x2="210" y2="120" /><line x1="210" y1="120" x2="150" y2="40" />
  </g>
  <g fill="var(--sl-color-accent)">
    <circle cx="150" cy="200" r="6" /><circle cx="90" cy="150" r="6" /><circle cx="90" cy="90" r="6" /><circle cx="210" cy="120" r="6" /><circle cx="150" cy="40" r="6" />
  </g>
  <g fill="currentColor" font-size="13" text-anchor="middle">
    <text x="150" y="28">1</text>
    <text x="70" y="94">c</text><text x="70" y="154">a</text>
    <text x="232" y="124">b</text>
    <text x="150" y="224">0</text>
  </g>
</svg>
</Figure>

次は、完備束の基本定理です。

<Theorem id="thm-knaster-tarski" title="Knaster–Tarski の不動点定理">
$L$ を完備束、$f:L\to L$ を単調（$x\le y\Rightarrow f(x)\le f(y)$）とする。このとき $f$ は不動点をもち、最小の不動点は $a=\bigwedge\{x\in L:f(x)\le x\}$ である。
</Theorem>

<Proof of="thm-knaster-tarski">
$A=\{x:f(x)\le x\}$ は最大元 $\hat1$ を含むので空でなく、$a=\bigwedge A$ が定まります。$x\in A$ なら $a\le x$ で、単調性から $f(a)\le f(x)\le x$ です。よって $f(a)$ は $A$ の下界で、$f(a)\le a$ です。単調性をもう一度使うと $f(f(a))\le f(a)$ で、$f(a)\in A$ ですから $a\le f(a)$ です。したがって $f(a)=a$ です。$f(x_0)=x_0$ なら $x_0\in A$ なので $a\le x_0$ で、$a$ は最小の不動点です。
</Proof>

たとえば集合 $X$ から $Y$ への単射と $Y$ から $X$ への単射が与えられたとき、$\mathcal{P}(X)$ 上の単調写像の不動点を使って、<Ref to="mathematics/foundations/cardinality-and-infinity#thm-cantor-bernstein" /> を証明する方法が知られています。

束の中には、「無限の極限を有限の近似で捉える」構造をもつものがあります。次の定義の直感は、実数の $[0,1]$ で $y$ に「十分手前から近づける数」$x$（$x\ll y$）を考え、$y$ をそのような数の上限として復元できる、ということです。有限な束では $x\ll y$ は単に $x\le y$ になり、実数の区間や冪集合では例が後の命題 4 にあります。

<Definition id="def-continuous-lattice" title="有向集合・way-below 関係・連続束">
半順序集合 $L$ の空でない部分集合 $D$ が**有向**であるとは、$D$ の任意の 2 元に対して、$D$ の中にその両方の上界があることをいう。完備束 $L$ の元 $x,y$ について、$y\le\sup D$ となるすべての有向集合 $D$ にその元 $d\ge x$ が含まれるとき、$x$ は $y$ の**way-below**であるといい、$x\ll y$ と書く。完備束 $L$ が**連続束**であるとは、すべての $y\in L$ について
$$
y=\sup\{x\in L:x\ll y\}
$$
が成り立つことをいう。
</Definition>

<Proposition id="prop-way-below" title="way-below 関係の性質">
$L$ を完備束とする。

1. $x\ll y$ ならば $x\le y$。また $x'\le x\ll y\le y'$ ならば $x'\ll y'$。
2. $0\ll y$（$0$ は最小元）で、$x_1\ll y$ かつ $x_2\ll y$ ならば $x_1\vee x_2\ll y$。したがって $\{x:x\ll y\}$ は有向集合である。
3. 有限な完備束（有限な束）はすべて連続束であり、そこでは $x\ll y\iff x\le y$ である。
4. $[0,1]$ は連続束で、$y>0$ のとき $x\ll y\iff x<y$ または $x=0$ である。冪集合 $\mathcal{P}(X)$ は連続束で、$A\ll B$ は「$A$ が $B$ の有限部分集合」と同値である。
</Proposition>

<Proof of="prop-way-below">
1: 有向集合 $D=\{y\}$ を取ると $y\le\sup D$ なので $x\le y$ です。後半：$y'\le\sup D$ なら $y\le y'\le\sup D$ なので $x\le d$ となる $d\in D$ があり、$x'\le x\le d$ です。

2: $D$ は空でないので任意の $d\in D$ について $0\le d$、したがって $0\ll y$ です。$y\le\sup D$ とすると、$x_1\le d_1$、$x_2\le d_2$ となる $d_1,d_2\in D$ があり、$D$ の有向性により両方の上界 $d\in D$ があるので $x_1\vee x_2\le d$ です。有向性は $\{x:x\ll y\}$ が空でなく（$0$ を含む）、2 元 $x_1,x_2$ の上界として $x_1\vee x_2$ が取れることから従います。

3: 有限な有向集合 $D$ は最大元をもつ（有限個の元の上界を繰り返し取る）ので $\sup D=\max D\in D$ です。$x\le y\le\sup D=d\in D$ から $x\le d$、すなわち $x\ll y$ です。逆は 1 です。したがって $\sup\{x:x\ll y\}=\sup\{x:x\le y\}=y$ です。

4: $y>0$ とする。$x<y$ とし、$y\le\sup D$ とする。$x<y\le\sup D$ なので $x$ は $D$ の上界でなく、ある $d\in D$ が $x<d$ です。$x=0$ なら $D$ が空でないので $0\le d$ となる $d$ があります。$x=y>0$ は $\ll$ でありません（$D=[0,y)$ は有向で $\sup D=y$ ですが $y\le d$ となる $d$ がない）。よって $\sup\{x:x\ll y\}=\sup([0,y)\cup\{0\})=y$ です。$y=0$ では $0\ll0$ で $\sup=0$ です。$\mathcal{P}(X)$ では、$A$ が $B$ の有限部分集合なら、$B\subseteq\bigcup D$ の有向集合 $D$ について、$A$ の各元を含む $D$ の元をとり、有限個なので有向性で一つの $d\in D$ にまとめられ、$A\subseteq d$ です。逆に $A\ll B$ なら、$B$ の有限部分集合全体 $D$ は有向で $\sup D=B$ なので、$A$ はある有限部分集合に含まれます。$B$ は有限部分集合の和なので連続束です。
</Proof>

<Theorem id="thm-interpolation" title="連続束の補間性質">
$L$ を連続束とする。$x\ll y$ ならば、$x\ll z\ll y$ となる $z\in L$ が存在する。
</Theorem>

<Proof of="thm-interpolation">
$\Downarrow z=\{u:u\ll z\}$ と書く。<Ref to="prop-way-below" /> の 2 より、各 $\Downarrow z$ は有向集合である。$D=\bigcup_{z\ll y}\Downarrow z$ を考える。$D$ は有向である：$u_1\ll z_1\ll y$、$u_2\ll z_2\ll y$ とすると、$\{z:z\ll y\}$ が有向なので $z_1,z_2\le z_3\ll y$ となる $z_3$ があり、1 により $u_1,u_2\ll z_3$ で、$\Downarrow z_3$ が有向なので両方の上界が $\Downarrow z_3\subseteq D$ の中にある。$\sup D$ を見ると、連続性から $\sup\Downarrow z=z$ なので $\sup D=\sup\{z:z\ll y\}=y$ である。$x\ll y\le\sup D$ と $D$ が有向であることから、$x\le u$ となる $u\in D$ があり、$u\ll z\ll y$ となる $z$ がある。1 より $x\le u\ll z$ なので $x\ll z\ll y$ である。
</Proof>

連続束は領域理論（計算の意味論）で、計算可能性を「有限の近似の極限」として捉えるための基本的な枠組みです。

## 8. Dilworth の定理

有限半順序集合の「幅」と「鎖への分割」の関係を調べます。$P$ は有限半順序集合とします。

<Definition id="def-chain-antichain" title="鎖・反鎖・幅">
$P$ の部分集合が**鎖**であるとは、任意の 2 元が比較可能であること、**反鎖**であるとは、相異なる任意の 2 元が比較不能であることをいう。反鎖の元の個数の最大値を $P$ の**幅**といい $w(P)$ と書く。$P$ の**鎖分割**とは、$P$ を互いに素な鎖の和集合として表すことである。
</Definition>

鎖と反鎖は高々 1 点でしか交わりません（2 点が共通なら、比較可能かつ比較不能になる）。したがって $P$ を $k$ 個の鎖に分割すれば、反鎖の元は異なる鎖にあるので $w(P)\le k$ です。逆向きの不等式が Dilworth の定理です。

<Theorem id="thm-dilworth" title="Dilworth の定理">
有限半順序集合 $P$ について、$P$ の鎖分割に必要な鎖の最小個数は、$P$ の幅 $w(P)$ に等しい。
</Theorem>

次の証明の方針は、元の個数に関する帰納法です。極大元 $a$ を一つ取り除いた集合を鎖に分け、$a$ を加えると幅が増えるか（鎖をもう 1 本足す）、増えないか（$a$ を含む鎖を一つ取り出し、残りに帰納法を使う）で場合分けします。

次の動画は、$\{1,\dots,12\}$ の整除関係で、12 本の 1 点の鎖から出発して鎖をつないでいき（比較可能な組を二部グラフの辺とみた最大マッチングを増加路で作る手順）、鎖の本数が最小の 6 本になる様子です。最後に、本数と同じ大きさの反鎖 $\{7,\dots,12\}$ が現れます。

<Figure caption="整除関係の半順序集合 {1,…,12} を鎖に分ける。鎖の本数は 12 から 6 まで減り、最小値は反鎖 {7,…,12} の大きさ（幅）に一致する。">
<img src="/figures/dilworth-chains.gif" alt="1 から 12 の整除関係で、1 点ずつの 12 本の鎖から、比較可能な元をつなぎ替えながら鎖の本数が 12, 11, …, 6 と減っていく。最後に 6 本の鎖と、大きさ 6 の反鎖 7〜12（破線の丸）が示される。" loading="lazy" />
</Figure>

<Proof of="thm-dilworth">
鎖と反鎖は高々 1 点でしか交わらないので、$P$ を $k$ 個の鎖に分割すると、最大の反鎖の元は相異なる鎖に入り、$w(P)\le k$ です。したがって鎖分割の個数は $w(P)$ 以上です。$P$ の元の個数 $|P|$ についての帰納法で、$w(P)$ 個の鎖への分割があることを示します（部分集合は鎖なので、「$k$ 個の鎖で覆える」ことと「$k$ 個以下の互いに素な鎖に分割できる」ことは同値です）。$P=\varnothing$ なら自明です。$P\ne\varnothing$ とし、$a$ を $P$ の極大元（<Ref to="mathematics/foundations/axiom-of-choice-zorn#def-bounds" /> の意味。有限なので存在する）、$P'=P\setminus\{a\}$、$k=w(P')$ とします。$k=0$ なら $P=\{a\}$ で自明です。$k\ge1$ とします。帰納法の仮定で $P'$ は互いに素な $k$ 個の鎖 $C_1,\dots,C_k$ に分割されます。大きさ $k$ の反鎖を **$k$-反鎖**と呼ぶと、$k$-反鎖は各 $C_i$ とちょうど 1 点で交わります（各鎖と高々 1 点、$k$ 個の鎖で全体を覆うので）。$k$-反鎖は存在します（$k=w(P')$）。

各 $i$ について、ある $k$-反鎖に含まれる $C_i$ の元のうち最大のもの $x_i$ を取ります（有限で空でない）。**主張 1：$A=\{x_1,\dots,x_k\}$ は反鎖である。** $x_i\in A_i$、$x_j\in A_j$ を $k$-反鎖とし、$i\ne j$ について $x_i<x_j$ と仮定します。$A_j$ は $C_i$ と 1 点 $z$ で交わり、$x_i$ の最大性から $z\le x_i$ です。すると $z\le x_i<x_j$ で、$z\in C_i$ と $x_j\in C_j$ は（鎖が互いに素なので）相異なる $A_j$ の元で比較可能になり、$A_j$ が反鎖であることに反します。$x_i>x_j$ も同様なので、$x_i,x_j$ は比較不能です。

**場合 1：$a$ が $x_1,\dots,x_k$ のすべてと比較不能。** $A\cup\{a\}$ は大きさ $k+1$ の反鎖なので $w(P)\ge k+1$ で、$C_1,\dots,C_k,\{a\}$ は $k+1\le w(P)$ 個の鎖への分割です。

**場合 2：$a$ がある $x_i$ と比較可能。** $a$ は極大元なので $x_i<a$ です。$K=\{a\}\cup\{y\in C_i:y\le x_i\}$ は鎖です。$P\setminus K$ に大きさ $k$ の反鎖 $B$ があったとすると、$P\setminus K\subseteq P'$ なので $B$ は $k$-反鎖で、$C_i$ との共通点 $y$ は $y\notin K$、すなわち $y>x_i$（$C_i$ は鎖）です。これは $x_i$ の最大性に反します。ゆえに $w(P\setminus K)\le k-1$ で、$|P\setminus K|<|P|$ なので帰納法の仮定により $P\setminus K$ は $k-1$ 個以下の鎖に分割されます。$K$ と合わせて $k$ 個以下の鎖で $P$ を分割できます。$w(P)\ge w(P')=k$ ですから、これは $w(P)$ 個以下です。

いずれの場合も $w(P)$ 個以下の鎖への分割が得られました。
</Proof>

双対の事実は、より簡単に示せます。

<Proposition id="prop-mirsky" title="Mirsky の定理（反鎖への分割）">
有限半順序集合 $P$ の最長の鎖の元の個数を $h$ とする。$P$ は $h$ 個の反鎖に分割でき、$h$ 個より少ない反鎖には分割できない。
</Proposition>

<Proof of="prop-mirsky">
$x\in P$ に対し、$x$ を最大元とする鎖の元の個数の最大値を $\ell(x)\in\{1,\dots,h\}$ とします。$\ell(x)=\ell(y)=j$ かつ $x<y$ なら、$x$ を最大元とする長さ $j$ の鎖に $y$ を付け足して $y$ を最大元とする長さ $j+1$ の鎖ができ、$\ell(y)\ge j+1$ で矛盾します。したがって各 $\ell^{-1}(j)$ は反鎖で、$P=\bigsqcup_{j=1}^h\ell^{-1}(j)$ です。長さ $h$ の鎖は各反鎖と高々 1 点で交わるので、$h$ 個より少ない反鎖では覆えません。
</Proof>

<Corollary id="cor-erdos-szekeres" title="Erdős–Szekeres の定理">
相異なる実数からなる長さ $rs+1$ の列 $a_1,\dots,a_{rs+1}$ は、長さ $r+1$ の増加部分列か、長さ $s+1$ の減少部分列をもつ。
</Corollary>

<Proof of="cor-erdos-szekeres">
添字の集合 $P=\{1,\dots,rs+1\}$ に、$i\preceq j\iff i\le j$ かつ $a_i\le a_j$ で順序を入れます（半順序）。鎖は増加部分列、反鎖は減少部分列です（$i<j$ で比較不能とは $a_i>a_j$）。長さ $r+1$ の増加部分列がないとすると、鎖の大きさはすべて $r$ 以下です。このとき <Ref to="thm-dilworth" /> により $w(P)$ 個の鎖に分割され、$|P|\le r\,w(P)$ から $w(P)\ge(rs+1)/r>s$、すなわち $w(P)\ge s+1$ です。大きさ $s+1$ の反鎖は長さ $s+1$ の減少部分列です。
</Proof>

<Example id="ex-dilworth-divisibility" title="1 から 2n までの整除関係">
$P=\{1,\dots,2n\}$ を整除で順序づけます。奇数 $m$ ごとに $\{m,2m,4m,\dots\}$ は鎖で、$n$ 個の鎖が $P$ を分割するので、<Ref to="thm-dilworth" /> の易しい側の不等式から $w(P)\le n$ です。$\{n+1,\dots,2n\}$ は反鎖（どの 2 元も整除関係にない）なので $w(P)=n$ です。したがって、$\{1,\dots,2n\}$ から $n+1$ 個の数を選ぶと、どれかが別のどれかを割り切ります。同じ結論は、鎖の分割に対する鳩の巣原理だけでも出ます。
</Example>

## 9. Whitney 数

束や半順序集合のうち、「階数」をもつものについて、元の個数と Möbius 関数の値を階数ごとに集計した数列を考えます。

<Definition id="def-whitney" title="階数付き半順序集合と Whitney 数">
最小元 $\hat0$ をもつ有限半順序集合 $P$ が**階数付き**であるとは、関数 $\rho:P\to\{0,1,2,\dots\}$ で $\rho(\hat0)=0$ かつ「$y$ が $x$ を被覆する（$x<y$ で $x<z<y$ となる $z$ がない）なら $\rho(y)=\rho(x)+1$」を満たすものがあることをいう。このとき
$$
W_k=\#\{x\in P:\rho(x)=k\},\qquad w_k=\sum_{x:\ \rho(x)=k}\mu(\hat0,x)
$$
をそれぞれ**第 2 種**、**第 1 種の Whitney 数**という。
</Definition>

<Example id="ex-whitney-boolean" title="ブール束の Whitney 数">
$B_n$ では $\rho(S)=|S|$ で、<Ref to="prop-mobius-boolean-divisor" /> の $\mu(\varnothing,S)=(-1)^{|S|}$ から $W_k=\binom nk$、$w_k=(-1)^k\binom nk$ です。$\sum_kw_k=(1-1)^n=0$ は $\sum_{x}\mu(\hat0,x)=\delta(\hat0,\hat1)=0$（<Ref to="def-mobius-function" />）の例です。
</Example>

分割束 $\Pi_n$ の Whitney 数は、有名な数と一致します。$S(n,m)$ を $[n]$ の $m$ ブロックへの分割の個数（第 2 種 Stirling 数、<Ref to="ex-ie-applications" /> の (c)）、$c(n,m)$ を $[n]$ の置換のうちちょうど $m$ 個の巡回置換（サイクル）の積に分解されるものの個数（符号なし第 1 種 Stirling 数）とします。

<Lemma id="lem-partition-graded" title="分割束は階数付き">
$\Pi_n$ は $\rho(\pi)=n-|\pi|$ で階数付きである。
</Lemma>

<Proof of="lem-partition-graded">
$\rho(\hat0)=n-n=0$ です。$\pi<\sigma$ なら、$\sigma$ のあるブロックは $\pi$ の 2 個以上のブロックの和なので、その中の 2 ブロックを併合した分割 $\tau$ について $\pi<\tau\le\sigma$ です。したがって $\sigma$ が $\pi$ を被覆するなら $\sigma=\tau$、つまり被覆は「2 ブロックの併合」だけで、ブロック数がちょうど 1 減るので $\rho$ はちょうど 1 増えます。
</Proof>

<Proposition id="prop-whitney-partition" title="分割束の Whitney 数">
$\Pi_n$ の Whitney 数は、$W_k=S(n,n-k)$、$w_k=(-1)^k\,c(n,n-k)$ である。
</Proposition>

<Proof of="prop-whitney-partition">
$W_k$ は $\rho(\pi)=k$、すなわち $|\pi|=n-k$ の分割の個数で、定義から $S(n,n-k)$ です。$w_k$ は、<Ref to="thm-partition-mobius" /> により
$$
w_k=\sum_{|\pi|=m}\ \prod_{B\in\pi}(-1)^{|B|-1}(|B|-1)!=(-1)^{n-m}\sum_{|\pi|=m}\ \prod_{B\in\pi}(|B|-1)!\qquad(m=n-k)
$$
です（$\sum_B(|B|-1)=n-m$）。$b$ 元集合の上の巡回置換（長さ $b$ のサイクル 1 つ）の個数は、最小の元から始めて残り $b-1$ 個の元の並べ方を決めればよいので $(b-1)!$ です。置換は、軌道への分割 $\pi$ と、各ブロック上の巡回置換の組を与えれば決まり、その逆も成り立ちます。したがって $\sum_{|\pi|=m}\prod_B(|B|-1)!$ は、ちょうど $m$ 個のサイクルをもつ置換の個数 $c(n,m)$ です。$(-1)^{n-m}=(-1)^k$ から主張を得ます。
</Proof>

<Proposition id="prop-stirling-first-gf" title="第 1 種 Stirling 数の母関数">
$\displaystyle\sum_{m=1}^nc(n,m)\,x^m=x(x+1)(x+2)\cdots(x+n-1)$。したがって
$$
\sum_{\pi\in\Pi_n}\mu(\hat0,\pi)\,x^{|\pi|}=x(x-1)(x-2)\cdots(x-n+1).
$$
</Proposition>

証明の方針は、$[n]$ の置換に新しい元 $n+1$ を付け加える方法を数えて、$c(n+1,m)$ を $c(n,m)$ と $c(n,m-1)$ で表す漸化式を作ることです。たとえば $n=2$ では、置換 $(1)(2)$ と $(12)$ のそれぞれについて、$3$ を単独のサイクルにする方法 1 通りと、元 $1$ か $2$ の直後に入れる方法 2 通りがあり、合わせて $2\times3=6$ 個の $[3]$ の置換が得られます。

<Proof of="prop-stirling-first-gf">
$n$ についての帰納法で前半を示します。$n=1$ は $c(1,1)=1$ です。$[n+1]$ の置換で $m$ 個のサイクルをもつものを、元 $n+1$ に注目して分類します。$n+1$ が不動点（長さ 1 のサイクル）なら、残りは $[n]$ の置換でサイクルが $m-1$ 個。そうでなければ、$n+1$ を除いた（$n+1$ の前の元の像を $n+1$ の像に直す）$[n]$ の置換でサイクルは $m$ 個で、逆に $[n]$ の置換と「$n+1$ をどの元 $i\in[n]$ の直後に挿入するか」の $n$ 通りから元に戻ります。よって $c(n+1,m)=c(n,m-1)+n\,c(n,m)$ で、母関数は $x\cdot\prod_{j=0}^{n-1}(x+j)+n\prod_{j=0}^{n-1}(x+j)=\prod_{j=0}^{n}(x+j)$ です。後半は <Ref to="prop-whitney-partition" /> から $\sum_\pi\mu(\hat0,\pi)x^{|\pi|}=\sum_m(-1)^{n-m}c(n,m)x^m=(-1)^n\prod_{j=0}^{n-1}(-x+j)=\prod_{j=0}^{n-1}(x-j)$ です。
</Proof>

後半の多項式は、完全グラフ $K_n$ の頂点を $x$ 色で塗り分ける（隣り合う頂点が同じ色にならない）方法の数でもあります。さらに、前章（[数え上げと母関数](/mathematics/combinatorics/enumeration-generating-functions)）で示したように、実根だけをもつ多項式の係数は対数凹で、とくに単峰です。$\prod_j(x+j)$ の根は $0,-1,\dots,-(n-1)$ で実数なので、$c(n,1),c(n,2),\dots,c(n,n)$ は単峰、すなわち Whitney 数 $|w_k|$ は階数 $k$ について単峰です（<Ref to="mathematics/combinatorics/enumeration-generating-functions#thm-newton-unimodal" />）。

## 10. 演習

<Exercise id="exr-pi4" difficulty="標準">
$\Pi_4$ の全ての分割について $\mu(\hat0,\pi)$ の総和を計算することで、$\mu(\hat0,\hat1)=-6$ を直接確かめよ。
<Solution>
$\Pi_4$ の分割の型は、$(4)$ が 1 個、$(3,1)$ が 4 個、$(2,2)$ が 3 個、$(2,1,1)$ が 6 個、$(1,1,1,1)$ が 1 個の計 15 個です。<Ref to="prop-partition-interval" /> と <Ref to="prop-mobius-product" /> より $\mu(\hat0,\pi)=\prod_Bm_{|B|}$ で、$m_1=1$、$m_2=-1$、$m_3=2$ です。型ごとの値は $(3,1)$: $m_3m_1=2$、$(2,2)$: $m_2^2=1$、$(2,1,1)$: $m_2=-1$、$(1,1,1,1)$: $1$。総和が $0$ なので $m_4+4\cdot2+3\cdot1+6\cdot(-1)+1=0$、すなわち $m_4=-6=(-1)^3\,3!$ です。
</Solution>
</Exercise>

<Exercise id="exr-surjection" difficulty="易">
<Ref to="ex-ie-applications" /> の (c) を使って、$[5]$ から $[3]$ への全射の個数と第 2 種 Stirling 数 $S(5,3)$ を求めよ。
<Solution>
全射の個数は $3^5-3\cdot2^5+3\cdot1^5-0=243-96+3=150$ です（$j=3$ の項は $0^5=0$）。$S(5,3)=150/3!=25$ です。
</Solution>
</Exercise>

<Exercise id="exr-euler-phi" difficulty="標準">
$n=\sum_{d\mid n}\varphi(d)$ が成り立つ（$1$ から $n$ の整数を $\gcd(k,n)$ で分類する）ことを使い、約数の束 $D_n$ の Möbius 反転で $\varphi(n)=\sum_{d\mid n}\mu_{\mathbb N}(d)\,\frac nd$ を導け。これを使って $\varphi(12)$ を求めよ。
<Solution>
$g(m)=m$、$f(d)=\varphi(d)$ は $D_n$ 上で $g(m)=\sum_{d\mid m}f(d)$ を満たすので、<Ref to="thm-mobius-inversion" /> の 1 と <Ref to="prop-mobius-boolean-divisor" /> の $\mu(d,m)=\mu_{\mathbb N}(m/d)$ から $\varphi(n)=\sum_{d\mid n}\mu_{\mathbb N}(n/d)\,d=\sum_{d\mid n}\mu_{\mathbb N}(d)\,\frac nd$ です。$n=12$ では約数 $1,2,3,4,6,12$ のうち $\mu_{\mathbb N}\neq0$ は $1,2,3,6$（値 $1,-1,-1,1$）で、$12-6-4+2=4$ です。
</Solution>
</Exercise>

<Exercise id="exr-bernoulli-cumulant" difficulty="標準">
$P(X=1)=p$、$P(X=0)=1-p$ の Bernoulli 変数について、$\kappa_1,\kappa_2,\kappa_3$ を求めよ。
<Solution>
$X^k=X$ なので $m_k=p$ です。$\kappa_1=p$、$\kappa_2=m_2-m_1^2=p-p^2$。<Ref to="ex-cumulants-low" /> の式で全て同じ変数なら $\kappa_3=m_3-3m_2m_1+2m_1^3=p-3p^2+2p^3=p(1-p)(1-2p)$ です。
</Solution>
</Exercise>

<Exercise id="exr-n5-lattice" difficulty="易">
$L=\{0,a,b,c,1\}$ を、$0<a<c<1$、$0<b<1$ で $b$ は $a,c$ と比較不能な半順序集合とする。$L$ は束だが分配束ではないことを示せ。
<Solution>
$L$ の 2 元の上限・下限は、比較可能なら大きい方・小さい方、比較不能な組 $\{a,b\},\{c,b\}$ では $a\vee b=c\vee b=1$、$a\wedge b=c\wedge b=0$ です。したがって束です。$c\wedge(a\vee b)=c\wedge1=c$ ですが、$(c\wedge a)\vee(c\wedge b)=a\vee0=a\ne c$ なので分配則が破れます。<Ref to="prop-lattice-laws" /> の 4 も、$a\wedge b=c\wedge b$ かつ $a\vee b=c\vee b$ なのに $a\ne c$ で破れています。
</Solution>
</Exercise>

<Exercise id="exr-dilworth-grid" difficulty="標準">
$P=\{1,\dots,m\}\times\{1,\dots,n\}$（$m\le n$）に成分ごとの順序（$(i,j)\le(i',j')\iff i\le i'$ かつ $j\le j'$）を入れる。$w(P)=m$ であることを示し、$m$ 個の鎖への分割を具体的に与えよ。
<Solution>
行 $R_i=\{i\}\times\{1,\dots,n\}$ は鎖で、$P=R_1\sqcup\cdots\sqcup R_m$ は $m$ 個の鎖への分割です。したがって反鎖の大きさは $m$ 以下です（鎖と反鎖は高々 1 点で交わる）。一方 $\{(i,m+1-i):1\le i\le m\}$ は反鎖です（$i<i'$ なら第 1 成分は増え第 2 成分は減る）ので $w(P)=m$ です。これは <Ref to="thm-dilworth" /> が保証する、鎖の最小個数と幅の一致の例です。
</Solution>
</Exercise>

<Exercise id="exr-whitney-pi4" difficulty="標準">
$\Pi_4$ の Whitney 数 $W_k$、$w_k$（$k=0,1,2,3$）を求め、$\sum_kw_k=0$ と $w_3=\mu(\hat0,\hat1)=-6$ を確かめよ。
<Solution>
<Ref to="prop-whitney-partition" /> より $W_k=S(4,4-k)$ で、$S(4,4)=1$、$S(4,3)=6$、$S(4,2)=7$、$S(4,1)=1$ なので $(W_0,\dots,W_3)=(1,6,7,1)$ です（合計は $\Pi_4$ の元の数 $15$）。$c(4,m)$ は $x(x+1)(x+2)(x+3)=x^4+6x^3+11x^2+6x$ の係数なので（<Ref to="prop-stirling-first-gf" />）$c(4,4)=1$、$c(4,3)=6$、$c(4,2)=11$、$c(4,1)=6$ で、$(w_0,\dots,w_3)=(1,-6,11,-6)$ です。和は $1-6+11-6=0$、$w_3=\mu(\hat0,\hat1)=-6$ は <Ref to="exr-pi4" /> の結果と一致します。
</Solution>
</Exercise>

## 参考文献

- Richard P. Stanley, *Enumerative Combinatorics, Volume 1*, 2nd edition, Cambridge University Press, 2012 — 第 3 章（半順序集合、束、Whitney 数）、第 2 章（包除原理）。
- B. A. Davey and H. A. Priestley, *Introduction to Lattices and Order*, 2nd edition, Cambridge University Press, 2002 — 第 2 章（束）、第 4 章（完備束と Tarski の定理）。
- R. P. Dilworth, "A decomposition theorem for partially ordered sets", *Annals of Mathematics* 51 (1950), 161–166.
- G. Gierz et al., *Continuous Lattices and Domains*, Cambridge University Press, 2003 — 第 I 章（連続束と way-below 関係）。
- Gian-Carlo Rota, "On the foundations of combinatorial theory I. Theory of Möbius functions", *Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete* 2 (1964), 340–368.
- Terence P. Speed, "Cumulants and partition lattices", *Australian Journal of Statistics* 25 (1983), 378–388.
- Alexandru Nica, Roland Speicher, *Lectures on the Combinatorics of Free Probability*, Cambridge University Press, 2006 — 第 2 章（分割束とキュムラント）。
- Peter J. Cameron, *Combinatorics: Topics, Techniques, Algorithms*, Cambridge University Press, 1994.