■円の切断(その4)

【4】最大分割数の二項係数表現

(問)平面をn本の線で分割する.その際,分割によってできる領域が最も多くなるようにする.最大分割領域数Snはいくつになるか,の答は

Sn=n+1C2+1=(n^2+n+2)/2

でしたが,もうひとつの答は

  Sn=nC0+nC1+nC2=(n^2+n+2)/2

 この公式はn本のカットから,それぞれ0本,1本,2本のカットを選ぶ,切り口はその選び方の順序にはよらないので2で割る,と同値であると解釈されます.

また,オイラーの公式を使って,ピザ切り分け問題を解くために,頂点と辺を数えると,2n個の境界頂点とnC2=n(n−1)/2個の内部頂点があるから

  e=2n+n(n−1)/2

 また,ピザの境界上にn本の曲線状の辺とn本のカットはそれぞれn本の直線の辺を含んでいるから

  v=2n+n^2

 よって,

  f=e−v+1=(n^2+n+2)/2

(問)1つの円をn本の弦で分割する.その際,分割によってできる領域が最も多くなるようにする.円と共通点をもつピースの個数Pnはいくつになるか?

  P1=2,P2=4,P3=6,P4=8,P5=10

はすぐに求められます.このことからn本目の線(弦)を引くと新しい領域が2個増えることがわかります.これを式で表すと

  Pn=Pn-1+2

  Pn=2n

 逆に,円と共通点をもたないピースの個数Qnは

  Qn=Sn−Pn=(n^2+n+2)/2−2n

あるいは,もうひとつのバージョンでは

  Qn=(nC0)−(nC1)+(nC2)=(n^2+n+2)/2−2n

===================================