怠け仕出し屋の数列
怠け仕出し屋の数列(なまけしだしやのすうれつ、英語:lazy caterer's sequence)は、より堅い言葉でいうと中心多角形数(ちゅうしんたかくけいすう、central polygonal numbers)であり、ある数の直線カットで作ることのできる円板の破片の最大数を表す(通常パンケーキやピザがこの状況を説明するのに使われる)。例えば、パンケーキを3回カットするとき、カットが全て円内の共通点で重なる場合は6個、そうでない場合は最大の7個になる。この問題は、直線のアレンジメントにおいてセルを数えることの1つとして数学的に定式化できる。高次元への一般化については、超平面配置参照。
この数列の3次元における類似なものはケーキ数である。
式と数列
カット数n(≥0)で作ることのできるピースの最大数pは、式
で与えられる。二項係数を用いると、次のように表される。
簡単に言うと、各数字は三角数に1を加えたものに等しい。
この数列(オンライン整数列大辞典の数列 A000124)はから始めると以下のようになる。
証明
最大数の破片を作るために円をn回カットする場合、p = ƒ(n)と表しn番目のカットを考慮する必要がある。最後のカットの前の破片の数はƒ(n − 1)であり、最後のカットにより加わった破片の数はnである。
破片の最大数を得るには、n番目のカットラインが園内の他の全てのそれまでのカットラインと交差する必要があるが、それまでのカットラインの交点は交わらない。それゆえn番目の線自体はn-1個の場所で切られ、n個の線分に分けられる。各線分はn-1本で切られたパンケーキの1つのピースを2つに分割し、ピースの数はn増える。新たな線は前からある各線を一度だけ横切ることができるため、これ以上区分を増やすことはできない。既にある交点ではない点を中心にナイフを小さな角度で回転させると、角度が十分小さい場合、追加する最後の線含む前からある線すべてと交差するため、カット線は、前からある線全てを常に横切ることができる。
よって、n回カットした後のピースの総数は
と表される。この漸化式は解くことができ、ƒ(n − 1) を1項展開すると関係式は
となる。ƒ(n − 2)の項の展開を最後の項がƒ(0)になるまで行うと
となる。カットする前は1つのピースしかないのでである。よって、次のように書き換えられる。
等差数列の合計の式を用いてシンプルな式にすると、以下の式になる。
関連項目
参考文献
- Moore, T. L. (1991), “Using Euler's formula to solve plane separation problems”, The College Mathematics Journal (Mathematical Association of America) 22 (2): 125–130, doi:10.2307/2686448, JSTOR 2686448.
- Steiner, J. (1826), “Einige Gesetze über die Theilung der Ebene und des Raumes ("A Few Statements about the Division of the Plane and of Space")”, J. Reine Angew. Math. 1: 349–364.
- Wetzel, J. E. (1978), “On the division of the plane by lines”, American Mathematical Monthly (Mathematical Association of America) 85 (8): 647–656, doi:10.2307/2320333, JSTOR 2320333.
外部リンク
- Weisstein, Eric W. "Circle Division by Lines". mathworld.wolfram.com (英語).