【組合せ論】メビウスの反転公式6　「(応用例)包除原理/オイラーの多面体定理」

前々回、poset におけるメビウスの反転公式を証明しました。

(前々回の記事に関しては下にあるリンクをご利用ください。)

前回は応用例として古典的なメビウスの反転公式と差分と和分の関係を紹介しました。

今回は包除原理(inclusion-exclusion principle)の証明を前半で行い、後半でオイラーの多面体定理との関連を紹介したいと思います。

※多面体定理に関してはメビウスの反転公式と初等数学を組み合わせて証明をしようと試みたのですが上手くいかなかったので、関連の紹介にとどめてあります。予めご了承ください。

math-topology.hatenablog.com

包除原理
オイラーの多面体定理（の気持ち）
参考文献
おわりに

まずはメビウスの反転公式の確認です。

定理(メビウスの反転公式)

$P$ を Poset とする。

任意の $P$ の元 $t$ に対して $P$ の部分集合 $I_{t}=\{ s\in P | s\le t \}$ が有限集合であるとする。(このとき特に $P$ は locally finite poset になります。)

このとき $P$ 上の関数 $f,g: P\longrightarrow \mathbb{C}$ について、以下の条件(1)(2)は同値である。

(1) 任意の $x\in P$ について、 $g(x)=\displaystyle\sum_{y\le x}f(y)$ となる。

(2) 任意の $x\in P$ について、 $f(x)=\displaystyle\sum_{y\le x}g(y)\mu (y,x)$ となる。　

包除原理

$n$ を $2$ 以上の自然数とします。

有限集合 $S_{1}$ , $S_{2}$ ,… $S_{n}$ に対して，和集合 $S_{1}\cup S_{2}\cup\dots\cup S_{n}$ の部分集合族 $P$ を $S=S_{1}\cup S_{2}\cup\dots\cup S_{n}$ と「 $S_{1}$ , $S_{2}$ ,… $S_{n}$ から作り得るすべての共通部分つまり

$S_{ k_{1} }\cap S_{ k_{2} }\cap\dots\cap S_{ k_{i} }$ $( 1\le i\le n , 1\le k_{1}\lt k_{2} \lt \cdots \le k_{i} \le n )$

で表される部分集合たち」と包含関係からなる poset とします。*1

前回と同じく、

① 公式が使える poset かどうかを確認する。

② Möbius function を求める。

③ 公式を適用する。

をという流れに沿って見ていこうと思います。

まず $P$ の元(要素)の個数は $2^{n} \left( =\displaystyle\sum_{1\le i\le n} \binom{n}{i} +1\right)$ 個となるため、①特に finite poset となりますので、メビウスの反転公式が使えます。

次に Möbius function を求めましょう。

$i$ を $1$ 以上の自然数とします。

$\mu ( S_{ k_{1} }\cap S_{ k_{2} }\cap\dots\cap S_{ k_{i+1} }, S_{ k_{1} }\cap S_{ k_{2} }\cap\dots\cap S_{ k_{i} } )$

$=-\mu( S_{ k_{1} }\cap S_{ k_{2} }\cap\dots\cap S_{ k_{i+1} }, S_{ k_{1} }\cap S_{ k_{2} }\cap\dots\cap S_{ k_{i+1} } )$

$=-1$

となります。

( $i=0$ のとき， $S_{ k_{i+1} }, S_{ k_{1} }\cap S_{ k_{2} }\cap\dots\cap S_{ k_{i} }=S$ と約束すると $i=0$ のときも成立します。)

ここで， $m$ 以下の任意の自然数 $l$ に対して

$\mu ( S_{ k_{1} }\cap S_{ k_{2} }\cap\dots\cap S_{ k_{i+l} }, S_{ k_{1} }\cap S_{ k_{2} }\cap\dots\cap S_{ k_{i} } )=(-1)^{l}$

が成り立つと仮定します。*2

この仮定の下で、

$\mu ( S_{ k_{1} }\cap S_{ k_{2} }\cap\dots\cap S_{ k_{i+m+1} }, S_{ k_{1} }\cap S_{ k_{2} }\cap\dots\cap S_{ k_{i} } )$

$\displaystyle =- \left( \binom{m+1}{0}+(-1)^{1}\binom{m+1}{1}+\cdots +(-1)^{m}\binom{m+1}{m} \right)$ *3

$= -\{ 1+(-1) \}^{m+1} +(-1)^{m+1}$

$= (-1)^{m+1}$

となるため、

すべての自然数 $m$ に対して

$\mu ( S_{ k_{1} }\cap S_{ k_{2} }\cap\dots\cap S_{ k_{i+m} }, S_{ k_{1} }\cap S_{ k_{2} }\cap\dots\cap S_{ k_{i} } )=(-1)^{m}$

が成り立ちます。

②特に

$\mu ( S_{ k_{1} }\cap S_{ k_{2} }\cap\dots\cap S_{ k_{m} }, S )=(-1)^{m}$

となります。

これで準備完了です。

$P$ 上の関数 $f$ , $g$ を次のように定義します。

$T\in P$ について

$f(T)= | \{ x\in T \, | \, \forall T' \lt T ，x\notin T' \} |$ 　( $|X|$ は有限集合 $X$ の元の個数を表します。) *4

$g(T)=|T|$

これらの定義から、任意の $T\in P$ について

$g(T)=\displaystyle\sum_{U\le T} f(U)$

となります。

この等式は集合の元の個数を次のように数えていることを数式に落としているものです。

f:id:kfukui-math7:20201220111009p:plain — (それぞれの数は各集合の元の個数を表します。)

たとえば $7+4+6+1=18$ より上に位置する赤い集合の要素の個数は $18$ 個ですね。

それでは、③メビウスの反転公式を適用してみましょう。

メビウスの反転公式により、任意の $T\in P$ について

$f(T)=\displaystyle\sum_{U\le T} g(U)\mu (U,T)$

が成り立ち、特に

$f(S)=\displaystyle\sum_{U\le S} g(U)\mu (U,S)$

すなわち

$0=\displaystyle\sum_{U\le S} g(U)\mu (U,S)$

から

$g(S)= -\displaystyle\sum_{U\lt S} g(U)\mu (U,S)$

となります。

右辺の $g(U)$ の各係数は Möbius function の値と正負の符号が逆転することに気を付けると

$|S|= \displaystyle\sum_{1\le i \le n ，1\le k_{1}\lt k_{2} \lt \cdots \le k_{i} \le n} (-1)^{i-1}|S_{ k_{1} }\cap S_{ k_{2} }\cap\dots\cap S_{ k_{i} }|$

が成り立ちます。

やや見づらいですね。

共通部分をとる数の偶奇によって係数が $1$ か $-1$ かが決まる、というイメージです。

さらに具体例を見てみましょう。

$n=2$ のとき、

$|S_{1}\cup S_{2}|=|S_{1}|+|S_{2}|-|S_{1}\cap S_{2}|$

$n=3$ のとき

$|S_{1}\cup S_{2}\cup S_{3}|=|S_{1}|+|S_{2}|+|S_{3}|-|S_{1}\cap S_{2}|-|S_{2}\cap S_{3}|-|S_{3}\cap S_{1}|+ |S_{1}\cap S_{2}\cap S_{3}|$

となります。

これはまさに高校数学で学ぶ公式に他なりません。

オイラーの多面体定理（の気持ち）

※「気持ち」なので定義等はゆるめに紹介します。

3次元凸多面体 $K$ に対して「頂点」「辺」「面」の集まりに、任意の元よりも小さい「最小元 $0$ 」と任意の元よりも大きい「最大元 $K$ 」を付加した poset を考えます。

Möbius function $\mu$ を計算しましょう。

任意の頂点 $v$ 、辺 $e$ 、面 $f$ を与えます。

まず

$\mu (0,v)=-\mu(0,0)=-1$

となります。

$e$ は2つの頂点が含まれるので、その頂点の1つを $v$ とすると

$\mu (0,e)=-\mu(0,0)-2\mu (0,v)=1$

となります。

$f$ が $N(f)$ 角形であるとすると、 $f$ には $N(f)$ 個の頂点と辺が含まれます。したがって含まれる頂点の1つを $v$ 、辺の1つを $e$ とすると

$\mu (0,f)=-\mu(0,0)-N(f)\mu (0,v)-N(f)\mu(0,e)=-1$

となります。

最後に $\mu (0,K)$ を定義するのですが、 $K$ には任意の頂点、辺、面が含まれます。(もちろん最小元 $0$ も含まれます。)

したがって頂点の個数を $V$ 、辺の個数を $E$ 、面の個数を $F$ とすると

$\mu(0,K)=-\mu (0,0)-V\mu (0,v) -E\mu (0,e) -F\mu (0,f)$

すなわち

$\mu(0,K)=-1+V -E +F$

となります。

この交代和こそ高校数学の「オイラーの多面体定理」に出てくるものです。

つまりオイラーの多面体定理は次のように言いかえることが出来ますね。

定理(オイラーの多面体定理)

任意の3次元凸多面体 $K$ について $\mu(0,K)=1$ が成り立つ。

ちなみにメビウスの反転公式は次のように絡めることが出来ます。

この poset 上の関数 $\psi$ と $g$ を

Kronecker の $\delta$ 関数を用いて $\psi (x)= \delta (0,x)$

つまり $x=0$ のときのみ $1$ でそれ以外のとき $0$ となる関数を $\psi$ とし、また $g$ を恒等的に $1$ をとる関数とします。

すると

$g(x)=\displaystyle\sum_{y\le x}\psi (y)$

となります。

したがってメビウスの反転公式により

$\psi (x) =\displaystyle\sum_{y\le x} g(y)\mu (y,x)$

特に $x=K$ とすると

$0 =\displaystyle\sum_{y\le K} g(y)\mu (y,K)$

となります。

冗長になるので省略しますが、頂点や辺に集まる面の個数にも注目しながら計算すると

$\mu (f,K)=-1$

$\mu (e,K)=1$

$\mu (v,K)=-1$

となります。

よって先ほどの等式

$0 =\displaystyle\sum_{y\le K} g(y)\mu (y,K)$

は次のように書きかえられます。

$0=\mu (0,K) -V+E-F+1$

ここからも先ほどのオイラーの多面体の定理の主張も得られます。

さて、証明を展開するのは本シリーズの狙いから大きく逸脱してしまうので、今回は行いませんが、機会があれば紹介したいですね…。

補足としては $\mu(0,K)$ を多面体 $K$ の Euler characteristic と定義したとき、 $K$ を3次元ユークリッド空間の部分空間と見たときの Euler characteristic と一致します。このことは参考文献 [Lei] を参照してもらうとよい*5かと思います。