空間分割について

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)

かな。

「原点を通る」という制約を外しても同様に考えることができるので、同じ漸化式が成立するっぽい。

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

[追記]

ちょっと調べたら、どうやらあってるみたい。

そして、原点を通る制約を外した場合

である。これは

からしめされる。また、このような分割のことを「アレンジメント」というそうだ。