平面を直線で分ける領域の数

同義語：直線による平面の分割plane division by lines

概要

前提知識: 数列の和と差分, 二項間漸化式, 数学的帰納法と整列性

高校での出発点：線を1本足す

紙に直線を1本引くと、平面は2つの領域に分かれる。もう1本を先の直線と交わるように引くと、4つになる。3本目を先の2本と別々の点で交わるように引けば、7つになる。ここで数える「領域」は、引いた直線を通らずに歩いて行き来できる範囲である。どこまでも広がる部分も1つの領域として数える。

3本目が作る領域

2本の直線でできた4つの領域を考える。3本目が先の2本と異なる2点で交わると、その直線は2点によって3つの部分に分かれる。両端の部分は半直線で、中央は線分である。3つの部分はそれぞれ別の領域の中を通り、その領域を2つに分ける。したがって領域は $4+3=7$ 個になる。
3本目が先の2本の交点を通ると、3本は1点で交わる。3本目の上の交点は1つになり、領域は $4+2=6$ 個にとどまる。増える数は「交わる直線の本数」より「異なる交点の数」で決まる。

この記事の問いは次の2つである。

$n$ 本の直線で作れる領域の最大数はいくつか。→ thm-rpl-total

そのうち、どこまでも広がる領域と、囲まれた領域はいくつずつか。→ thm-rpl-bounded

高校の計算	この記事で数えるもの	大学数学で見ると
数列の差を足す	新しい直線が増やす領域	直線の配置の領域数
$1+2+\cdots+n$	$n$ 本で作れる最大数から1を引いた値	平面上の交点と領域の関係
$\binom n2$	2本を選んで作る交点	配置の頂点の数

二項間漸化式では、前の値と今回増えた数を使って数列を決める。ここでは「領域がいくつ増えるか」を幾何から読み取って漸化式を立てる。

一般の位置と領域

一般の位置にある直線

$n$ 本の直線について、次の2条件が成り立つとき、この直線たちは 一般の位置 にあるという。

どの2本も平行でない。
どの3本も1点で交わらない。
$n=0$ のとき平面全体を1つの領域と数える。$n$ 本が一般の位置にあるときの領域数を $L(n)$ と書く。

「一般の位置」は、交点が重ならず、交わる機会を失わない置き方である。$n$ 本のうち2本を選ぶたびに交点が1つでき、別の選び方で同じ交点にはならない。したがって交点は $\binom n2$ 個である。これは領域数そのものではないが、後で $\binom n2$ が式に現れる理由になる。
平面から直線を除いた各領域は凸である。実際、1本の直線について領域はそのどちらか一方の開いた半平面にあり、2点を結ぶ線分も同じ半平面に入る。このことがすべての直線について成り立つので、同じ領域にある2点を結ぶ線分はどの直線も横切らない。この性質を使うと、新しい直線の異なる部分が同じ古い領域を通ることはない。もし同じ領域にある2点を結んだ線分が新しい直線上の交点をまたげば、その間に古い直線との交点があり、古い直線を横切るからである。
一般の位置にある直線を1本ずつ増やす。4本目は先の3本と異なる3点で交わり、4つの部分を作ることを見る図

4本目を足す

3本で7つの領域がある。4本目が先の3本と異なる3点で交わるように置く。3点は新しい直線を4つの部分に分ける。各部分が古い領域を1つずつ割るので、新たに4つの領域が生まれ、$L(4)=7+4=11$ となる（図1）。

主定理1：領域の総数

一般の位置の $n$ 本が作る領域

$n$ 本の直線が一般の位置にあるとき、領域の数は
$$ L(n)=1+\frac{n(n+1)}2=\frac{n^2+n+2}2 =\binom n0+\binom n1+\binom n2 $$
である。ただし $n=0$ のとき $\binom00=1$、$\binom01=\binom02=0$ とする。

新しい直線上の交点を数える

方針：$n$ 本目の直線が増やす領域を数え、得た漸化式の差を足す。
段1（増える数）。$n\ge1$ とし、先の $n-1$ 本が作る領域を考える。新しい直線はその各直線と交わる。3本が1点で交わらないので、新しい直線上には異なる交点が $n-1$ 個ある。これらは新しい直線を $n$ 個の部分に分ける。$n=1$ なら交点はなく、直線全体を1つの部分とみなす。
段2（各部分が何をするか）。交点を含まない各部分は、先の直線が作った領域の内部を通る。両側には新しい直線を横切らずには行き来できない部分ができるので、その古い領域は2つに分かれる。異なる部分は異なる古い領域を通る。これは def-rpl-general の後で確かめた凸性から分かる。したがって、増える領域はちょうど $n$ 個である。
$$ L(n)-L(n-1)=n\qquad(n\ge1),\qquad L(0)=1. $$
段3（差を足す）。左辺を $n=1$ から順に足すと、途中の $L(1),\ldots,L(n-1)$ は相殺される（数列の和と差分）。よって
$$ L(n)-L(0)=1+2+\cdots+n=\frac{n(n+1)}2. $$
$L(0)=1$ を入れれば最初の式を得る。
段4（二項係数で書く）。$\binom n0=1$、$\binom n1=n$、$\binom n2=\frac{n(n-1)}2$ なので、
$$ \binom n0+\binom n1+\binom n2 =1+n+\frac{n(n-1)}2 =1+\frac{n(n+1)}2. $$
最後の形も同じ数を表す。$\square$

「2つに分かれる」ことの根拠

段2では、新しい直線の1つの部分が古い領域を2つに分けることを使った。直線の場合、これは凸性で確かめられる。古い領域 $R$ は凸で、新しい直線が $R$ の点を通るので、直線の両側にそれぞれ $R$ の点がある。$R$ のうち直線の一方の側にある部分は、凸な集合どうしの共通部分なので凸で、一続きである。よって $R$ はちょうど2つに分かれる。
一方、円のような曲線で領域を切るときの同じ事実、すなわち「穴のない領域を境界の2点を結ぶ曲線で切ると2つに分かれる」ことは、厳密な証明に位相幾何の道具（Jordan の曲線定理）が要る。高校数学の範囲を超えるので、この記事でも平面を円で分ける領域の数でも証明しない。

$$ \underbrace{L(n)-L(n-1)}_{\text{新しい直線で増える領域}}= \underbrace{(n-1)+1}_{\text{新しい直線上の交点と部分}} $$

小さい本数を順に数える

$L(0)=1$ から漸化式に $n=1,2,3,4,5$ を順に入れる。
$$ L(1)=1+1=2,\quad L(2)=2+2=4,\quad L(3)=4+3=7, $$
$$ L(4)=7+4=11,\quad L(5)=11+5=16. $$
例えば5本目は先の4本と4点で交わり、自身が5つの部分に分かれる。したがって $11$ 個から $16$ 個へ増える。一般項でも $L(5)=1+\frac{5\cdot6}2=16$ と確かめられる。

この数は最大でもある。任意の置き方で新しい直線を足すと、先の $n-1$ 本との異なる交点は高々 $n-1$ 個であり、増やせる領域は高々 $n$ 個だからである。一般の位置なら毎回その上限に達する。Keller と Trotter はこの漸化式を直線の配置の例として扱う（KT17 Example 3.3、§9.1.3）。最大値の式と数列は MWLines にも載っている。

主定理2：囲まれた領域

直線だけで囲まれた三角形や四角形の内部は、有限の範囲に収まる。このような領域を 有界な領域 という。どこまでも進める領域を 有界でない領域 という。直線が1本もなければ、平面全体が有界でない領域である。

3本のときの内訳

一般の位置の3本では、3つの交点を頂点とする三角形の内部が1つだけ有界な領域になる。残りの6つはどこまでも広がる。合計は $1+6=7$ で、ex-rpl-three と一致する。
3本が1点で交わると、三角形はできず、6つとも有界でない。領域の総数だけでなく、囲まれた領域の数も交点の重なりで変わる。

有界な領域と有界でない領域

$n\ge1$ 本の直線が一般の位置にあるとき、有界でない領域は $2n$ 個、有界な領域は
$$ L(n)-2n=\frac{(n-1)(n-2)}2=\binom{n-1}2 $$
個である。$n=1$、$n=2$ では右辺を $0$ と読む。

十分大きな円の外側で数える

方針：直線どうしの交点をすべて中に入れる大きな円を考える。有界でない領域と円周上の弧が1対1に対応することを、直線を1本ずつ足して確かめる。
段1（最初の直線）。1本の直線は円周を2点で切り、円周に2本の弧を作る。直線の両側の領域はそれぞれ1本の弧を含み、ともに有界でない。ここで領域と弧の1対1対応が成り立つ。
段2（1本足す）。先の $n-1$ 本について、それらの交点をすべて内部に含み、どの直線とも2点で交わる円であれば、どの円でも1対1対応が成り立つとする（段1 の議論はどの円でも同じである）。すべての古い交点と新しい交点を内部に含む円を十分大きく取り、円周上のどの直線の交点も重ならないようにする。$n$ 本目は円周と2点で交わる。その2点は、先のどの直線についても反対側にある。なぜなら新しい直線はその古い直線と円の内部で交わるからである。よって2点は異なる古い領域の弧の中にある。
段3（新しい弧と領域）。新しい2点は、異なる古い弧をそれぞれ2本に分ける。新しい直線の両端の半直線は、この2つの古い領域をそれぞれ割り、割った両側は円周の新しい弧に接するので有界でない。一方、新しい直線の有限な部分が割る古い領域では、円周上の古い弧は切られない。古い領域が有界なら割った両側も有界である。古い領域が有界でないなら、分かれた2つのうち円周に達するのは一方だけで、他方は有界である。したがって領域と弧の1対1対応は保たれ、弧も有界でない領域も2個増える。帰納法により、有界でない領域は $n\ge1$ で $2n$ 個である。
段4（数を引く）。thm-rpl-total から引くと
$$ L(n)-2n=1+\frac{n(n+1)}2-2n =\frac{n^2-3n+2}2 =\frac{(n-1)(n-2)}2 $$
となる。$n\ge2$ なら最後は $\binom{n-1}2$ である。$n=1$ の有界な領域は直接 $0$ 個と分かる。$\square$

有界でない領域を円周の弧で数える際、円は「交点を含む」だけでなく、直線と円の交点が互いに異なるほど十分大きくする。円を小さく描いて直線を見落とすと $2n$ 本にはならない。

4本と5本の内訳

4本なら総数は $L(4)=11$。有界でない領域は $2\cdot4=8$、有界な領域は $\binom32=3$ 個である。
5本なら総数は $L(5)=16$。有界でない領域は $2\cdot5=10$、有界な領域は $\binom42=6$ 個である。5本目を入れると総数は5つ増え、そのうち有界でない領域の増加は2つ、有界な領域の増加は3つになる。

直線の本数 $n$	$L(n)$	有界でない領域	有界な領域
$0$	$1$	$1$	$0$
$1$	$2$	$2$	$0$
$2$	$4$	$4$	$0$
$3$	$7$	$6$	$1$
$4$	$11$	$8$	$3$
$5$	$16$	$10$	$6$

$n=0$ だけは有界でない領域が1つであり、$2n$ の式には含めない。表の各行では、有界な領域と有界でない領域の和が $L(n)$ になっている。

一般の位置でない場合（反例）

新しい直線が先の直線と平行なら、その相手とは交点を作らない。3本以上が1点で交わると、複数の「交わる機会」が1つの交点になる。どちらの場合も、交点の数と増える領域が減る。thm-rpl-total・thm-rpl-bounded とその証明の仮定を1つずつ外した反例を表にまとめる。

外す条件	反例	成り立たなくなること
条件1（どの2本も平行でない）	平行な2本と、両方を横切る1本	領域は $7$ でなく $6$。平行な2本は交わらないので、3本目の上の交点が1つ減る
条件1（どの2本も平行でない）	縦2本・横2本の2組の平行線	領域は $11$ でなく $9$。交点は $6$ 個でなく $4$ 個
条件2（どの3本も1点で交わらない）	1点で交わる3本	領域は $7$ でなく $6$。有界な三角形もできず、thm-rpl-bounded の $\binom22=1$ も $0$ になる
平面全体を分ける	円の内部だけを数える（3本が円の中で交わる）	有界でない領域が $2n$ 個（円の内部には有界でない領域がない）

条件1を外す2つの例では、平行な組が交点をもたないので、「新しい直線は先の直線と $n-1$ 個の点で交わる」という prf-rpl-total の段1が崩れている。条件2を外す例では、3組の交わりが1点に重なり、同じ段1の「異なる交点が $n-1$ 個」が崩れている。
定義の外の例として、直線の代わりに線分を許すと、どの直線とも交わらない短い線分は1つの領域の中に収まり、領域を1つも増やさない。たとえば交わる2直線（領域 $4$ 個）に、どちらにも届かない短い線分を足しても、領域は $4$ 個のままである。線分の端から先では古い領域を割らないので、thm-rpl-total の数え方はそのままでは使えない。

平行な2本と横切る1本

最初の2本を平行に置くと、平面は3つの帯状の領域に分かれる。3本目が両方を横切ると交点は2つあり、3本目は3つの部分になる。各部分で古い領域が割れるので $3+3=6$ 個となる。3本を一般の位置に置いたときの $7$ より1個少ない。

2組の平行線

縦の2本と横の2本を引く。縦の2本は平行で、横の2本も平行である。縦2本だけなら領域は3つ。横の1本目は縦2本と2点で交わるので3つ増え、横の2本目も同様に3つ増える。総数は $3+3+3=9$ 個である。中央の長方形の内部だけが有界で、残りの8つは有界でない。一般の位置の4本なら総数は $11$ であり、この格子とは異なる。

交点の重なり方が複雑でも、一般の式を1つ書ける。交点 $P$ を通る直線の本数を $m_P$ とする。和は、直線どうしの交点すべてにわたって取る。

任意の直線配置の領域数

相異なる $n$ 本の直線が作る領域の数は
$$ 1+n+\sum_P(m_P-1) $$
である。平行な組は交点を作らず、和に寄与しない。

直線を1本ずつ加える

直線をどの順に加えてもよい。新しい直線上に、先の直線との異なる交点が $k$ 個あると、その直線は $k+1$ 個の部分に分かれ、領域を $k+1$ 個増やす。交点をまったく作らない直線も1個増やすので、全体でまず $n$ 個増える。
次に、ある交点 $P$ に注目する。そこを通る $m_P$ 本のうち、最初に加えた1本は $P$ を交点としては作らない。残りの $m_P-1$ 本は、加わるときにそれぞれ $P$ を「異なる交点」の1つとして数える。したがって $P$ が全体の $k$ の合計に寄与するのは $m_P-1$ 回である。交点全体について足し、最初の1領域を加えれば式になる。$\square$

重なる交点を式で確かめる

3本が1点 $P$ を通ると、$m_P=3$ で、ほかの交点はない。prop-rpl-arbitrary は $1+3+(3-1)=6$ を与え、ex-rpl-three の結果と一致する。
2組の平行線の格子では、縦と横の交点が4つあり、どれも $m_P=2$ である。式は $1+4+4(2-1)=9$ を与え、ex-rpl-grid と一致する。

この式を使うと、領域の数が最大値 $L(n)$ になるのは一般の位置のときに限ることが分かる。つまり、表の 1〜3 行目のように一般の位置の条件が1つでも崩れると、領域は必ず減る。

最大になるのは一般の位置のときだけ

相異なる $n$ 本の直線が作る領域の数は $L(n)$ 以下であり、ちょうど $L(n)$ になるのは $n$ 本が一般の位置にあるときに限る。

2本の組を交点ごとに分ける

$n$ 本から2本を選ぶ組は $\binom n2$ 通りある。平行な組は交点をもたない。平行でない組は、ちょうど1つの交点 $P$ をもつ。交点 $P$ を通る直線は $m_P$ 本なので、$P$ で交わる組は $\binom{m_P}2$ 通りある。したがって
$$ \sum_P\binom{m_P}2=\binom n2-(\text{平行な組の数}) $$
である。一方 $m_P\ge2$ なので
$$ \binom{m_P}2-(m_P-1)=\frac{m_P(m_P-1)}2-(m_P-1)=\frac{(m_P-1)(m_P-2)}2\ge0 $$
であり、等号は $m_P=2$ のときに限る。prop-rpl-arbitrary と合わせると
$$ 1+n+\sum_P(m_P-1)\le1+n+\sum_P\binom{m_P}2\le1+n+\binom n2=L(n) $$
である。1つ目の不等号が等号になるのは、すべての交点で $m_P=2$、つまりどの3本も1点で交わらないときである。2つ目の不等号が等号になるのは、平行な組が1つもないときである。両方がそろうことが一般の位置の定義そのものである。$\square$

等号を確かめる

3本が1点で交わるときは $m_P=3$ の交点が1つで、$\binom32-(3-1)=3-2=1$ だけ1つ目の不等号で減る。領域は $L(3)-1=6$ 個である。2組の平行線では交点はすべて $m_P=2$ だが、平行な組が2つあるので2つ目の不等号で $2$ 減り、$L(4)-2=11-2=9$ 個になる。どちらも ex-rpl-triple の計算と一致する。

大学数学で見る：交点・辺・領域

直線を平面に描いた図は、交点を頂点、交点から次の交点までの線分や外へ伸びる半直線を辺とする図形とみなせる。これは Eulerの多面体定理（高校数学）で現れる、頂点・辺・領域を結ぶ考え方に近い。

頂点と辺から数え直す

$n\ge2$ 本を一般の位置に置く。2本を選ぶたびに1つの交点があるので、有限の頂点数は $V=\binom n2$ である。各直線は先の数え方と同様、自分以外の $n-1$ 本との交点によって $n$ 個の辺に分かれる。辺は別の直線と重ならないので、全体では $E=n^2$ 本である。無限遠に1つの頂点を加え、すべての半直線の先をそこで結ぶと、球面上の連結したグラフになる（球面から1つの面の内部の点を除いて平面に移せば、平面上の描画になり、面の数は変わらない）。このグラフの頂点は $V+1$ 個、辺は $E$ 本、面はもとの領域と同じ $F=L(n)$ 個である。連結なグラフについての Euler の関係 $(V+1)-E+F=2$ から（この記事では証明しない。KT17 Theorem 5.32、p. 90。同じ 2 頂点を結ぶ辺が複数あるが、各辺の途中に頂点を 1 つずつ足せばそれがなくなり、頂点と辺が同じ数だけ増えるので左辺は変わらない）
$$ F=1+E-V=1+n^2-\binom n2=1+\frac{n(n+1)}2 $$
を再び得る。無限遠の頂点を入れ忘れて $V-E+F=2$ とすると、答えが1だけずれる。この見方は KT17 §9.1.3 の漸化式とは別の数え方である。

この数え直しでは、直線の部分を辺として数えるときに、交点のない1本目だけを特別扱いしないでよい。$n\ge2$ では各直線に $n-1$ 個の交点があるので、辺が $n$ 本になる。$n=1$ は直接数えられる。

4本を頂点・辺で検算する

一般の位置の4本には交点が $\binom42=6$ 個ある。1本あたり4本の辺があり、辺は $4\cdot4=16$ 本である。無限遠の頂点を1つ加えると頂点は7個。Euler の式から面は $2-7+16=11$ 個となり、ex-rpl-four と一致する。

直線を点に置き換えて数直線を分ければ、$n$ 個の異なる点は $n+1$ 個の区間を作る。平面ではそれに $\binom n2$ が加わる。さらに空間を平面で切ると $\binom n3$ も加わる。この次元ごとに項が1つ増える関係は空間を平面で分ける領域の数で扱う。平面を直線ではなく円で分けると、1本目から増え方が変わる。それは平面を円で分ける領域の数に進む。

さらに先へ

円周上の点をすべて弦で結び、円の内部を分ける問題は数列の一般項の推定と帰納法の命題「円の内部の領域の個数」にある。この記事の直線による平面全体の分割とは対象が違う。そこでは4点を選ぶ交点が現れ、答えに $\binom n4$ が出る。どちらの問題でも「新しい図形を1つ足したとき、領域がいくつ増えるか」が出発点になる。
同じ出発点から、直線を円に替えた平面を円で分ける領域の数では漸化式が $C(n)-C(n-1)=2(n-1)$ になり、次元を1つ上げた空間を平面で分ける領域の数では、新しい平面の上にこの記事の直線の分割がそのまま現れて $S(n)-S(n-1)=L(n-1)$ になる。