場合の数 ★★★★ 難関の問題 全8問

方針

解答

⓪ 発想(どう考え始めるか) 「女子どうしが隣り合わない」は、女子を直接並べると条件が扱いにくい。先に男子を並べ、その隙間に女子を入れるのが基本だ。

まず男子 $4$ 人を円形に並べる。円順列だから $(4-1)!=6$ 通り。男子 $4$ 人の間には $4$ つの隙間ができる。ここに女子 $4$ 人を $1$ 人ずつ入れれば、女子は必ず男子にはさまれて隣り合わない。入れ方は $4!=24$ 通り。積で $6\times 24=144$。

① 男子を円形に並べる。 男子 $4$ 人の円順列は $(4-1)!=3!=6$ 通り。

② 隙間に女子を入れる。 男子 $4$ 人を円形に並べると、隣り合う男子の間に隙間が $4$ つできる。この $4$ か所に女子 $4$ 人を $1$ 人ずつ入れれば、女子はどの $2$ 人も隣り合わない。入れ方は $4!=24$ 通り。

③ 積をとる。

$$6\times 24=144\text{通り}$$

まとめ:「隣り合わない」円順列は「片方を円形に並べる → 隙間に入れる」の $2$ 段。円順列で先に並べるほうは $(n-1)!$、隙間の数はちょうど並べた人数と同じ($4$ 人なら $4$ 隙間)になるのがポイント。人数が同じ($4$ と $4$)なので隙間がぴったり埋まる。

発展。 男子 $m$ 人・女子 $f$ 人($f\le m$)の円卓で女子が隣り合わない場合の数は $(m-1)!\times {}_m{\mathrm{P}}_f$。男子の隙間 $m$ か所から $f$ か所を選んで女子を並べる。$m=f$ のときは女子が全隙間を埋め、男女交互になる。「隙間に入れる」発想は隣接禁止の配置問題ならいつでも使える。

別解

別解:女子を「$1$ 人だけ固定」して回転を消す(別の視点)。 円順列を「$1$ 人を固定して残りを直線的に並べる」方法で数え直す。

女子の $1$ 人 W₁ を上席に固定する(これで回転の重複が消える)。残りの $7$ 席に、男子 $4$ 人と女子 $3$ 人を並べる。

W₁ の両隣は男子でなければならない(女子隣り合わせ禁止)。両隣の男子を選んで並べ、残りを配置する…と数えると煩雑になるので、本解の「男子を円に並べ隙間に女子」の方が速い。ただし固定の考え方は同じで、$\frac{8!\text{相当}}{\text{回転}}$ を条件付きで数えることに変わりはない。

検算として、条件なしの男女 $8$ 人の円順列は $(8-1)!=5040$ 通り。そのうち女子が隣り合わない $144$ 通りは約 $2.9\%$。「男女交互(女子が完全に離れる最も厳しい配置)」は $(4-1)!\times 4!=144$ でこれと一致する。女子 $4$・男子 $4$ で女子が隣り合わないのは、実は男女交互しかないからだ。

方針

解答

⓪ 発想(どう考え始めるか) 回転を考えなければ $6$ 面に $6$ 色で $6!=720$ 通り。だが立方体は回転で重なるものを同一視するので、重複を除く。

回転の重複を除くうまい方法は「$1$ つの面を固定する」。たとえば「ある色(赤)を上面に固定」と決めると、回転の自由度が減る。赤を上に固定したら、底面の色は残り $5$ 通り。側面 $4$ 色は上下軸まわりの回転(円順列)で $(4-1)!=6$ 通り。$5\times 6=30$。

① 上面の色を固定する。 ある特定の色(赤とする)を上面に来るように回転で合わせる。どの塗り方も回転すれば赤を上にできるので、これで上下方向の重複が消える。

② 底面の色を選ぶ。 残り $5$ 色から底面の色を選ぶ:$5$ 通り。

③ 側面 $4$ 色を並べる。 残り $4$ 色を $4$ つの側面に配置する。上下を軸にして回すとぐるぐる回るので、これは円順列:$(4-1)!=3!=6$ 通り。

④ 積をとる。

$$5\times 6=30\text{通り}$$

(確かめ:回転の重複を考えない $6!=720$ を、立方体の回転の総数 $24$ で割っても $720÷24=30$。)

まとめ:回転で同一視する塗り分けは「基準を固定して重複を封じる」。上面を固定すると側面が円順列になり、$5\times (4-1)!=30$。全体を回転数 $24$ で割る方法(すべての色が異なるので割り切れる)でも同じ答えになる。

発展。 立方体の面の塗り分けは回転群(位数 $24$)による対称性の数え上げ。色に重複があると、バーンサイドの補題(各回転で不変な塗り方を平均する)が役に立つ。たとえば $2$ 色で塗る場合は $10$ 通り、$3$ 色なら…と、群論が「見た目の対称性」を数える道具になる。

別解

別解:バーンサイドの補題で回転群 $24$ で割る(得意な人向けの高い視点)。 立方体の回転は全部で $24$ 通り(面を上にする選び $6$ × その面の回転 $4$)。異なる $6$ 色で全面を塗るとき、回転で不変な塗り方は「恒等回転」以外にない(どの回転も少なくとも $2$ 面を入れ替えるが、$6$ 色すべて異なるので入れ替わると別物)。

バーンサイドの補題「異なる塗り方の数 $=\frac{1}{|G|}\sum (\text{各回転で不変な塗り方の数})$」を使う。不変なのは恒等回転のときの $6!=720$ 通りだけ、他の $23$ 個の回転では $0$。

$$\frac{720+0+\cdots +0}{24}=\frac{720}{24}=30.$$

$1$ 面固定で数える本解と同じ $30$ だが、バーンサイドは「回転で不変なものを数えて群の位数で割る」一般公式。色に重複がある場合(たとえば $6$ 面を $3$ 色で)には、各回転の寄与が $0$ でなくなり、本解の固定法より機械的に数えられる。

方針

解答

⓪ 発想(どう考え始めるか) 「$\mathrm{a}$ が隣り合わない」も、$\mathrm{a}$ 以外を先に並べて隙間に $\mathrm{a}$ を入れる型だ。

まず $\mathrm{a}$ 以外の $\mathrm{b},\mathrm{b},\mathrm{c}$ を並べる。同じ $\mathrm{b}$ が $2$ 個あるので $\frac{3!}{2!}=3$ 通り。$3$ 文字の間と両端で、隙間は $4$ か所。ここから $3$ か所を選んで $\mathrm{a}$ を $1$ 個ずつ入れる($\left(\genfrac{}{}{0ex}{}{4}{3}\right)=4$ 通り)。同じ隙間に $2$ 個入れなければ $\mathrm{a}$ は隣り合わない。$3\times 4=12$。

① $\mathrm{a}$ 以外を並べる。 $\mathrm{b},\mathrm{b},\mathrm{c}$ の $3$ 文字の並べ方は、$\mathrm{b}$ が $2$ 個ダブるので

$$\frac{3!}{2!}=3\text{通り}$$

② 隙間を数えて $\mathrm{a}$ を入れる。 $3$ 文字を並べると、間と両端に隙間が $4$ か所できる。

この $4$ か所から $3$ か所を選んで $\mathrm{a}$ を $1$ つずつ入れる($\mathrm{a}$ は同じ文字なので順序は関係ない):

$${}_4{\mathrm{C}}_3=4\text{通り}$$

③ 積をとる。

$$3\times 4=12\text{通り}$$

まとめ:「同じ文字が隣り合わない」は「他を並べて隙間に入れる」。$\mathrm{a}$ 以外の並べ方(ダブりを $2!$ で割る)と、隙間の選び方 ${}_4{\mathrm{C}}_3$ の積。両端も隙間に数えることを忘れない($3$ 文字なら隙間は $4$ か所)。

発展。 「同じ文字が隣り合わない」の一般的な数え上げは、包除原理や隙間法で扱う。文字の種類と個数が増えると難しくなり、「$\mathrm{aa}\cdots \mathrm{a}$($p$ 個)が隣り合わない」は、他の文字の並びの隙間から $p$ か所を選ぶ問題。連続を禁止する配置はDNA配列やスケジューリングなど応用も広い。

別解

別解:総数から「$\mathrm{a}$ が隣り合う」を引く(補集合のルート)。 $6$ 文字全体の並べ方は $\frac{6!}{3!2!}=60$ 通り。ここから「$\mathrm{a}$ が隣り合う場合」を引く。ただし「隣り合う」の数え上げは包除が要る。

「$\mathrm{aa}$ が少なくとも $1$ 組できる」を数える。$\mathrm{aa}$ を $1$ かたまり $[\mathrm{aa}]$ とみて、$[\mathrm{aa}],\mathrm{a},\mathrm{b},\mathrm{b},\mathrm{c}$ の $5$ 個を並べると $\frac{5!}{2!}=60$…だが、これは $\mathrm{aaa}$($3$ 個連続)を二重に数える。$\mathrm{aaa}$ を $1$ かたまりとみると $[\mathrm{aaa}],\mathrm{b},\mathrm{b},\mathrm{c}$ で $\frac{4!}{2!}=12$ 通り。包除で「隣り合う」$=60-12=48$。

答え $=60-48=12$。隙間法(本解)が「隣り合わない」を直接作るのに対し、補集合は「全体 $-$ 隣り合う」。ただし「隣り合う」の数え上げに包除が必要で、$\mathrm{aaa}$ の二重計上に注意が要る。同じ $12$ に着くが、隙間法の方が明快だ。

方針

解答

⓪ 発想(どう考え始めるか) 「$\mathrm{P}$ を通り $\mathrm{Q}$ を通らない」は、直接数えず引き算で攻める。

「$\mathrm{P}$ を通る経路」から「$\mathrm{P}$ と $\mathrm{Q}$ の両方を通る経路」を引けば、$\mathrm{P}$ を通るが $\mathrm{Q}$ は通らない経路になる。各区間の最短経路数は右と上の移動回数の組合せ。$\mathrm{A}\to \mathrm{P}$、$\mathrm{P}\to \mathrm{B}$、$\mathrm{P}\to \mathrm{Q}\to \mathrm{B}$ をそれぞれ計算し、$(\mathrm{A}\to \mathrm{P}\to \mathrm{B})-(\mathrm{A}\to \mathrm{P}\to \mathrm{Q}\to \mathrm{B})$ を求める。

① $\mathrm{P}$ を通る経路。 $\mathrm{A}(0,0)\to \mathrm{P}(2,1)$ は右 $2$・上 $1$ で ${}_3{\mathrm{C}}_2=3$ 通り。$\mathrm{P}(2,1)\to \mathrm{B}(5,4)$ は右 $3$・上 $3$ で ${}_6{\mathrm{C}}_3=20$ 通り。よって

$$3\times 20=60\text{通り}$$

② $\mathrm{P}$ と $\mathrm{Q}$ の両方を通る経路。 $\mathrm{A}\to \mathrm{P}$ は $3$ 通り。$\mathrm{P}(2,1)\to \mathrm{Q}(3,3)$ は右 $1$・上 $2$ で ${}_3{\mathrm{C}}_1=3$ 通り。$\mathrm{Q}(3,3)\to \mathrm{B}(5,4)$ は右 $2$・上 $1$ で ${}_3{\mathrm{C}}_2=3$ 通り。よって

$$3\times 3\times 3=27\text{通り}$$

③ 引く。

$$60-27=33\text{通り}$$

まとめ:「通る・通らない」が混ざったら「通る全体 − 両方通る」の引き算。最短経路数は区間ごとに ${}_{p+q}{\mathrm{C}}_p$ で出し、点を通る経路は掛け算でつなぐ。$\mathrm{P}$ を通る $60$ から、余分な「$\mathrm{Q}$ も通る $27$」を除いて $33$。

発展。 格子の最短経路数は各点に「左＋下」を足し込むパスカルの三角形そのもの。通行止め(通らない点)は、その点を $0$ にするだけで対応できる。これは動的計画法(DP)の最も基本的な例で、迷路の経路数え上げやロボットの経路計画の原型になっている。

別解

別解:格子の各点に経路数を書き込む(視覚で確実なルート)。 $\mathrm{A}$ から各格子点までの最短経路数を、左下から順に書き込む(各点は「左の点＋下の点」の和)。ただし「$\mathrm{Q}$ を通らない」ので、$\mathrm{Q}(3,3)$ の経路数を $0$ にしてから先へ進める。

まず $\mathrm{A}(0,0)$ から $\mathrm{P}(2,1)$ までの経路数は $\left(\genfrac{}{}{0ex}{}{3}{2}\right)=3$。ここからは「$\mathrm{P}$ を出発点」として、$\mathrm{Q}$ を封鎖しながら $\mathrm{B}(5,4)$ まで足し上げる。

$\mathrm{P}$ に $3$ を置き、右・上へ和を伝播。$\mathrm{Q}(3,3)$ に来たらそこを $0$ にリセット($\mathrm{Q}$ 経由を消す)。この「通行止め付き」の経路数え上げを $\mathrm{B}$ まで続けると $\mathrm{B}$ に $33$ が現れる。

引き算(本解)$60-27=33$ と同じ結果。格子に数を書き込む方法は、封鎖点が複数あっても「その点を $0$ にする」だけで対応でき、視覚的に確実。動的計画法(DP)の最も素朴な形だ。

方針

解答

⓪ 発想(どう考え始めるか) 「組を区別しない」「人数は問わない」の $2$ つが厄介。まず「組を区別する」問題に直し、あとで区別をなくす。

$3$ つの区別する箱に $6$ 人を、空箱がないように入れる。全体 $3^6$ から、空箱ができる場合を包除原理で引く。$3^6-\left(\genfrac{}{}{0ex}{}{3}{1}\right)2^6+\left(\genfrac{}{}{0ex}{}{3}{2}\right)1^6=729-192+3=540$。

最後に組の区別をなくす。$3$ つの組はどれも $1$ 人以上で人数が違えば区別が意味を持つが、区別しないので $3!$ で割る。$540÷6=90$。

① 区別する $3$ 組へ、空なしで入れる。 各人が $3$ 組のどれかに入る入れ方は $3^6=729$。ここから「ある組が空」の場合を包除で除く。

$$3^6-{}_3{\mathrm{C}}_1\cdot 2^6+{}_3{\mathrm{C}}_2\cdot 1^6=729-3\cdot 64+3\cdot 1=729-192+3=540$$

② 組の区別を消す。 いま組を区別して数えたが、実際は区別しない。組の並べ替え $3!=6$ 通りが同じ分け方を重複して数えているので、$6$ で割る。

$$\frac{540}{6}=90\text{通り}$$

まとめ:人数指定のない組分けは「区別あり(各人に組を割り当て)→ 包除で空組を除く → $3!$ で区別を消す」の $3$ 段。人数が同じとは限らないので $\frac{6!}{2!2!2!3!}$ のような単純な式は使えず、包除が要る。この数は $6$ 人を $3$ つに分ける「第 $2$ 種スターリング数」$S(6,3)=90$ にあたる。

発展。 「$n$ 人を $k$ 組(区別なし・各 $1$ 人以上)に分ける」数は第 $2$ 種スターリング数 $S(n,k)$。$S(6,3)=90$。組を区別すれば $k!S(n,k)$(全射の数)。$k$ を $1$ から $n$ まで足した ${\sum }_{k}S(n,k)$ はベル数(組の数を問わない分割の総数)で、集合の分割を数える基本量だ。

別解

別解:人数の組(パターン)で場合分けする(苦手な人にも見通しのよいルート)。 $6$ 人を $3$ 組(区別なし・各 $1$ 人以上)に分けるとき、人数のパターンは $6=4+1+1=3+2+1=2+2+2$ の $3$ 通り。パターンごとに数える。

【$4,1,1$】$4$ 人組の選び方 $\left(\genfrac{}{}{0ex}{}{6}{4}\right)=15$。残り $2$ 人は $1$ 人ずつ($1$ 通り、$1$ 人組どうしは区別なし)。$15$ 通り。

【$3,2,1$】$3$ 人 $\left(\genfrac{}{}{0ex}{}{6}{3}\right)=20$、$2$ 人 $\left(\genfrac{}{}{0ex}{}{3}{2}\right)=3$、$1$ 人 $1$。人数がすべて違うので区別の重複なし。$20\times 3=60$ 通り。

【$2,2,2$】$\frac{1}{3!}\left(\genfrac{}{}{0ex}{}{6}{2}\right)\left(\genfrac{}{}{0ex}{}{4}{2}\right)\left(\genfrac{}{}{0ex}{}{2}{2}\right)=\frac{15\cdot 6\cdot 1}{6}=15$ 通り(同じ人数 $3$ 組は $3!$ で割る)。合計 $15+60+15=90$。包除 $+$ $3!$ で割る本解に対し、人数パターンで分けると各ケースが素朴な組合せになる。同じ人数の組がある($2,2,2$)ときだけ重複を割る、という注意が要点だ。

方針

解答

⓪ 発想(どう考え始めるか) 偶数 $⟺$ 一の位が偶数($0,2,4$)。だが $0$ は百の位に置けないので、一の位が $0$ か $2,4$ かで制約が変わる。場合分けする。

【一の位が $0$】百の位・十の位は残り $\{1,2,3,4\}$ から $2$ 個で $4\times 3=12$ 通り($0$ の制約なし)。【一の位が $2$ または $4$】($2$ 通り)。百の位は $0$ と一の位の目を除く $3$ 通り、十の位は残り $3$ 通り。$2\times 3\times 3=18$ 通り。合わせて $12+18=30$。

① 一の位が $0$ のとき。 一の位は $0$ に確定。残り $4$ 個($1,2,3,4$)から百の位・十の位を選ぶ。$0$ はもう使ったので先頭制約はなく、

$$4\times 3=12\text{個}$$

② 一の位が $2$ または $4$ のとき。 一の位の選び方は $2$ 通り。このとき百の位には $0$ と一の位の数字が使えないので、残り $3$ 個(=$\{0,1,2,3,4\}$ から一の位を除いた $4$ 個のうち $0$ を除く)から選ぶ:$3$ 通り。十の位は残り $3$ 個から $1$ つ($0$ も使える):$3$ 通り。よって

$$2\times 3\times 3=18\text{個}$$

③ 合計する。

$$12+18=30\text{個}$$

まとめ:「$0$ を含む数字で整数を作る」は、$0$ の特別扱い(先頭に置けない)で場合分け。一の位が $0$ なら先頭の制約が消え、一の位が $2,4$ なら先頭で $0$ を除く。$0$ をどこで消費するかを軸に分けると数え漏れがない。

発展。 $0$ を含む数字で整数を作る問題は「最高位に $0$ を置けない」制約が要。$0$ を一の位に置くか否かで場合分けするのが基本だ。桁の制約(最高位 $\ne 0$、偶数なら末尾偶数、$3$ の倍数なら桁和が $3$ の倍数)を組み合わせると、様々な整数の個数え上げに発展する。

別解

別解:全体から奇数を引く(補集合のルート)。 $0\sim 4$ から異なる $3$ 個で作る $3$ 桁の整数の総数を出し、そこから奇数を引く。

$3$ 桁の整数の総数: 百の位は $0$ 以外で $4$ 通り、十の位は残り $4$ 通り、一の位は残り $3$ 通り。$4\times 4\times 3=48$ 個。奇数($⟺$ 一の位が $1$ か $3$)を数える。一の位が奇数($2$ 通り)。百の位は $0$ と一の位を除く $3$ 通り、十の位は残り $3$ 通り。$2\times 3\times 3=18$ 個。

偶数 $=48-18=30$ 個。一の位で場合分けする本解と同じ $30$ だが、「総数 $-$ 奇数」で攻めると、奇数の一の位($1,3$ で $0$ を含まない)は場合分けが $1$ 通りで済み、$0$ の制約が絡まない分すっきりする。$48$ 個中、偶数 $30$・奇数 $18$ の内訳も見える。

方針

解答

⓪ 発想(どう考え始めるか) 「$1$ が $1$ 番目・$2$ が $2$ 番目・$3$ が $3$ 番目のいずれもない」を直接数えるのは難しい。反対(少なくとも $1$ つ起こる)を包除で数える。

$A_k$ を「数 $k$ が $k$ 番目に来る並べ方」の集合とする($k=1,2,3$)。$|A_1\cup A_2\cup A_3|$ を包除原理で。$j$ 個の位置を固定すると、残り $6-j$ 個は自由で $(6-j)!$ 通り。$|A_1\cup A_2\cup A_3|=\left(\genfrac{}{}{0ex}{}{3}{1}\right)5!-\left(\genfrac{}{}{0ex}{}{3}{2}\right)4!+\left(\genfrac{}{}{0ex}{}{3}{3}\right)3!$。全体 $6!$ から引く。

① 部品を用意する。 $A_i$ を「数 $i$ が $i$ 番目に来る並べ方」とする($i=1,2,3$)。$k$ 個の条件を同時に満たす($k$ 個を定位置に固定)並べ方は、残り $6-k$ 個の並べ方で $(6-k)!$ 通り。

• $|A_i|=5!=120$($3$ 個)
• $|A_i\cap A_j|=4!=24$(${}_3{\mathrm{C}}_2=3$ 組)
• $|A_1\cap A_2\cap A_3|=3!=6$($1$ 組)

② 少なくとも $1$ つ起こる数(包除)。

$$|A_1\cup A_2\cup A_3|=3\cdot 120-3\cdot 24+6=360-72+6=294$$

③ 全体から引く。

$$6!-294=720-294=426\text{通り}$$

まとめ:「どの条件も成り立たない」は「全体 − 少なくとも $1$ つ成り立つ」。重なりを足し引きする包除原理が要。$k$ 個を定位置に固定すると残りは自由に $(6-k)!$、という部品を、条件の個数ごとに符号を変えて足し合わせる。

発展。 全 $n$ か所に「$k$ 番目に $k$ が来ない」を課すと完全順列 $D_n=n!{\sum }_{j=0}^n\frac{(-1{)}^j}{j!}$。本問は $3$ か所だけの制限。「禁止位置」が任意に散らばる一般の問題は、禁止を表す盤面(ルーク多項式)で数えられ、包除原理の項がその盤面の配置数になる。

別解

別解:完全順列(かく乱順列)の一般化として捉える(得意な人向けの視点)。 「$k$ 番目に $k$ が来ない」($k=1,2,3$)だけを課し、$4,5,6$ は自由。これは「$3$ か所に禁止がある順列」で、包除原理の一般形で書ける。

禁止の集合 $A_1,A_2,A_3$ に対し、求める数は

$$\sum _{j=0}^3(-1{)}^j(\genfrac{}{}{0ex}{}{3}{j})(6-j)!=6!-3\cdot 5!+3\cdot 4!-3!=720-360+72-6=426.$$

$j$ 個の位置を「$k$ が $k$ 番目」に固定すると、残り $6-j$ 個が自由で $(6-j)!$、その選び方が $\left(\genfrac{}{}{0ex}{}{3}{j}\right)$、符号が $(-1{)}^j$。

もし全 $6$ か所に「$k$ 番目に $k$ が来ない」を課せば、完全順列 $D_6=265$。本問は $3$ か所だけの制限なので、$4,5,6$ の分だけ自由度が増え $426$ になる。「一部の位置にだけ禁止」の順列は包除の項数を禁止の数に合わせるだけで数えられる。

方針

解答

⓪ 発想(どう考え始めるか) 弦の交点を $1$ つずつ数えるのは無理。交点と何かを $1$ 対 $1$ に対応させる。

円の内部の交点 $1$ つは、それを作る $2$ 本の弦で決まる。その $2$ 本の弦の端点は円周上の $4$ 点。逆に、円周上の $4$ 点を選ぶと、それらを頂点とする凸四角形の対角線がちょうど $1$ 点で交わる。

だから「交点」と「円周上の $4$ 点の組」がぴったり $1$ 対 $1$。交点の個数 $=$「$10$ 点から $4$ 点を選ぶ」$=\left(\genfrac{}{}{0ex}{}{10}{4}\right)=210$。

① 対応を確認する。 円周上の $4$ 点を選ぶと、それらを頂点とする四角形ができ、その $2$ 本の対角線が円の内部でちょうど $1$ 点で交わる。逆に、内部の交点はどれも $2$ 本の弦の交わりで、$4$ 個の端点を持つ。

② 組合せで数える。 どの $3$ 本の弦も同じ点で交わらないので、交点はすべて別々。よって交点の個数は「$10$ 点から $4$ 点を選ぶ」組合せに等しい:

$${}_{10}{\mathrm{C}}_4=\frac{10\cdot 9\cdot 8\cdot 7}{4\cdot 3\cdot 2\cdot 1}=210\text{個}$$

まとめ:交点を「$4$ 点の選び方」に言い換えれば解ける。ごちゃごちゃした弦の交わりを直接数えず、$1$ 対 $1$ 対応で ${}_{10}{\mathrm{C}}_4$ という組合せに帰着させる。「どの $3$ 弦も $1$ 点で交わらない」の条件は、交点がダブらない(=最大になる)ことを保証している。

発展。 円周上 $n$ 点の弦の交点数は $\left(\genfrac{}{}{0ex}{}{n}{4}\right)$(一般の位置で)。同じ $n$ 点で、弦が円を分ける領域の数は $\left(\genfrac{}{}{0ex}{}{n}{4}\right)+\left(\genfrac{}{}{0ex}{}{n}{2}\right)+1$(オイラーの公式から)。$4$ 点から $1$ 交点、という対応が、これらの数え上げの共通の核。組合せ論では「何と何が $1$ 対 $1$ に対応するか」を見抜けるかどうかが、多くの問題の決め手になる。

別解

別解:対角線の交点として凸多角形で数える(視覚で納得するルート)。 円周上の $10$ 点を頂点とする凸 $10$ 角形を考える。弦はすべて、この $10$ 角形の辺または対角線だ。内部の交点は「対角線どうしの交点」そのものである。

凸多角形で「$2$ 本の対角線が内部で交わる」$⟺$「その $4$ つの端点が凸四角形をなす」。逆に、任意の $4$ 頂点を選ぶと、それらを頂点とする凸四角形の $2$ 本の対角線がちょうど $1$ 点で交わる。だから交点と「$4$ 頂点の組」が $1$ 対 $1$。

$$(\text{交点数})=\left(\genfrac{}{}{0ex}{}{10}{4}\right)=210.$$

弦の交点を弦のペアで数える本解と同じだが、「凸四角形の対角線交点」と読むと、$4$ 点を選べば交点が $1$ つ確定する対応が図で見える。「どの $3$ 本の弦も $1$ 点で交わらない」という条件は、この $1$ 対 $1$ 対応を保証するためのもの($3$ 本が $1$ 点で交わると $\left(\genfrac{}{}{0ex}{}{4}{3}\right)=3$ 個の交点が $1$ 個に重なってしまう)。