組合せ数学の雑記帳、第1回の話題は超平面配置における領域の個数でした。
$d$次元ユークリッド空間において、超平面は空間を2つの領域に切り分けます。 （超平面というのは、2次元空間においては直線、3次元空間においては平面、 $d$次元空間においては$(d-1)$次元アフィン部分空間、のことです。） 超平面が複数枚あると、もっと細かく、多くの領域に切り分けられます。 $d$次元空間に$n$枚の超平面があったら、この切り分けられる領域の個数はいくつになるか？ というのが この回の題材でした。
もちろん、超平面がどのように配置されているかで領域数は変わります。 例えば、2次元空間に3本の直線（＝3つの超平面）がある場合、配置によって次のようなケースがあります。 順に、4個、6個、6個、7個、に切り分けられています。
ここで、最大いくつに切り分けられるか、を考えることにしましょう。2次元で3本の直線の場合は 切り分けられる領域の最大個数は7個です。$d$次元空間をn個の超平面で切り分ける場合の最大個数を$f_d(n)$とします。
$d$次元空間に$n$個の超平面がある場合、その切り分ける最大数は、超平面の配置が一般の位置にある場合である （一般の位置にありさえすればどんな配置でも同じ個数に切り分けられる）こと、また、 その個数は$n$個の超平面を1枚ずつ加えていくプロセスを考えることにより、漸化式で記述できることが 観察されます。（ここではこの「一般の位置」の意味についての詳細は省きます。） 漸化式は $$ f_d(n) = f_d(n-1) + f_{d-1}(n-1) $$ という形になります。（初項は$f_d(0)=1$と$f_1(n)=n+1$.)
この漸化式を解くと、この領域の最大個数は次の式で与えられることが導かれます。
$$f_d(n)=\binom{n}{d}+\binom{n}{d+1}+\dotsc +\binom{n}{1}+\binom{n}{0}$$
これは、シュレフリ（L. Schläfli）が1901年に与えている公式です。
第1回の内容は、2次元、3次元というところで漸化式を導いてそれを解いてみるところから始め、このシュレフリの 公式に到達するところまでで、この話は第2回に続きます。
実は、第1回はこのシュレフリの公式を見て、でもここで登場する各二項係数の意味は分からないよね、という ところで終わり、第2回でこの意味の解釈を紹介する、という予定でした。 （漸化式の方は右辺の第1項は$d$次元空間中に$(n-1)$個の超平面がある状況、第2項はそこに$n$個目の超平面を加えた ときに増える領域数、という明確な意味があります。一方、シュレフリの公式の方では各項の意味が（一見）明確ではない。）
ところが、原稿を書き終えてから、マトウシェク「離散数学講義」の書籍中で関連部分を確認してみると、そこには シュレフリの公式の別証明が説明されており、その証明においては公式中の二項係数が明確な意味を持つ形になっていました。 …ということで、この別証明と、そこでの二項係数の解釈を簡単に紹介して初回を終える、という形に書き直しました。
初回からバタバタ慌てた裏事情はあったものの、この話は第2回へ続き、 シュレフリの公式に現れる二項係数を（この別証明における解釈とは別の方法で）きれいに解釈できる説明がある、 という話につながります。
八森正泰