【第12章】「場合の数」のいちばん大切なこと──数えるとは1対1対応

数強塾オリジナル無料講座『数学の原理』第12章
「場合の数」は、公式を覚える単元だと思われています。\({}_n \mathrm{P}_r\)、\({}_n \mathrm{C}_r\)、円順列、重複順列……。でも、いちばん大切なことは公式ではありません。数えるとは、1対1の対応をつけることである。これが腹に落ちると、\({}_n \mathrm{C}_r\) をなぜ \(r!\) で割るのかも、自分の言葉で説明できるようになります。

「数える」とは、そもそも何をしているのか

藤原です。第12章です。

目の前にリンゴが並んでいます。あなたはそれを数える。「1、2、3、4、5個」。

このとき、あなたは何をしたでしょうか。

リンゴを1つずつ指さして、\(1, 2, 3, 4, 5\) という番号を1個ずつ、もれなく、だぶりなく割り当てました。そして最後の番号が5だったから「5個」。

数えるとは、数えたいものと \(\{1, 2, \ldots, n\}\) との間に、1対1の対応をつけることである。

当たり前すぎて拍子抜けしたかもしれません。でも、この見方が強力なんです。なぜなら

2つの集合の間に1対1の対応がつけば、個数は等しい。
だから、数えにくいものを、数えやすいものに”翻訳”すれば勝ち。

これがこの章の主題です。公式を思い出せなくても、対応さえ作れれば数えられます。

まずは2つの法則──「または」と「かつ」

第1章でやった「または」「かつ」が、そのまま数え上げの2大法則になります。

【和の法則】　場合を重なりなく2つに分けられるなら、それぞれ数えて足す。
（集合でいえば \(A \cap B = \varnothing\) のとき \(|A \cup B| = |A| + |B|\)）

【積の法則】　選択を順に行い、前の選び方によらず後の選択肢の数が一定なら、掛ける。

和の法則で最重要なのは「重なりなく」の部分です。重なりがあると、二重に数えてしまう。第1章で「または」を扱ったとき、「両方でもよい」と注意しましたね。数えるときは、その「両方」を引く必要があります。

\[|A \cup B| = |A| + |B| – |A \cap B|\]

これがいわゆる包除原理です。「重なりを引く」だけの、素朴な話です。

積の法則で注意すべきは「前の選び方によらず」の部分です。たとえば「5人から委員長と副委員長を選ぶ」なら、委員長を5通り選んだあと、副委員長は残り4人から。委員長が誰であっても、副委員長の選択肢は必ず4通り。だから \(5 \times 4\) と掛けられる。

もし「前の選び方によって、後の選択肢の数が変わる」なら、掛け算はできません。そのときは場合分けして和の法則です。

順列は、積の法則そのもの

\(n\) 個から \(r\) 個を選んで並べる方法の数を \({}_n \mathrm{P}_r\) と書きます。

1番目には \(n\) 通り、2番目には残りから \(n-1\) 通り、……、\(r\) 番目には \(n-r+1\) 通り。積の法則で

\[{}_n \mathrm{P}_r = n(n-1)(n-2) \cdots (n-r+1) = \frac{n!}{(n-r)!}\]

公式というより、数えた結果をそのまま書いただけです。だから忘れても、その場で作れます。

組合せ──なぜ \(r!\) で割るのか

ここが、この章のいちばん大事なところです。

\(n\) 個から \(r\) 個を選ぶだけ（並べない）方法の数を \({}_n \mathrm{C}_r\) と書きます。そして

\[{}_n \mathrm{C}_r = \frac{{}_n \mathrm{P}_r}{r!}\]

この「\(r!\) で割る」を、丸暗記していませんか。理由はこうです。

たとえば5人 A, B, C, D, E から3人を選ぶとします。「A, B, C を選ぶ」という1つの選び方に対して、それを並べる方法は

\[\mathrm{ABC},\ \mathrm{ACB},\ \mathrm{BAC},\ \mathrm{BCA},\ \mathrm{CAB},\ \mathrm{CBA}\]

の \(3! = 6\) 通りあります。他のどの3人組についても、やはり6通り。

つまり、「並べたもの全体」と「選んだもの全体」の間には、6対1の対応がある。
6個ずつ束にすると、束の個数が「選び方の数」になる。だから \(6 = 3!\) で割る。

これを一般化すると、数え上げで最強の原理が手に入ります。

【\(k\) 対1対応の原理】
数えたいもの1つに対して、数えやすいものが必ず \(k\) 個ずつ対応しているなら、
（数えたいものの個数）＝（数えやすいものの個数）÷ \(k\)

「必ず \(k\) 個ずつ」というのが命です。個数が場合によってバラバラなら、この原理は使えません。割り算をするときは、いつも「本当に均等に重複しているか」を確認してください。

この原理だけで、公式が次々に出てくる

円順列

\(n\) 人が円形に並ぶ方法の数。まず一列に並べると \(n!\) 通り。でも円形では、全員が同時に1つずつずれた並びは同じとみなします。1つの円の並びに対して、一列の並びは \(n\) 通り（どこを先頭にするかで \(n\) 通り）。

だから \(n\) 対1対応です。

\[\frac{n!}{n} = (n-1)!\]

じゅず順列

ネックレスのように裏返しても同じとみなす場合。円順列の並びが、裏返しでさらに2個ずつ同じになるので

\[\frac{(n-1)!}{2} \qquad (n \ge 3)\]

同じものを含む順列

たとえば「あかいかい」の5文字を並べ替える方法。全部区別すれば \(5!\) 通りですが、「あ」が1個、「か」が2個、「い」が2個。同じ文字どうしを入れ替えても見た目が同じなので、\(2! \times 2!\) 個ずつ重複しています。

\[\frac{5!}{1! \, 2! \, 2!} = \frac{120}{4} = 30\]

3つの公式が、全部「\(k\) 対1対応で割る」という同じ操作でした。覚えることは1つで済みます。

対応づけの本領──「翻訳」で数える

ここからが応用です。まったく別の問題に翻訳してしまうという技を見ます。

例題　碁盤の目状の道路がある。左下の点 A から右上の点 B まで、右または上にだけ進んで行く最短経路は何通りあるか。ただし横に3区画、縦に2区画とする。

ふつうに数えようとすると大変です。でも、経路を文字列に翻訳してみてください。

右に進むことを「→」、上に進むことを「↑」と書くと、A から B へ行くには必ず「→」を3回、「↑」を2回使います（順序は自由）。逆に、「→」3個と「↑」2個を並べた文字列を作れば、それに対応する経路がちょうど1つ決まります。

最短経路　⟷　「→」3個と「↑」2個を並べた列
この対応は1対1。だから、個数は等しい。

あとは「同じものを含む順列」です。

\[\frac{5!}{3! \, 2!} = \frac{120}{12} = 10\]

答え：10通り

あるいは「5つの場所のうち、どこを『↑』にするか」を選ぶと考えて \({}_5 \mathrm{C}_2 = 10\) でも同じです。見方は複数あっても、対応が正しければ答えは一致します。

この「翻訳」こそが、場合の数の本体です。
難しい数え上げ問題は、ほぼ例外なく「別のものに翻訳できないか」を問うています。翻訳先の定番は①文字列 ②○と|（仕切り） ③数の組の3つ。次章で徹底的に扱います。

数え上げの3つの方針

整理しておきます。数える方法は、大きく3つです。

① 素直に数える（積の法則・和の法則）
② 全体から引く（余事象。「少なくとも1つ」に強い）
③ 別のものに翻訳する（1対1対応・\(k\) 対1対応）

②について一言。第3章・第8章でやったとおり、「少なくとも1つ〜」は否定すると「すべて〜でない」になって扱いやすくなります。数え上げでも同じで、「少なくとも1個は当たり」は「全部はずれ」を全体から引くのが定石です。

【原理】この章の芯

① 数えるとは、1対1の対応をつけること。
② 対応がつけば個数は等しい。だから数えやすいものに翻訳すればよい。
③ 和の法則は「重なりなく」、積の法則は「選択肢の数が一定」が命。
④ \(k\) 個ずつ均等に重複しているなら、\(k\) で割る。円順列も組合せも同じ原理。
⑤ 方針は3つ：素直に数える／全体から引く／翻訳する。

オリジナル問題で確かめる

問題1（積の法則・和の法則）

1. 大中小3個のさいころを投げるとき、目の出方は何通りか。
2. 1から100までの整数のうち、3の倍数または5の倍数であるものは何個か。

問題2（順列・組合せの基本）

8人の生徒がいる。

1. この中から委員長・副委員長・書記を1人ずつ選ぶ方法は何通りか。
2. この中から3人の委員を選ぶ方法は何通りか。
3. (1) と (2) の答えの比が \(3!\) になる理由を、対応の言葉で説明せよ。

問題3（対応で等式を説明する）

次の等式が成り立つ理由を、計算ではなく「対応」の言葉で説明せよ。

\[{}_n \mathrm{C}_r = {}_n \mathrm{C}_{n-r}\]

問題4（円順列・じゅず順列）

1. 6人が円形のテーブルに座る方法は何通りか。
2. 異なる6個の玉でネックレスを作る方法は何通りか。
3. 6人が円形に座るとき、特定の2人 A, B が隣り合う座り方は何通りか。

問題5（同じものを含む順列）

「すうきょうじゅく」の8文字をすべて並べ替えてできる文字列は何通りか。ただし「う」が2個、「く」が2個、他の文字（す・き・ょ・じ・ゅ）は1個ずつとする。

問題6（最短経路）

横に5区画、縦に3区画の碁盤の目がある。左下 A から右上 B への最短経路について答えよ。

1. 全部で何通りか。
2. ある特定の交差点 P（A から右に2区画、上に1区画の位置）を通る経路は何通りか。
3. P を通らない経路は何通りか。

問題7（余事象）

10本のくじの中に当たりが3本ある。この中から同時に3本引くとき、少なくとも1本が当たりである引き方は何通りか。

問題8（翻訳して数える）

1から10までの番号が付いた10個の席が一列に並んでいる。この中から3席を選ぶとき、選んだどの2席も隣り合わないような選び方は何通りか。

問題9（パスカルの関係式を対応で）

\(1 \le r \le n-1\) のとき、次の等式が成り立つ。この等式が成り立つ理由を、対応の言葉で説明せよ。

\[{}_n \mathrm{C}_r = {}_{n-1} \mathrm{C}_{r-1} + {}_{n-1} \mathrm{C}_r\]

解答と解説

問題1の解答

(1)　3個のさいころは区別できるので、それぞれ6通り。積の法則より

\[6 \times 6 \times 6 = 216\]

答え：216通り

(2)　3の倍数は \(\lfloor 100/3 \rfloor = 33\) 個、5の倍数は \(20\) 個。ただし両方の倍数（15の倍数）を二重に数えているので引きます。15の倍数は \(\lfloor 100/15 \rfloor = 6\) 個。

\[33 + 20 – 6 = 47\]

答え：47個

和の法則をそのまま使うと \(33+20 = 53\) となって間違います。「または」で数えるときは、必ず重なりを確認してください。

問題2の解答

(1)　役職が違うので、並べる問題です。\({}_8 \mathrm{P}_3 = 8 \times 7 \times 6 = 336\)。336通り。

(2)　役職がないので、選ぶだけ。\({}_8 \mathrm{C}_3 = \dfrac{336}{6} = 56\)。56通り。

(3)　「3人の組」を1つ決めると、その3人に3つの役職を割り当てる方法が \(3! = 6\) 通りあります。逆に役職つきの選び方が決まれば、3人の組は1つに決まります。

つまり、「役職つきの選び方」と「3人の組」の間には6対1の対応があります。だから (1) は (2) のちょうど \(3!\) 倍になるのです。

問題3の解答

\(n\) 個から \(r\) 個を選ぶことは、「残りの \(n-r\) 個を選ぶこと」と同じです。

もっと丁寧に言えば、「選んだ \(r\) 個の組」に対して「選ばれなかった \(n-r\) 個の組」を対応させます。この対応は

• 異なる選び方には異なる残りが対応する（だぶりなし）
• どんな \(n-r\) 個の組も、その補集合を選んだ結果として現れる（もれなし）

ので、1対1の対応です。1対1対応があるので個数は等しく、\({}_n \mathrm{C}_r = {}_n \mathrm{C}_{n-r}\)。

計算で示すこともできますが、対応で説明したほうが「なぜ」が伝わります。そして、この見方は「\({}_{100} \mathrm{C}_{98}\) を計算せよ」のような場面で、実際に手を軽くしてくれます（\({}_{100} \mathrm{C}_2 = 4950\) と読み替えられる）。

問題4の解答

(1)　\((6-1)! = 120\)。120通り。

(2)　円順列を裏返しで2個ずつ同一視するので \(\dfrac{120}{2} = 60\)。60通り。

(3)　A と B を1人分の”かたまり”とみなします。すると5個のものの円順列なので \((5-1)! = 24\) 通り。さらに、かたまりの中で A と B の並び方が \(2! = 2\) 通り。

\[24 \times 2 = 48\]

答え：48通り

「隣り合う」＝「くっつけて1つとみなす」。これも一種の翻訳です。問題の設定を、扱いやすい設定に置き換えているわけです。

問題5の解答

全8文字のうち「う」が2個、「く」が2個、残り4文字は1個ずつ。同じ文字どうしの入れ替えで重複するので

\[\frac{8!}{2! \, 2!} = \frac{40320}{4} = 10080\]

答え：10080通り

別の見方もできます。「8つの位置のうち、どの2つを『う』にするか」で \({}_8 \mathrm{C}_2 = 28\) 通り、「残り6つのうち、どの2つを『く』にするか」で \({}_6 \mathrm{C}_2 = 15\) 通り、残り4つに4種類の文字を並べて \(4! = 24\) 通り。

\[28 \times 15 \times 24 = 10080\]

一致しました。2通りの数え方で同じ答えが出たら、それは強力な検算です。

問題6の解答

(1)　「→」5個と「↑」3個、計8個の並べ方なので

\[\frac{8!}{5! \, 3!} = {}_8 \mathrm{C}_3 = 56\]

答え：56通り

(2)　「A から P へ」と「P から B へ」に分けます（積の法則）。

• A → P：「→」2個と「↑」1個　→　\({}_3 \mathrm{C}_1 = 3\) 通り
• P → B：残りは「→」3個と「↑」2個　→　\({}_5 \mathrm{C}_2 = 10\) 通り

\[3 \times 10 = 30\]

答え：30通り

ここで積の法則が使える理由も確認しておきましょう。A→P の行き方が何であっても、P→B の行き方の数は必ず10通り。前の選択が後の選択肢の数に影響しないので、掛けられます。

(3)　全体から (2) を引きます（余事象）。

\[56 – 30 = 26\]

答え：26通り

「通らない」を直接数えるのは大変です。「〜でない」を見たら、まず全体から引くことを考える。これは第8章の背理法と同じ発想ですね。

問題7の解答

「少なくとも1本当たり」を直接数えると、1本の場合・2本の場合・3本の場合に分けることになって面倒です。余事象を使います。

全体：10本から3本を選ぶ方法は \({}_{10} \mathrm{C}_3 = 120\) 通り。

余事象（1本も当たらない＝はずれ7本から3本選ぶ）：\({}_{7} \mathrm{C}_3 = 35\) 通り。

\[120 – 35 = 85\]

答え：85通り

検算のために直接数えてみましょう。当たり1本：\({}_3\mathrm{C}_1 \times {}_7\mathrm{C}_2 = 3 \times 21 = 63\)。当たり2本：\({}_3\mathrm{C}_2 \times {}_7\mathrm{C}_1 = 3 \times 7 = 21\)。当たり3本：\({}_3\mathrm{C}_3 = 1\)。合計 \(63+21+1 = 85\)。一致します。

問題8の解答

この問題こそ「翻訳」の出番です。

選んだ3席を \(a \lt b \lt c\) とします。「隣り合わない」という条件は

\[b – a \ge 2, \qquad c – b \ge 2\]

です。この不等号が扱いにくい。そこで、新しい変数に翻訳します。

\[a’ = a, \qquad b’ = b – 1, \qquad c’ = c – 2\]

とおくと、条件は

\[a’ \lt b’ \lt c’\]

というただの大小関係になります（\(b’ – a’ = b-a-1 \ge 1\)、\(c’-b’ = c-b-1 \ge 1\) なので）。

そして \(a’ \ge 1\)、\(c’ = c – 2 \le 10 – 2 = 8\) なので、\(a’,\ b’,\ c’\) は \(1\) から \(8\) までの相異なる3つの数です。

逆に、\(1\) から \(8\) までの相異なる3数 \(a’ \lt b’ \lt c’\) を取れば、\(a = a’,\ b = b’+1,\ c = c’+2\) として条件を満たす席の組が1つ決まります。1対1対応です。

\[{}_8 \mathrm{C}_3 = 56\]

答え：56通り

検算のため、小さい場合で確かめましょう。席が5、選ぶのが2席なら、この方法では \({}_4\mathrm{C}_2 = 6\) 通り。実際に列挙すると \((1,3),(1,4),(1,5),(2,4),(2,5),(3,5)\) の6通り。一致します。

この「ずらして翻訳する」技は、隣り合わない条件の定番です。別解として「まず選ばない7席を並べ、その間の8か所の隙間から3か所を選ぶ」と考えても \({}_8\mathrm{C}_3\) が出ます。どちらも同じ対応を、違う言葉で説明しているだけです。

問題9の解答

\(n\) 個のものから \(r\) 個を選ぶ、という状況を考えます。ここで特定の1個（これを「太郎くん」と呼びます）に注目し、太郎くんを選ぶか選ばないかで場合分けします。

• 太郎くんを選ぶ場合：残り \(n-1\) 個から、あと \(r-1\) 個を選べばよい。\({}_{n-1}\mathrm{C}_{r-1}\) 通り。
• 太郎くんを選ばない場合：太郎くん以外の \(n-1\) 個から \(r\) 個を選ぶ。\({}_{n-1}\mathrm{C}_{r}\) 通り。

この2つの場合は重なりがなく（太郎くんを選ぶか選ばないかは同時に起こらない）、もれもない（どちらかには必ず入る）ので、和の法則が使えます。

\[{}_n \mathrm{C}_r = {}_{n-1} \mathrm{C}_{r-1} + {}_{n-1} \mathrm{C}_r\]

（説明終）

これがパスカルの三角形の作り方（上の2つを足すと下ができる）の理由です。階乗の式を通分して計算しても示せますが、この説明のほうが「なぜ」が見えます。

ちなみにこの式は漸化式でもあります。第11章でやった「1つに注目して場合を尽くす」という漸化式の立て方が、そのままここでも効いていますね。

よくある誤解

誤解1：和の法則で重なりを確認しない
「または」で数えるときは、必ず重なりを引いてください（包除原理）。

誤解2：選択肢の数が変わるのに掛け算する
積の法則は「前の選び方によらず、後の選択肢が一定」のときだけ使えます。変わるなら場合分けです。

誤解3：重複が均等でないのに割る
\(k\) で割れるのは「必ず \(k\) 個ずつ重複している」ときだけ。円順列で「全員同じ」のような特殊な場合が混ざると、この前提が崩れます。

誤解4：区別するかしないかを曖昧にしたまま数える
「3個のさいころ」は区別する、「3個の同じ玉」は区別しない。数え始める前に、何を同じとみなすかを決めてください。ここが場合の数で最大の事故ポイントです。

よくある質問

Q. P と C の使い分けが分かりません。

並べたら P、選ぶだけなら C。判断の基準は「順番を変えたら別のものになるか」です。委員長と副委員長は入れ替えたら別（P）、ただの委員2人は入れ替えても同じ（C）。迷ったら、小さい数で実際に書き出してみてください。

Q. 場合の数の問題で、どこから手をつければいいですか？

まず小さい場合を手で書き出す。これに尽きます。「3個ならどうなるか」を実際に列挙すると、構造が見えて対応が思いつきます。いきなり公式に当てはめようとするのがいちばん危険です。

Q. 答えが合っているか不安なときは？

別の方法でもう一度数えてください。問題5や問題7でやったように、2通りの数え方で同じ答えが出れば、まず間違いありません。場合の数は検算が効きにくい分野なので、この習慣が効きます。

次の章へ

「数えるとは対応をつけること」が手に入りました。次の第13章では、この対応づけを技術のレベルまで引き上げます。○と仕切り棒、重複組合せ、そして「同じものを配る」問題。難関大が好んで出す数え上げの型を、すべて対応で処理します。

◀ 第11章：漸化式は「関係」でしかない──解く型より作る型
▶ 第13章：数え上げの技術──重複・仕切り・対応づけ
▶ 『数学の原理』全24章の目次に戻る