せんべい分割問題 解３

せんべい分割問題の解答例を示します。

解３：漸化式を使う。

分割の数をh(n)とする。

　n-1回の切断が行われたところにn回目の切断を行う。このとき、n回目の切断線はn-1回の切断線と交わり、新たに n個の断片が作られる。

　　　　h(n) = h(n-1)+n

したがって、h(n) = h(n-1)+n
                             = n+(n-1)+(n-2)+…+2+2
                             = n(n+1)/2+1
                             = (n²+n+2)/2

（注意）h(n) = (n²+n+2)/2 = C(n,0)+C(n,1)+C(n,2) とも書ける。
ただし、C(n,r)は２項係数。