空間分割について - 落書き、時々落学

n次元空間を原点を通るk個の(n-1)次元超平面で分割したときの最大個数D(n,k)はどうなるか。
たぶん、k枚目の超平面に注目して、それが1,2,...,k-1枚目の超平面によって、分割される様子を考える。k枚目の超平面はそれまでの超平面によって最大D(n-1,k-1)個に分割される。つまり、もとのn次元空間にもどって考えると、k枚目の超平面を追加するとその超平面は最大D(n-1,k-1)個の分割された空間と交わる。超平面は空間を二分するので、結果最大D(n-1,k-1)分割数が増える。したがって、
D(n,k)=D(n,k-1)+D(n-1,k-1)
かな。
「原点を通る」という制約を外しても同様に考えることができるので、同じ漸化式が成立するっぽい。

正確な証明はよくわかりません。

[追記]
ちょっと調べたら、どうやらあってるみたい。
そして、原点を通る制約を外した場合

$D(n,k)={k \choose 0}+{k \choose 1}+\cdots + {k \choose n}$
である。これは
${k-1 \choose m} + {k-1 \choose m-1} = {k \choose m}$
からしめされる。また、このような分割のことを「アレンジメント」というそうだ。