\(N\)次元超平面配置の問題 Part 1の続きです．
1 ザスラフスキー(Zaslavsky)の定理に基づく計算
前回の解法では(1)の最大値を漸化式によるゴリゴリ計算で初等的に求めましたが，実は束論を用いるとよりエレガントに証明できます．更に，二項係数の和が出てくる必然性が高次元でも説明できるようになります．Zaslavskyの定理[1] と呼ばれる次の事実を使います．
Theorem 1. \(\mathbb{R}^N\)内の有限個の超平面の集合\(\mathcal{A}\)によって分割されてできる領域の個数\(N(\mathcal{A})\)は， \[N(\mathcal{A})= \sum_{x\in L(\mathcal{A})}|\mu(0,x)|\] により計算できる．ここで，\(L(\mathcal{A})\)は\(\mathcal{A}\)のいくつかの元の共通部分として得られる\(\mathbb{R}^N\)の空でない部分集合全体に，包含関係と反対の順序，すなわち\(x\subset y\Longleftrightarrow y\leq x\)となる順序\(\leq\)を入れてできる半順序集合を表し，\(\mu\)は\(L(\mathcal{A})\)上のメビウス関数を表す．
\(L(\mathcal{A})\)は任意の2元集合に最大下界が存在するという性質をもちます．このような性質をもつ半順序集合を「交わり半束」(meet-semilattice)といいます．束論には「結び」\(\lor\)（順序に関する最小上界）と「交わり」\(\land\)（順序に関する最大下界）と呼ばれる演算が登場しますが，\(L(\mathcal{A})\)の場合は包含関係ではなくその反対（双対順序）を順序として考えているがゆえに，「交わり」がその言葉とは裏腹に集合としての共通部分ではなくなるので注意してください． \[x\lor y=x\cap y,\quad x\land y=\bigcap\{z\in L(\mathcal{A})\mid x\cup y\subset z\}\] のように，むしろ「結び」の方が集合としての共通部分になります．もう一点注意として，\(\mathbb{R}^N\)自体も「0個の元の共通部分」として解釈され，\(L(\mathcal{A})\)に属します．順序の定め方から，\(L(\mathcal{A})\)の最小元は全空間\(\mathbb{R}^N\)になります．交わり半束の最小元はよく\(0\)と書かれるので，今の状況では\(0=\mathbb{R}^N\)です．
一般に，交わり半束\(L\)上のメビウス関数\(\mu:L\times L\to \mathbb{Z}\)は \[\mu(x,y)=\begin{cases} 1& (x=y) \\ -\sum_{z:x\leq z< y}\mu(x,z) & (x<y) \\ 0& (\text{otherwise})\end{cases}\] を満たすものとして定義され，この性質により一意に決まります．\(x<y\)の場合の式は漸化式のような役割をし，これを用いて\(\mu(0,z)\)の値を\(z\)が小さい方から求めていくことができます．具体的な結果として，順序に関する帰納法により，次が分かります．
Proposition 2. \(L\)が束であるとき，\(L\)上のメビウス関数\(\mu\)と任意の\(z\in L\)に対し， \[\mu(0,z)=\sum_{S\in\mathcal{S}_z}(-1)^{|S|}\] が成り立つ．ここで，\(\mathcal{S}_z\)は，\(a\leq z\)を満たすatom \(a\)からなる\(L\)の部分集合\(S\)であって\(\vee S=z\)を満たすもの全体からなる集合を表し，\(|S|\)は集合\(S\)の要素の個数を表す．
一般の有限な交わり半束\(L\)における「atom」の定義は次の通りです．
Definition 3. \(x\)が\(L\)の極小元のとき\(\operatorname{rank}x=0\)とし，\(x,y\in P\)に対し，\(x<z<y\)となるような\(z\in P\)が存在せず，かつ\(x<y\)が成り立つとき，\(\operatorname{rank}y= \operatorname{rank}x+1\)とすることで，\(\operatorname{rank}:L\to\mathbb{Z}\)を定める．\(\operatorname{rank} a=1\)であるとき，\(a\in L\)はatomであるという．
要するに，あと一歩で極小元なのにギリギリ極小元ではないものがatomです．\(L(\mathcal{A})\)の場合はちょうど\(\mathcal{A}\)がatom全体の集合に一致します．すなわち，配置されている超平面がatomです．
\(\mathcal{A}\)が一般の位置にある超平面配置の場合，各\(z\in L(\mathcal{A})\)に対し，\(z\)を含むatomの組み合わせで共通部分がちょうど\(z\)に一致するものは高々1通りしかありません．よって， \[\mu(0,z)=\sum_{S\in\mathcal{S}_z}(-1)^{|S|}=\pm 1\] が成り立ちます．よって，Zaslavskyの定理より， \[N(\mathcal{A})= \sum_{x\in L(\mathcal{A})}|\mu(0,x)|= \sum_{x\in L(\mathcal{A})}1=| L(\mathcal{A})|\] です．一般の位置にあるという仮定より，\(L(\mathcal{A})\)のうち，\(N-k\)次元の集合は，ちょうど\(k\)個の超平面を\(\mathcal{A}\)から選ぶことで決まるから，\({_{|\mathcal{A}|}}C_k\)個あります．ゆえに， \[N(\mathcal{A})= | L(\mathcal{A})|=\sum_{k=0}^N {_{|\mathcal{A}|}}C_k.\] 先程の初等的な解法における考察と同様にして，できる領域の数が最大になるのは超平面が一般の位置にあるときであることが分かります．よって，これが求める最大値です．
2次元の場合と同様に，できる領域の個数は超平面同士がどのように交差するかによって決まり，答えに現れる二項係数は超平面の選び方の数に対応していたというわけです．
かなり数学的に高度な内容だったと思いますが，いかがだったでしょうか．交わり半束と呼ばれる数学的構造を考えることで二項係数が出てくる必然性が分かりました．素朴な問題を抽象化して捉えると，思ってもみなかった数学的な構造が背後に現れることがあります．深い背景がある問題が大学入試に出題されるとワクワクしますね．
References
[1] T. Zaslavsky, “Facing up to Arrangements: Face-Count Formulas for Partitions of Space by Hyperplanes,” AMS Memoirs 1, no. 154, 1975.
