場合の数 ★ 基礎の問題 全12問

方針

解答

⓪ 発想(どう考え始めるか) 犬 $22$ 人と猫 $15$ 人を単純に足すと $37$ 人。しかしクラスは $40$ 人で、犬も猫も飼う $8$ 人はどちらにも入っている。

足すと、両方飼っている $8$ 人を $2$ 回数えてしまう。だから $1$ 回ぶん引く。

$$n(A\cup B)=n(A)+n(B)-n(A\cap B)$$

これが個数定理だ。「足しすぎたぶんを引く」、それだけの話である。

(2)は「犬または猫」の反対だから、全体から引く。$40$ 人から $29$ 人を引いて $11$ 人。困ったらベン図を描いて、$4$ つの部屋の人数を書き込む。それが一番確実な方法だ。

まず図をかいて、重なりの部分に「8人」と書き込もう。

(1) 犬または猫を飼っている人

「または」は、2つの輪を合わせた全体のことだ。そのまま足すと $22+15=37$ 人。でも、これでは多すぎる。重なっている8人を、犬のほうでも猫のほうでも数えていて、2回分になっているからだ。だから8人を1回だけ引く。

$$n(A\cup B)=n(A)+n(B)-n(A\cap B)=22+15-8=29(\text{人})$$

($A$ は犬を飼う人、$B$ は猫を飼う人。$n(A\cup B)$ は「どちらか一方でも飼っている人の数」を表す記号だと思えばよい。)

(2) どちらも飼っていない人

クラスは全部で40人。そのうち「犬か猫を飼っている人」が(1)で求めた29人だった。残りが「どちらも飼っていない人」になる。

$$40-n(A\cup B)=40-29=11(\text{人})$$

まとめ:最後に図で確かめよう。犬だけの人は $22-8=14$ 人、猫だけの人は $15-8=7$ 人、両方が8人、どちらも飼わない人が11人。全部足すと $14+7+8+11=40$ 人。確かに40人になった。合っている。

発展。 集合が $3$ つになると、公式はこうなる。

$$n(A\cup B\cup C)=n(A)+n(B)+n(C)-n(A\cap B)-n(B\cap C)-n(C\cap A)+n(A\cap B\cap C)$$

足す → 引く → また足すと符号が交互に入れかわる。これを包除原理という。

理由はベン図の真ん中の部屋を追えば分かる。$3$ つ全部に属する人は、最初の $3$ 項で $3$ 回数えられ、次の $3$ 項で $3$ 回引かれて $0$ 回になってしまう。だから最後に $1$ 回足し戻す。数えすぎと引きすぎを、交互に修正していく。

この「足しては引く」という発想は、確率(少なくとも $1$ つ起こる確率)や整数(倍数の個数の数え上げ)でもよく使われる。数え上げの基礎にある原理であり、$n$ 個の集合まで一般化される。$2$ つの場合の $-n(A\cap B)$ は、その最初の一歩だ。

別解

公式を使わず、$4$ つの部屋の人数を全部埋めるやり方を身につけよう。ベン図を描くと、クラスは必ず次の $4$ 種類に分かれる。

• 犬だけ飼っている人
• 猫だけ飼っている人
• 両方飼っている人
• どちらも飼っていない人

両方から埋めるのがコツ。 分かっているのは「両方 $=$ $8$ 人」。ここが交わりだ。

犬だけは、犬 $22$ 人から両方の $8$ 人を除いて

$$22-8=14(\text{人})$$

猫だけは、猫 $15$ 人から両方の $8$ 人を除いて

$$15-8=7(\text{人})$$

ここまでで、何かを飼っている人は $14+8+7=29$ 人。これが(1)の答えである。残りのどちらも飼っていない人は

$$40-29=11(\text{人})$$

これが(2)の答え。 $4$ つの部屋は $14,7,8,11$ で、合計は $14+7+8+11=40$ となり、クラスの人数とぴったり合う。この検算ができるのが、この方法の強みだ。

表にすると、さらに見通しがよい。

縦・横のどの合計も、確かに辻褄が合う。 $2\times 2$ のマスのうち $1$ つと、周りの合計が分かれば、残りは引き算だけで全部決まるのだ。

この表は分割表と呼ばれ、アンケート集計の現場でそのまま使われている。公式 $n(A\cup B)=n(A)+n(B)-n(A\cap B)$ は、この表の「$8$ を二重に数えた」という事実を式にしただけ。式を忘れても、表を描けば必ず解ける。

方針

解答

⓪ 発想(どう考え始めるか) 「すべて書き上げよ」と言われている。数え上げの出発点はもれなく・重なりなく並べることだ。

そのためには順番のルールを決めて機械的に書く。硬貨の順番を「$100$ 円 → $10$ 円 → $5$ 円」と固定し、表を先・裏を後にして、辞書のように並べていく。

$$\text{表表表},\text{表表裏},\text{表裏表},\text{表裏裏},\text{裏表表},\dots$$

思いつくままに書くと、必ずどこかでもれるか、ダブる。「決めた順に書く」だけで、数え上げは正確になる。

樹形図を描けば、枝が $2\to 4\to 8$ と広がる様子が目に見える。$8$ 通りという答えの「かたち」まで分かるはずだ。

硬貨を100円→10円→5円の順に見て、表を「オ」、裏を「ウ」と書くことにする。100円が表の場合を先に全部、次に裏の場合を全部、という順で並べると

$$(\text{オ},\text{オ},\text{オ}),(\text{オ},\text{オ},\text{ウ}),(\text{オ},\text{ウ},\text{オ}),(\text{オ},\text{ウ},\text{ウ}),$$

$$(\text{ウ},\text{オ},\text{オ}),(\text{ウ},\text{オ},\text{ウ}),(\text{ウ},\text{ウ},\text{オ}),(\text{ウ},\text{ウ},\text{ウ})$$

の8通りだ。なぜ数え落としがないと言えるかというと、「100円が表」の場合で前半4つ、「100円が裏」の場合で後半4つ、と場合をきちんと分けて並べたからだ。

まとめ:慣れてくれば、各硬貨が2通りずつだから $2\times 2\times 2=8$ 通り、と計算でも出せる。でも最初のうちは、こうして自分の手で全部書き出して「たしかに8通りだ」と目で確かめるのが大事だ。

発展。 表の枚数ごとの内訳 $1,3,3,1$ を足すと $8=2^3$ になった。これは偶然ではない。

$$\sum _{k=0}^n{}_n{\mathrm{C}}_k=2^n$$

「$n$ 個から何個か選ぶ選び方を全部足すと $2^n$」 と読める。左辺は「選ぶ個数で分類して数えた」もの、右辺は「各要素について入れる・入れないの $2$ 択が $n$ 回」と数えたものだ。同じものを $2$ 通りに数えたから等号が成り立つ。

この「$1$ つのものを $2$ 通りに数えて等式を作る」という手口は二重数え上げと呼ばれ、組合せ論でよく使われる証明法である。二項定理 $(1+1{)}^n=\sum {}_n{\mathrm{C}}_k$ からも同じ式が出る。

$3$ 枚の硬貨という素朴な設定を $n$ 枚に一般化すると、この等式が得られる。具体例を丁寧に観察することが、一般法則を見つける手がかりになる。

別解

書き上げた $8$ 通りを、別の目で読み直す。ここに、これから学ぶ「場合の数」のほとんどの種が入っている。見方1: かけ算で出す(積の法則)。

$100$ 円硬貨の出方は $2$ 通り。そのそれぞれについて $10$ 円硬貨が $2$ 通り。さらにそのそれぞれについて $5$ 円硬貨が $2$ 通り。

$$2\times 2\times 2=8(\text{通り})$$

樹形図の枝の本数がそのままかけ算になっている。「$3$ 枚あるから $3$ 倍」ではなく「$2$ 通りが $3$ 回」だから $2^3$。ここを取り違えないこと。

見方2: $2$ 進数として読む。 表を $1$、裏を $0$ と書くと、$8$ 通りはこうなる。

$$000,001,010,011,100,101,110,111$$

これは $0$ から $7$ までの数を $2$ 進法で書いたものだ。$3$ 桁の $2$ 進数は $2^3=8$ 個。硬貨の表裏を数えることと、コンピュータが $3$ ビットで数を表すことは、まったく同じ数え上げである。

見方3: 「表が何枚か」で分類する。 $8$ 通りを、表の枚数ごとに数える。

合計は $1+3+3+1=8$。この $1,3,3,1$ という並びに見覚えはないだろうか。パスカルの三角形の $3$ 段目だ。「$3$ 枚のうち表になる $2$ 枚を選ぶ」から $3$ 通りで、これは後で学ぶ組合せ${}_3{\mathrm{C}}_2=3$ と同じである。

同じ $8$ を、$3$ つの目で見た。 積の法則、重複順列($2^3$)、組合せの和である。書き上げた $8$ 通りの中に、単元全体の設計図が入っている。数え上げに詰まったら、いつでも「全部書き出す」に戻ってよい。公式はその作業を速くするための道具にすぎない。

方針

解答

⓪ 発想(どう考え始めるか) 「たすのか、かけるのか」は、場合の数で最初に迷うところだ。見分け方は $1$ つ。

「$3$ つとも選ぶ(かつ)」ならかける。「どれか $1$ 品だけ(または)」ならたす。

(1)は前菜も主菜もデザートも選ぶ。前菜 $3$ 通りのそれぞれについて主菜が $4$ 通り、そのそれぞれについてデザートが $2$ 通りある。枝が枝分かれしていくのでかけ算になる。

(2)は主菜かデザート、どちらか一方だけ。$1$ 品しか選ばないのだから、選択肢は主菜の $4$ 種類とデザートの $2$ 種類を並べただけ。重なりもない($1$ つの料理が主菜でもデザートでもある、ということはない)。だからたし算。

「かつ」か「または」かを、問題文の日本語を読み直して確かめる。それが最初の一手である。

(1) 前菜の選び方は3通り。その1つ1つに対して主菜が4通りずつ、さらにその1つ1つに対してデザートが2通りずつある。続けて選んでいくので、数をかけていく。

$$3\times 4\times 2=24(\text{通り})$$

イメージとしては、前菜3本の枝がそれぞれ主菜4本に分かれ、さらにデザート2本に分かれる木を思い浮かべるとよい。枝の先の数がかけ算になる。

(2) 今度は1品だけ選ぶ。それが主菜のときとデザートのときは、同時には起きない(1品だけだから)。こういうときはたす。

$$4+2=6(\text{通り})$$

(1)でかけて(2)でたした違いは、「続けて選ぶ(かけ算)」か「どちらか一方だけ(たし算)」かの1点だけだ。問題文の「1品ずつ」と「どれか1品だけ」を読み分けよう。

発展。 積の法則には、見落としやすい条件がある。「前菜を選んだ結果、主菜の選択肢が減る」ようなことが起きない、という前提だ。

もし「和風の前菜を選んだら、主菜は和食 $2$ 種類からしか選べない」というルールがあれば、単純な $3\times 4$ は使えない。場合分けして、それぞれで積の法則を使い、最後に足すことになる。

$$(\text{全体})=(\text{和風前菜のとき})+(\text{洋風前菜のとき})+\cdots$$

積の法則で数え、和の法則でつなぐ。複雑な数え上げはたいていこの組合せでできている。順列 ${}_n{\mathrm{P}}_r=n(n-1)\cdots$ も「$1$ 人選ぶごとに候補が $1$ 人減る」という変化する選択肢を積の法則で扱ったものだ。

「$1$ 段目を決めたとき、$2$ 段目の選択肢は何通りか」を毎回きちんと確かめることが大事だ。それが一定なら単純なかけ算、変わるなら場合分け。この問いを飛ばさなければ、数え間違いが減る。

別解

かけ算とたし算の違いを、絵で見て区別できるようにしよう。公式でなく形で覚えれば、迷わない。積の法則は「長方形の面積」。

前菜を行、主菜を列にして表を作る。前菜 $3$ 種類 $\times$ 主菜 $4$ 種類 $=$ $3$ 行 $4$ 列の表ができ、マスは $12$ 個。マス $1$ つが「前菜と主菜の組合せ $1$ つ」だ。

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

さらにデザートが $2$ 種類。$12$ 個のマスそれぞれが $2$ 階建てになると思えばいい($1$ 階がデザートA、$2$ 階がデザートB)。立体の箱で言えば $3\times 4\times 2$ のブロック。

$$3\times 4\times 2=24(\text{通り})$$

選ぶものが増えるたびに、次元が $1$ つ増える。積の法則を図にすると、こうなる。和の法則は「箱を横に並べる」。

(2)では選べる料理を書き出してみる。

• 主菜: ${\mathrm{M}}_1,{\mathrm{M}}_2,{\mathrm{M}}_3,{\mathrm{M}}_4$($4$ 個)
• デザート: ${\mathrm{D}}_1,{\mathrm{D}}_2$($2$ 個)

$1$ 品だけ選ぶのだから、この $6$ 個の中から $1$ つ指さすだけ。

$$4+2=6(\text{通り})$$

表のマスにはならず、$1$ 列に並ぶ。 掛け算になる余地がない。

見分けの合言葉。

• かけ算: 選択が続く(前菜を選んだ、その上で主菜も選ぶ)。「$\dots$ して、さらに $\dots$」
• たし算: 選択肢が並ぶ(主菜から選ぶか、デザートから選ぶか)。「$\dots$ か、または $\dots$」

なお和の法則には重要な前提がある。$2$ つのグループに同じものが入っていない(重なりがない)ことだ。もし「主菜にもデザートにもなる一品」があったなら、単純に足すと二重に数えてしまう。そのときは重なりを引く(それが個数定理だ)。和の法則と個数定理は、地続きの話である。

方針

解答

⓪ 発想(どう考え始めるか) 約数を $1$ つずつ探すのは効率が悪い。素因数分解して、約数の「作り方」から数える。

$$72=2^3\times 3^2$$

$72$ の約数とは $2$ を何個か・$3$ を何個か掛け合わせたもの。$2$ の個数は $0,1,2,3$ の $4$ 通り、$3$ の個数は $0,1,2$ の $3$ 通り。この $2$ つを独立に選べるので、積の法則で

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

注意するのは「$0$ 個」を数え忘れないこと($2$ を $0$ 個使うのも立派な選択で、それが奇数の約数になる)。だから指数に $+1$ する。総和も同じ発想で、「$2$ の使い方の合計」と「$3$ の使い方の合計」を掛ける。

まず素因数分解する。

$$72=2^3\times 3^2$$

72の約数は2を $a$ 個、3を $b$ 個かけた $2^a\times 3^b$ の形で全部表せる。$a$ は $0,1,2,3$ の4通り、$b$ は $0,1,2$ の3通りだ。

(1) 「2を何個使うか」の4通りと、「3を何個使うか」の3通りは、別々に選べる。だからかけ算で

$$(3+1)(2+1)=4\times 3=12(\text{個})$$

指数に $+1$ するのは、「0個(その素数を使わない)」という選び方を数えるためだ。ここを忘れやすい。

(2) 約数の総和は次のかけ算を計算すると求まる。

$$(2^0+2^1+2^2+2^3)(3^0+3^1+3^2)$$

なぜこれで総和になるかというと、このカッコを展開すると、$2^a\times 3^b$ の形の約数が1個ずつ全部、ちょうど1回ずつ出てくるからだ。たとえば $2^2\times 3^1=12$ も、この展開の中に必ず現れる。

$$(1+2+4+8)(1+3+9)=15\times 13=195$$

発展。 約数の個数が奇数になるのは、どんな数のときだろうか。

上で見たように、約数は「掛けて $n$ になるペア」で作られる。だから普通は偶数個。ペアの相手が自分自身になるとき、つまり $n$ が平方数のときだけ、$1$ 個あまって奇数個になる($36$ なら $6\times 6$ の $6$ だけが組にならない)。

公式で見ても同じだ。$n=p^a{q}^b$ の約数の個数 $(a+1)(b+1)$ が奇数 $⟺$ $a$ も $b$ も偶数 $⟺$ $n$ は平方数。$2$ つの説明が同じ結論に着く。

この事実は有名なパズルの答えにもなっている。「$100$ 個のロッカーが閉じている。$1$ 番目の人が全部開け、$2$ 番目の人が $2$ の倍数を切り替え、$3$ 番目の人が $3$ の倍数を切り替え $\cdots$ $100$ 番目まで終わったとき、開いているロッカーは?」という問題で、答えは番号が平方数のロッカー($1,4,9,\dots ,100$ の $10$ 個)だ。切り替えられた回数が約数の個数で、奇数回切り替わったものだけが開いているからだ。

約数の個数という素朴な量が、パズルの構造を丸ごと決めている。

別解

全部書き出して、公式が本当に正しいことを確かめよう。 そのうえで「なぜ総和の公式があの形になるのか」の理由を説明する。約数を小さい順に全部書く。

$$1,2,3,4,6,8,9,12,18,24,36,72$$

数えると $12$ 個。足すと

$$1+2+3+4+6+8+9+12+18+24+36+72=195$$

公式の答えと一致した。

書き出すときのコツはペアで探すこと。$1\times 72$、$2\times 36$、$3\times 24$、$4\times 18$、$6\times 12$、$8\times 9$ と、掛けて $72$ になる組を小さいほうから順に見つける。$8\times 9$ で $\sqrt{72}\approx 8.5$ を越えたので終わり。$6$ 組できたから、約数は $12$ 個。この探し方なら、もれも重複も起きない。

さて、理由を説明する。なぜ総和が $(1+2+4+8)(1+3+9)$ になるのか。 この積をそのまま展開してみる。

$$(1+2+4+8)(1+3+9)=1\cdot 1+1\cdot 3+1\cdot 9+2\cdot 1+2\cdot 3+2\cdot 9+4\cdot 1+\cdots +8\cdot 9$$

展開して出てくる項は $12$ 個。それを計算すると

$$1,3,9,2,6,18,4,12,36,8,24,72$$

これは、さっき書き出した約数の一覧と完全に同じ集合だ(順番が違うだけ)。

つまり 「約数を全部足す」$=$「$(2$ の使い方の合計$)\times (3$ の使い方の合計$)$ を展開する」。展開の各項が約数 $1$ つずつときれいに $1$ 対 $1$ で対応しているのである。

$$\underset{2\text{をどう使うか}}{\underbrace{(1+2+2^2+2^3)}}\times \underset{3\text{をどう使うか}}{\underbrace{(1+3+3^2)}}=15\times 13=195$$

公式は暗記事項ではなく、「約数 $=$ 素因数の選び方」という $1$ つの見方から、個数($4\times 3$)も総和($15\times 13$)も同時に出てくる。同じ絵を、数えるか、足すかの違いだけだ。

なお $1+2+4+8=15$ は等比数列の和 $\frac{2^4-1}{2-1}$、$1+3+9=13$ は $\frac{3^3-1}{3-1}$ である。指数が大きい数(たとえば $2^{10}$)でも、等比数列の和の公式ですぐに出る。

方針

解答

⓪ 発想(どう考え始めるか) 委員長・副委員長・書記は役が違う。$\mathrm{A}$ が委員長で $\mathrm{B}$ が副委員長、と、$\mathrm{B}$ が委員長で $\mathrm{A}$ が副委員長は、別物だ。

役の区別があるなら順列である。

席を $3$ つ並べて、左から埋めていくと考えよう。

• 委員長: $7$ 人の誰でもよい → $7$ 通り
• 副委員長: 委員長になった人は使えない → 残り $6$ 通り
• 書記: さらに $1$ 人減って → $5$ 通り

$$7\times 6\times 5=210$$

選ぶたびに候補が $1$ 人ずつ減る。これが順列の特徴だ。掛ける個数は「選ぶ人数」と同じ $3$ 個。$4$ 個掛けたり、$2$ 個で止めたりしないこと。

3つの役は区別されるので、これは7人から3人を選んで並べる順列だ。記号では ${}_7{\mathrm{P}}_3$ と書く。

順に埋めていこう。委員長は7人の誰でもよいので7通り。委員長が決まると、副委員長はもう選べないその人を除いた残り6人から選ぶので6通り。さらに書記は残り5人から5通り。続けて選ぶのでかけ算して

$${}_7{\mathrm{P}}_3=7\times 6\times 5=210(\text{通り})$$

まとめ:かける数が $7,6,5$ と1ずつ減るのは、1人選ぶごとに残りが1人ずつ減るからだ。「役は3つだから、かける数は3個」と本数を意識すると、$7\times 6$ で止めたり、$\times 4$ まで余分にかけたりするミスを防げる。

発展。 順列の公式は階乗を使うとこう書ける。

$${}_n{\mathrm{P}}_r=\frac{n!}{(n-r)!}$$

$7\times 6\times 5$ は $\frac{7!}{4!}=\frac{7\cdot 6\cdot 5\cdot \cancel{4!}}{\cancel{4!}}$ と書ける。使わない下のほうを、割り算で消している。

この形にすると、$r=n$ のとき $\frac{n!}{0!}$ となる。$7$ 人全員を並べるのは $7!$ 通りのはずだから、$0!=1$ と決めておくと辻褄が合う。$0!=1$ は「そう決めると公式が全部きれいに動くから」という理由で定められている。数学ではしばしば、こうした「定義の後付け」で体系が整えられる($a^0=1$ も同じ考え方だ)。

なお ${}_n{\mathrm{P}}_r$ の $\mathrm{P}$ は「並べる」を表す言葉の頭文字、${}_n{\mathrm{C}}_r$ の $\mathrm{C}$ は「選ぶ」を表す言葉の頭文字である。記号の意味を知っておくと、どちらを使うか迷ったときの手がかりになる。

別解

「選ぶ」と「並べる」を、$2$ 段階に分けて数えるとどうなるか。この見方が次に習う組合せへの橋になる。

手順1: まず、役を気にせず $3$ 人選ぶ。

$7$ 人から $3$ 人を選ぶ選び方は ${}_7{\mathrm{C}}_3$ 通りだ。

$${}_7{\mathrm{C}}_3=\frac{7\times 6\times 5}{3\times 2\times 1}=35(\text{通り})$$

手順2: 選ばれた $3$ 人に、役を割りふる。

たとえば $\mathrm{A},\mathrm{B},\mathrm{C}$ の $3$ 人が選ばれたとしよう。この $3$ 人に委員長・副委員長・書記を配る方法は、$3$ 人の並べ方と同じで

$$3!=3\times 2\times 1=6(\text{通り})$$

($\mathrm{A}$ が委員長・$\mathrm{B}$ が副・$\mathrm{C}$ が書記、$\mathrm{A}$ が委員長・$\mathrm{C}$ が副・$\mathrm{B}$ が書記、$\dots$ と $6$ 通り。)

手順3: 掛ける。

$$35\times 6=210(\text{通り})$$

本解と同じ答えだ。この $2$ 段階がそのまま公式の意味になっている。

$${}_7{\mathrm{P}}_3={}_7{\mathrm{C}}_3\times 3!$$

順列 $=$ 組合せ $\times$ 並べ替え。 言いかえれば

$${}_7{\mathrm{C}}_3=\frac{{}_7{\mathrm{P}}_3}{3!}$$

組合せ $=$ 順列を、並べ替えのぶんで割ったもの。 組合せの公式の分母に $3!$ が現れる理由が、これではっきりする。同じ $3$ 人組を、順列では $6$ 回も数えているから、$6$ で割って $1$ 回にしているのだ。

使い分けの合言葉。

• 役・順番・場所の区別がある → 順列(並べる)
• 区別がなく、メンバーだけが問題 → 組合せ(選ぶ)

この問題を「掃除当番 $3$ 人を選ぶ」に変えれば、答えは $35$ 通り。同じ $7$ 人と $3$ という数字でも、区別の有無で答えが $6$ 倍違う。問題文の「それぞれ $1$ 人ずつ」「役割の区別はない」という一言を、決して読み飛ばしてはいけない。

方針

解答

⓪ 発想(どう考え始めるか) $0$ が入っていることに注意する。

$0$ は百の位に置けない。 $012$ は $3$ 桁の数ではないからである。だから制約のきついところ(百の位)から先に決める。これは数え上げの原則だ。

• 百の位: $0$ は使えないので $1,2,3,4$ の $4$ 通り
• 十の位: 百の位で使った $1$ 個を除いた残り $4$ 個($0$ も使える)→ $4$ 通り
• 一の位: さらに $1$ 個減って $3$ 通り

$$4\times 4\times 3=48$$

(2)の偶数は、条件がもう $1$ つ増える。一の位が $0,2,4$ であることだ。ここでも「制約のきつい一の位」から決めるが、一の位が $0$ のときとそうでないときで、百の位の自由度が変わる。だから場合分けが要る。

(1) 条件のきつい百の位から決める。百の位に0は置けないので、$1,2,3,4$ の4通り。残る十の位・一の位にはまだ使っていない4個(0を含む)から2個を選んで並べるので ${}_4{\mathrm{P}}_2=4\times 3=12$ 通り。かけ算して

$$4\times 12=48(\text{個})$$

(2) 偶数になるのは、一の位が $0,2,4$ のとき。ここで、一の位が0のときと、2や4のときで事情が変わる。だから場合を分ける。

一の位が0のとき: 0は一の位で使ってしまったので、百の位は残り $1,2,3,4$ の4通り。十の位は残り3個から3通り。$4\times 3=12$ 個。

一の位が2のとき: 百の位は0と2を除いた $1,3,4$ の3通り。十の位は残り3個から3通り。$3\times 3=9$ 個。

一の位が4のとき: 同じように $3\times 3=9$ 個。この3つは同時に起きないので、たして

$$12+9+9=30(\text{個})$$

まとめ:一の位を0とそれ以外で分けたのは、一の位が0のときだけ、百の位が0を気にせず4通り選べるからだ。ここを分けないと数を間違える。

発展。 この問題が教えているのは「条件のきついところから決める」という数え上げの原則だ。

なぜか。ゆるいところから決めると、後で来る「きつい条件」の選択肢数がその前の選択に依存して変わってしまい、単純なかけ算ができなくなるからである。十の位から先に決めると、そこに $0$ を入れたかどうかで百の位の候補数が変わる。そうなると場合分けが増えるだけだ。

同じ原則はいろいろな場面で使われる。

• 数独やパズルは、候補の少ないマスから埋める
• 方程式は、条件の強い式から使う
• 図形問題は、直角や等辺のある部分から攻める

自由度の低いところが全体の形を決める。 これは数学に限らない、問題解決の一般則だろう。

なお、$0$ を含む数字の問題では「$0$ を使わない場合」と「$0$ を使う場合」で分ける手もある。どのルートを通っても答えは同じだが、場合分けの数が少ないルートを選ぶ。その判断ができることが、数え上げの実力である。

別解

「引き算で数える」ルートを通ってみよう。数えにくいものを直接数えず、全体から要らないものを引く。場合の数で最もよく使う方法だ。

(1) 引き算で。

まず「$0$ を先頭に置いてもよい」ことにして、$5$ 個から $3$ 個を選んで並べる。

$${}_5{\mathrm{P}}_3=5\times 4\times 3=60(\text{通り})$$

このうち、百の位が $0$ になってしまったものを数えて引く。百の位が $0$ と決まると、残る十の位・一の位は $1,2,3,4$ の $4$ 個から $2$ 個を並べるので

$${}_4{\mathrm{P}}_2=4\times 3=12(\text{通り})$$

したがって

$$60-12=48(\text{通り})$$

本解と一致した。「ダメなものを数えて引く」ほうが、場合分けより楽なことが多い。

(2) 偶数も引き算で出せる。 $3$ 桁の数は偶数か奇数のどちらかだから

$$(\text{偶数})=(\text{全部})-(\text{奇数})=48-(\text{奇数の個数})$$

奇数は一の位が $1$ か $3$ のとき。ここが $0$ でないので、百の位の制約が単純になる。

• 一の位: $1$ か $3$ の $2$ 通り
• 百の位: $0$ と、一の位で使った数を除くので $5-2=3$ 通り
• 十の位: 残り $3$ 通り

$$2\times 3\times 3=18(\text{通り})$$

よって偶数は

$$48-18=30(\text{個})$$

本解の場合分け($12+18=30$)と一致した。

なぜ奇数のほうが数えやすいのか。 奇数では一の位が $1$ か $3$ で、$0$ が絡まないので、百の位の「$0$ 禁止」を一律に処理できる(場合分けが不要)。偶数だと一の位に $0$ が来るかどうかで百の位の候補数が変わるから、場合分けが要る。

教訓。「数えにくいほう」を直接攻めない。 反対側($=$ 余事象)が数えやすいなら、そちらを数えて引く。この発想は確率の「少なくとも $1$ つ $\dots$」の問題で、これから何度も使う。

$2$ つのルートで同じ $30$ が出た。これが何よりの検算である。

方針

解答

⓪ 発想(どう考え始めるか) 「隣り合う」と言われたら、$2$ 人を $1$ つのかたまりにする。これがこの型の第一手だ。

女子 $2$ 人をひもで縛って $1$ 人ぶんの荷物にすれば、並べるのは「男子 $3$ 人 $+$ 女子のかたまり」の $4$ 個になる。その並べ方は $4!$ 通り。

そして、かたまりの中でも $2$ 人が入れかわれる($\mathrm{女}1\mathrm{女}2$ と $\mathrm{女}2\mathrm{女}1$)。この $2!$ を掛け忘れるのが最頻ミスだ。

$$4!\times 2!=24\times 2=48$$

(2)の「隣り合わない」は、直接数えると場合が散らばって数えにくい。そこで全体から「隣り合う」を引く。

$$5!-48=120-48=72$$

数えにくいほうは、反対を数えて引く。

(1) 女子2人をひもで結んで、1つのかたまりだと思う。すると並べるものは「男子3人 + 女子のかたまり」の4つになる。この4つの並べ方は $4!=24$ 通り。

さらに、かたまりの中で女子2人の並ぶ順が $2!=2$ 通りある。両方かけて

$$4!\times 2!=24\times 2=48(\text{通り})$$

かたまりの中の $2!$ をかけ忘れるのが、いちばん多いミスだ。「かたまりにしたら、中の並びも数える」とセットで覚えよう。

(2) 「隣り合わない」を最初から数えようとすると、場合が多くて大変だ。そこで、全部の並べ方から「隣り合う」場合を引く。

全部の並べ方は $5!=120$ 通り、隣り合うのは(1)の48通りだから

$$120-48=72(\text{通り})$$

まとめ:「隣り合わない = 全部 − 隣り合う」と裏返して数えるのがコツだ。正面から数えるのが大変なときは、反対側から数えられないか考えてみよう。

発展。 すきま法は「$n$ 人並べたら、すきまは $n+1$ か所」という単純な事実の上に立っている。この $+1$(両端のぶん)を落とすかどうかが、正解できるかどうかの分かれ目だ。

一般化してみよう。男子 $m$ 人、女子 $f$ 人が誰も隣り合わないように並べるには

$$m!\times {}_{m+1}{\mathrm{P}}_f$$

そしてこの式は $f>m+1$ のとき $0$ になる(すきまの数より女子が多ければ、どうやっても隣り合ってしまう)。${}_4{\mathrm{P}}_5$ のような記号は定義されない。式を見れば「不可能」が自動的に分かる。

たとえば男子 $2$ 人・女子 $4$ 人では、すきまは $3$ か所しかないので、女子 $4$ 人を別々に入れることはできない。鳩の巣原理(巣より鳩が多ければ、どこかに $2$ 羽入る)そのものである。

数え上げの式から、単に数を出すだけでなく「そもそも可能か」まで分かる。 答えが $0$ になったり、記号が定義できなくなったりしたときこそ、問題の構造が見えている瞬間だ。

別解

(2)は引き算に頼らず、直接数えることもできる。「隣り合わない」を積極的に作りにいく方法で、すきま法と呼ばれる。人数が増えたときはこちらのほうが強い。

手順1: まず、じゃまにならない男子だけを並べる。

男子 $3$ 人を $1$ 列に並べる。

$$3!=6(\text{通り})$$

手順2: 男子の「すきま」を数える。

男子が $3$ 人並ぶと、女子が入れる場所は男子と男子のあいだ、および両端である。

$$\underline{}\text{男}\underline{}\text{男}\underline{}\text{男}\underline{}$$

下線の場所は $4$ か所ある($3$ 人の両側で $3+1=4$)。

手順3: すきまに女子を入れる。

女子は別々のすきまに入れる。 そうすれば、女子どうしのあいだに必ず男子が $1$ 人以上いるので、決して隣り合わない。$4$ か所のすきまから $2$ か所を選び、そこに女子 $2$ 人を並べる(どちらの女子がどちらのすきまか、で区別がつく)。

$${}_4{\mathrm{P}}_2=4\times 3=12(\text{通り})$$

手順4: 掛ける。

$$6\times 12=72(\text{通り})$$

引き算のルートと同じ答えだ。

すきま法の何が強いのか。 「隣り合わない」人が $3$ 人以上になると、引き算のルートは急に難しくなる。「少なくとも $2$ 人が隣り合う」を引こうとすると、$2$ 人だけ隣り合う場合と $3$ 人固まる場合が重なって、包除原理が必要になるからだ。

一方すきま法なら、人数が増えても手順は同じ。男子 $5$ 人・女子 $3$ 人が隣り合わないなら、$5!\times {}_6{\mathrm{P}}_3$ となる。すきまが $6$ か所になるだけである。

「隣り合う」ならかたまり、「隣り合わない」ならすきま。 $2$ つの型をセットで覚えておくと、この手の問題はすべて片づく。そして引き算のルートと突き合わせて検算する。$2$ つの方法で同じ数になれば、まず間違いない。

方針

解答

⓪ 発想(どう考え始めるか) 円卓では回転して重なる並びは同じものとみなす。$1$ 列に並べる $6!$ 通りをそのまま答えにすると、同じ座り方を $6$ 回ずつ数えてしまう(円を $1$ 目盛りずつ回した $6$ 通りが全部同じだから)。

対処は $2$ つある。

• 割る: $\frac{6!}{6}=120$
• 固定する: $1$ 人の席を決めてしまう。$\mathrm{A}$ を「北」の席に固定すれば、もう回転の自由はない。残り $5$ 人を並べて $5!=120$

どちらでも同じだが、固定する考え方のほうが応用が利く。円順列では誰か $1$ 人を基準にして、そこから見た並びを数える。(2)も同じ発想で、$\mathrm{A}$ を固定してから $\mathrm{B}$ の座れる席を考えればよい。

(1) 円で並べるときは、回転して同じになるものを1つと数えたい。そこで、まず1人の席を固定してしまう。すると、残りの5人を、固定した人から見た残りの席に並べる問題になる。

$$(6-1)!=5!=120(\text{通り})$$

$6!$ としないのは、6通りの回転がどれも同じ並びを表すからだ。だから $6!÷6=5!$ と、数え過ぎた分を割り落とす。「1人を固定する」というのは、この割り算を先に済ませたのと同じことだ。

(2) A, Bをひもで結んで1つのかたまりにする。すると「かたまり + 残り4人」の5つを円形に並べる問題になるので $(5-1)!=4!=24$ 通り。さらに、かたまりの中でA, Bの並ぶ順が $2!=2$ 通り。

$$(5-1)!\times 2!=24\times 2=48(\text{通り})$$

まとめ:隣り合う条件は1列のときと同じで「かたまりにして、中の並びも数える」。違うのは、かたまりにしたあとが円順列なので $(5-1)!$ になる点だけだ。

発展。 円順列は「回転で移り合うものを同じとみなす」数え方だった。では、裏返しも同じとみなしたらどうなるか。

たとえば $6$ 個のビーズで首飾りを作るとき、裏返せば時計回りと反時計回りは区別できない。このときの数え方をじゅず順列といい、円順列をさらに $2$ で割る。

$$\frac{(6-1)!}{2}=\frac{120}{2}=60(\text{通り})$$

「同じとみなす操作」が増えるほど、割る数が増える。 回転($6$ 通り)で割り、さらに裏返し($2$ 通り)で割る。この「対称性の数だけ割る」という発想は、大学で学ぶ群論(対称性の数学)の基礎になる。

ただし注意が必要だ。裏返して自分自身に重なる並びがあると、単純に $2$ で割るのは誤りになる(その並びは $2$ 回数えられていないから)。今回のように全員が異なる人なら問題ないが、同じ色のビーズが混じると話が変わる。

「割り算で重複を消す」ときは、「すべてがちょうど同じ回数だけ重複しているか」を必ず確かめる。ここは場合の数で最も注意すべき点である。

別解

$\mathrm{A}$ の席を固定するという一手だけで、(1)も(2)も暗算に近くなる。円順列の問題はこれ $1$ つで戦える。

(1) $\mathrm{A}$ を固定して数える。

$\mathrm{A}$ をテーブルの「$12$ 時の席」に座らせてしまう。もう回転はできない($\mathrm{A}$ の位置が動かないから)。残り $5$ 人を、$\mathrm{A}$ から時計回りに $5$ つの席へ並べるだけ。

$$5!=120(\text{通り})$$

「$(n-1)!$」という公式の $-1$ は、$1$ 人を固定したからである。丸暗記でなく、こう理解しておけば忘れない。

(2) $\mathrm{A}$ を固定し、$\mathrm{B}$ の席を考える。

$\mathrm{A}$ は $12$ 時に固定。$\mathrm{A}$ の隣は左隣と右隣の $2$ 席。$\mathrm{B}$ はこのどちらかに座る。

$$\text{B の席: }2\text{通り}$$

$\mathrm{A}$ と $\mathrm{B}$ の席が決まれば、残り $4$ 人を残り $4$ 席に自由に並べるだけ。

$$4!=24(\text{通り})$$

したがって

$$2\times 24=48(\text{通り})$$

公式ルート($(5-1)!\times 2!=24\times 2=48$)と同じ答えになった。固定法の利点は $2$ つある。

$1$ つ目: 「かたまりを作った後も円順列」という点を忘れない。 (2)を「$\mathrm{AB}$ をかたまりにして $5$ 個を並べる」と考えたとき、$5!$ としてしまう誤りが非常に多い。円卓なのだから、かたまりにした後も円順列で $(5-1)!$ である。固定法なら、そもそもこの心配がない。

$2$ つ目: 条件が増えても素直に伸びる。 「$\mathrm{A}$ と $\mathrm{B}$ が向かい合う」なら、$\mathrm{A}$ を固定した時点で $\mathrm{B}$ の席は $1$ 通りに決まり、$4!=24$ 通り。「$\mathrm{A}$ と $\mathrm{B}$ が隣り合わない」なら、$\mathrm{B}$ の席は隣 $2$ 席を除く $3$ 通りで $3\times 4!=72$ 通り(検算: $120-48=72$)。

円順列は「誰か $1$ 人の目線に立つ」ことで、ただの順列になる。 回転の自由度という厄介者を、$1$ 人を釘づけにすることで消し去るのだ。

方針

解答

⓪ 発想(どう考え始めるか) 順列との違いは、$1$ 行の条件だけだ。

「同じ色を何人が選んでもよい」 とある。つまり、$\mathrm{A}$ が赤を選んでも、$\mathrm{B}$ の選択肢は減らない。だから順列のように $4\times 3\times 2$ とはならない。

• $\mathrm{A}$: $4$ 通り
• $\mathrm{B}$: $\mathrm{A}$ が何を選ぼうと $4$ 通り
• $\mathrm{C}$: やはり $4$ 通り

$$4\times 4\times 4=4^3=64$$

選択肢が減らないので、同じ数を掛け続ける。これが重複順列だ。

$4^3$ か $3^4$ かで迷ったら、こう考える。「$4$ 通りの選択が、$3$ 回起こる」。だから $4$ を $3$ 回掛ける。下(底)が選択肢の数、肩(指数)が選ぶ回数である。

「同じ色を何人が選んでもよい」ので、誰かが色を選んでも、次の人はまた4色から選べる。選択肢は減らない。だからA・B・Cはそれぞれ4通りずつ自由に選べる。かけ算して

$$4\times 4\times 4=4^3=64(\text{通り})$$

これは4個から3個を選ぶ重複順列だ。順列 ${}_4{\mathrm{P}}_3=4\times 3\times 2=24$ とは違って、かける数が減らない。選んでも選択肢が元に戻る(同じ色をまた選べる)からだ。

「選択肢が毎回元に戻るか、1つずつ減るか」を見分けるのが、重複順列と順列の分かれ道になる。

まとめ:式の形は「(選択肢の数)の(選ぶ回数)乗」で $4^3$。どちらが色の数(4)で、どちらが人数(3)か、意味に戻って確かめよう。

発展。 重複順列 $m^n$ の指数関数的な増え方は、想像を超えて速い。

$4$ 色・$3$ 人なら $64$ 通りだが、$4$ 色・$10$ 人なら $4^{10}=1048576$ となり、$100$ 万通りを超える。人が $1$ 人増えるたびに、場合の数は $4$ 倍になるからだ。

この急激な増え方は暗証番号の強さの根拠でもある。$4$ 桁の数字の暗証番号は $10^4=10000$ 通り。桁を $1$ つ増やして $5$ 桁にすれば $10$ 万通りになる。$1$ 桁で $10$ 倍安全になる。パスワードに英大小文字と記号を混ぜて選択肢を $70$ 通りに増やせば、$8$ 文字で $70^8\approx 5.8\times 10^{14}$ 通りになる。

「長さを足すと、場合の数は掛け算で増える」 と言える。足し算的な努力が掛け算的な効果を生む。これが指数の力だ。

逆に言えば、総当たりで解ける問題の限界もここで決まる。$n$ 個のものの並べ方 $n!$ は指数よりさらに速く増え、$20!\approx 2.4\times 10^{18}$ にもなる。1秒に10億通り調べても、全部を調べるのに80年近くかかる数だ。総当たりで調べられる範囲には限りがある。

別解

$4^3$ と $3^4$ の取り違えはこの単元で最も多いミスだ。二度と迷わないための考え方を $2$ つ渡しておく。考え方1: 「人」を主語にして、$1$ 人ずつ配る。

$\mathrm{A}$ さんの前に立って聞く。「何色にしますか?」への答えは $4$ 通りだ。$\mathrm{B}$ さんにも聞く。$4$ 通り。$\mathrm{C}$ さんにも。$4$ 通り。

質問した回数 $=$ $3$ 回(人数)。毎回の答えの数 $=$ $4$(色数)。

$$\underset{3\text{人ぶん}}{\underbrace{4\times 4\times 4}}=4^3=64$$

「人の数だけ掛け算が並び、色の数が掛けられる数になる」。主語を人にすれば、迷いようがない。考え方2: 対比して覚える。

同じ「$3$ 人と $4$ 色」でも、条件が変われば答えは変わる。

「重複してよい $\to$ 減らない $\to$ 累乗」「重複ダメ $\to$ 減る $\to$ 順列」。 この対比を頭に入れておけば、問題文の「同じ色を選んでもよい」という一言が、使う公式を決める手がかりになる。

もし $3^4$ ならどんな問題か。 「$4$ 色のカードそれぞれを、$3$ 人の誰かに $1$ 枚ずつ配る」なら $3^4=81$ 通りだ。配られる側と配る側が入れかわっている。 「何が選ばれる側で、何が選ぶ側か」を取り違えると、この $2$ つが逆になる。

見分け方は1つだけだ。$1$ つの選択が終わったとき、次の選択肢は減っているか? 減っていなければ累乗。減っていれば順列。この $1$ 問だけを自分に投げかければよい。

もっと高い視点から。 この数え方は「$3$ 人のそれぞれに $4$ 色のどれかを対応させる方法は何通りか」、つまり $3$ 個の要素から $4$ 個の要素への対応(写像)の総数を数えている。一般に $n$ 個から $m$ 個への対応は $m^n$ 通り。肩に乗るのは出発点の個数である。$0$ と $1$ の $2$ 択が $n$ 回で $2^n$、サイコロ $n$ 個の目の出方が $6^n$ で、どれも同じ形をしている。

方針

解答

⓪ 発想(どう考え始めるか) 「$3$ 人に役割の区別はない」という一言から、組合せを使うと分かる。

$\{\mathrm{A},\mathrm{B},\mathrm{C}\}$ を選ぶのも $\{\mathrm{C},\mathrm{A},\mathrm{B}\}$ を選ぶのも、同じ $3$ 人組。順番は関係ない。もし順番をつけて数えると(順列)、$3$ 人組 $1$ つを $3!=6$ 回も数えてしまう。だから $6$ で割って $1$ 回にする。

$${}_8{\mathrm{C}}_3=\frac{{}_8{\mathrm{P}}_3}{3!}=\frac{8\times 7\times 6}{3\times 2\times 1}=\frac{336}{6}=56$$

分母は $3$ ではなく $3!=6$。 ここを間違えないこと。

「選ぶだけか、並べるまでか」 の答えは、問題文に必ず書いてある。

3人に役の区別がないので、選ぶ順番は関係ない。こういうときは組合せ ${}_8{\mathrm{C}}_3$ を使う。

$${}_8{\mathrm{C}}_3=\frac{8\times 7\times 6}{3\times 2\times 1}=\frac{336}{6}=56(\text{通り})$$

分母の $3!=6$ で割る意味を確かめておこう。もし役を区別して並べるなら ${}_8{\mathrm{P}}_3=8\times 7\times 6=336$ 通り。でも同じ3人組は、並べ方が $3!=6$ 通りあって、その6通りが全部ダブって数えられている。この順番の違いを消すために6で割る。

$${}_8{\mathrm{C}}_3=\frac{{}_8{\mathrm{P}}_3}{3!}$$

まとめ:「順番を区別すれば順列、区別しなければ組合せ($r!$ で割る)」。この対応が場合の数の基本になる。

発展。 組合せの数 ${}_n{\mathrm{C}}_r$ は数IIで学ぶ二項定理の係数として再登場する。

$$(a+b{)}^n=\sum _{r=0}^n{}_n{\mathrm{C}}_r{a}^{n-r}{b}^r$$

なぜ組合せが出てくるのか。$(a+b{)}^8$ を展開するとき、$8$ 個の $(a+b)$ からどの $3$ 個で $b$ を選ぶかを決めれば、$a^5{b}^3$ の項が $1$ つできる。その選び方は ${}_8{\mathrm{C}}_3=56$ 通りなので、$a^5{b}^3$ の係数は $56$ になる。

「展開の係数」と「選び方の数」が同じものだと分かると、代数と数え上げが一本につながる。だから ${}_n{\mathrm{C}}_r$ は二項係数とも呼ばれる。パスカルの三角形の各段が $(a+b{)}^n$ の係数になっているのも、この対応の帰結だ。$1,4,6,4,1$ は $(a+b{)}^4=a^4+4a^{3}b+6a^2{b}^2+4a{b}^3+b^4$ の係数そのものである。

数える(組合せ)・展開する(代数)・足し上げる(パスカル) の $3$ つの場面で同じ数が現れ、高校数学のあちこちで使われる。

別解

組合せの計算には、割り算をまったく使わない道がある。特定の $1$ 人に注目して、入るか入らないかで場合分けするやり方だ。

$\mathrm{A}$ さん $1$ 人に注目する。 掃除当番の $3$ 人組は次の $2$ 種類しかない。

(i) $\mathrm{A}$ が当番に入る場合。 $\mathrm{A}$ はもう決まったので、残り $7$ 人から $2$ 人を選べばよい。

$${}_7{\mathrm{C}}_2=\frac{7\times 6}{2}=21(\text{通り})$$

(ii) $\mathrm{A}$ が当番に入らない場合。 $\mathrm{A}$ を除いた $7$ 人から $3$ 人を選ぶ。

$${}_7{\mathrm{C}}_3=\frac{7\times 6\times 5}{6}=35(\text{通り})$$

この $2$ つに重なりはなく、これで全部である($\mathrm{A}$ は入るか入らないかのどちらか)。だから足す。

$$21+35=56(\text{通り})$$

本解と一致した。この関係を式にすると

$${}_8{\mathrm{C}}_3={}_7{\mathrm{C}}_2+{}_7{\mathrm{C}}_3$$

一般に

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

これがパスカルの法則だ。上の段の隣り合う $2$ 数を足すと、下の段の数になる。パスカルの三角形は、この式で組み上がっている。

$$\begin{array}{c}1\\ 11\\ 121\\ 1331\\ 14641\end{array}$$

掛け算も割り算も使わず、足し算だけで組合せの値が出る。手計算でも、コンピュータでも(桁あふれしにくいので)重宝する方法である。もう $1$ つ、計算を楽にする性質。

$${}_8{\mathrm{C}}_3={}_8{\mathrm{C}}_5=56$$

「$8$ 人から当番 $3$ 人を選ぶ」ことは、「$8$ 人から居残らない $5$ 人を選ぶ」ことと同じだ。選ぶ側を数えても、選ばれない側を数えても、通り数は変わらない。だから ${}_n{\mathrm{C}}_r={}_n{\mathrm{C}}_{n-r}$。

たとえば ${}_{100}{\mathrm{C}}_{98}$ を計算するとき、まともにやると大変だが、${}_{100}{\mathrm{C}}_2=\frac{100\times 99}{2}=4950$ と読みかえればすぐに計算できる。大きいほうの $r$ が出てきたら、ひっくり返す。実戦で役に立つ小技である。

方針

解答

⓪ 発想(どう考え始めるか) $6$ 文字を並べるだけなら $6!=720$ 通り。しかし $\mathrm{A}$ が $3$ つ、$\mathrm{B}$ が $2$ つ同じ文字だ。

$3$ つの $\mathrm{A}$ にこっそり番号をつけて ${\mathrm{A}}_1,{\mathrm{A}}_2,{\mathrm{A}}_3$ と区別すれば $720$ 通り。でも番号を消すと、$\mathrm{A}$ の並べ替え $3!=6$ 通りは全部同じ見た目になる。つまり $720$ は同じ並びを $3!\times 2!$ 回ずつ数えている。だから割る。

$$\frac{6!}{3!\times 2!}=\frac{720}{6\times 2}=60$$

分母は足し算ではなく掛け算($3!+2!=8$ で割るのは誤り)。$\mathrm{A}$ の重複と $\mathrm{B}$ の重複は独立に起きているので、重複の総数は積になるからだ。

6文字が全部違うなら $6!=720$ 通り。でも実際はAが3個、Bが2個ある。

同じAどうしや、同じBどうしを入れ替えても並びは変わらない。そのぶん、同じ並びを何回もダブって数えている。Aの3個の並べ替え $3!$ 通り、Bの2個の並べ替え $2!$ 通りがそれぞれ同じ並びを表す。だからこれらで割る。

$$\frac{6!}{3!\times 2!}=\frac{720}{6\times 2}=\frac{720}{12}=60(\text{通り})$$

Cは1個なので $1!=1$ で割ることになり、影響しない(書かなくてよい)。分母は「同じ文字ごとに、その個数の階乗をかけ合わせたもの」だ。A用の $3!$、B用の $2!$ をかける。

まとめ:別の見方もできる。6か所のうちAを置く3か所を選び(${}_6{\mathrm{C}}_3$)、残り3か所からBを置く2か所を選ぶ(${}_3{\mathrm{C}}_2$)、最後の1か所にCを置く、と考えても ${}_6{\mathrm{C}}_3\times {}_3{\mathrm{C}}_2=20\times 3=60$ で同じになる。

発展。 $\frac{n!}{p!q!r!}$ という数は多項係数と呼ばれ、二項係数 ${}_n{\mathrm{C}}_r=\frac{n!}{r!(n-r)!}$ の自然な拡張になっている(グループが $2$ つなら二項、$3$ つ以上なら多項)。

これは $(a+b+c{)}^6$ を展開したときの $a^3{b}^{2}c$ の係数でもある。$6$ 個の $(a+b+c)$ から、どの $3$ 個で $a$ を、どの $2$ 個で $b$ を選ぶかを数えることになる。文字の並べ方と、展開の係数が同じ数になる。実際、その係数はぴったり $60$ になる。

日常の言葉で言えば、この数は「$6$ 個のものを、$3$ 個・$2$ 個・$1$ 個の名前つきグループに分ける方法の数」である。トランプを配る、チームを分ける、荷物を仕分けるなど、現実の分配問題はたいていこの形をしている。

なお「$6$ 人を $3$ 人・$2$ 人・$1$ 人の名前のない組に分ける」なら話が変わる。組に区別がないと、さらに割る必要が出てくる場合があるからだ(同じ人数の組が複数あるとき)。場合の数は最後まで「区別があるか、ないか」という問いに尽きる。

別解

割り算を使わず、「どの場所に置くか」を選んでいくやり方がある。こちらのほうが、じつは直感的かもしれない。

発想の転換。 「文字を並べる」のではなく、「$6$ つの席のうち、どの席に $\mathrm{A}$ を座らせるか」を選ぶと考える。

$$\underline{1}\underline{2}\underline{3}\underline{4}\underline{5}\underline{6}$$

手順1: $6$ 席から、$\mathrm{A}$ の $3$ 席を選ぶ。

$\mathrm{A}$ は $3$ つとも同じ文字だから、どの $\mathrm{A}$ がどこか、は気にしなくてよい。ただ「$3$ 席を選ぶ」だけ。

$${}_6{\mathrm{C}}_3=\frac{6\times 5\times 4}{3\times 2\times 1}=20(\text{通り})$$

手順2: 残り $3$ 席から、$\mathrm{B}$ の $2$ 席を選ぶ。

$${}_3{\mathrm{C}}_2=3(\text{通り})$$

手順3: $\mathrm{C}$ は残った $1$ 席に入るしかない。

$${}_1{\mathrm{C}}_1=1(\text{通り})$$

掛け合わせる。

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

割り算を $1$ 度も使わずに、同じ $60$ にたどり着いた。

この方法の何がいいか。 「同じものだから割る」という引け目のある操作が消える。同じ文字はもともと区別しないまま、席だけを選んでいるからだ。「$720$ 通りを一度作ってから、重複を割って消す」より、「最初から重複を作らない」ほうが気持ちがいい。

そして、この見方は次の問題(最短経路)に直結する。 「右へ $4$ 回・上へ $3$ 回、合わせて $7$ 回の移動のうち、どの $3$ 回を『上』にするか」は、席選びそのものだ。

同じものを含む順列は、じつは組合せだった。 一般に

$$\frac{n!}{p!q!r!}={}_n{\mathrm{C}}_p\times {}_{n-p}{\mathrm{C}}_q\times \cdots$$

「割り算の式」と「選び方の積」は同じものである。どちらで計算してもよいが、意味が見えるのは後者だ。

方針

解答

⓪ 発想(どう考え始めるか) 「右か上にだけ進む」ので、$\mathrm{A}$ から $\mathrm{B}$ へ行くには右に $4$ 区画、上に $3$ 区画、合わせて必ず $7$ 回進む。どんな経路でも、この回数は変わらない。

違うのは順番だけだ。だから経路は $\to$ を $4$ 個、$\uparrow$ を $3$ 個並べた文字列と $1$ 対 $1$ で対応する。

$$\to \to \uparrow \to \uparrow \uparrow \to ,\uparrow \to \to \to \uparrow \to \uparrow ,\dots$$

道の問題が同じものを含む順列の問題になった。

$$\frac{7!}{4!\times 3!}=\frac{5040}{24\times 6}=35$$

$7$ 回のうち、どの $3$ 回を上にするかと読めば、${}_7{\mathrm{C}}_3=35$ でも同じこと。経路を記号の列で表す。これがこの問題の発想だ。

AからBへ最短で行くには、右へ4区画、上へ3区画進む必要がある。右への1歩を「→」、上への1歩を「↑」で表すと、1つの道は「→を4個、↑を3個」並べた記号の列で表せる。たとえば $\to \to \uparrow \to \uparrow \uparrow \to$ のように、並べる順番が道の形を決める。

だから、求める道の数は「→を4個、↑を3個(合わせて7個)を1列に並べる」同じものを含む順列だ。

$$\frac{7!}{4!\times 3!}=\frac{5040}{24\times 6}=\frac{5040}{144}=35(\text{通り})$$

矢印は全部で7個(右4回 + 上3回)。これは、はしからはしまで進むのに必ず7歩かかることを表している。「→の数 = 横の区画数、↑の数 = 縦の区画数」を図から正しく読み取るのが出発点だ。

まとめ:組合せの形で書けば、7個の場所から→を置く4か所を選ぶ ${}_7{\mathrm{C}}_4=35$、あるいは↑を置く3か所を選ぶ ${}_7{\mathrm{C}}_3=35$ でも同じだ。

発展。 最短経路の数え上げは「問題を、別の言葉に言い換える」というよく使う方法の例だ。

道 $\to$ 矢印の列 $\to$ 席の選び方 $\to$ 組合せ

言い換えるたびに、問題は解きやすい形になっていく。もとの「道を数える」は幾何の問題に見えるが、最後は ${}_7{\mathrm{C}}_3$ というただの計算になった。考える部分は言い換えの作業に移っている。

この方法は先へ進むほど役に立つ。

• 確率の問題を、場合の数に言い換える
• 図形の問題を、座標やベクトルで表す
• 漸化式を、等比数列に直す

「これは、何の言い換えか?」と問う癖をつけたい。

なお格子の書き込み法はコンピュータの動的計画法という手法そのものである。「小さい問題の答えを表に記録し、それを足して大きい問題を解く」という考え方で、カーナビの経路探索も、文章の類似度計算も動いている。$35$ という数を求める考え方は、コンピュータの計算にも使われている。

別解

公式を使わず、交差点に数を書き込んでいく方法がある。地図に直接書き込むだけで答えが出る、目で見える解き方だ。

ルールは $1$ つだけだ。「その交差点への行き方の数」$=$「左隣への行き方」$+$「下隣への行き方」なぜか。ある交差点にたどり着く最後の一歩は、左から来たか、下から来たかのどちらかしかない。だから $2$ つを足せばよい。

まず、$\mathrm{A}$ のある左端の列と、下端の行に $1$ を書く(まっすぐ進むしか行き方がないから、どこも $1$ 通り)。あとは左下から順に足していく。

(いちばん下の行が $\mathrm{A}$ のある行、右上の $35$ が $\mathrm{B}$ である。)

たとえば下から $2$ 行目の $6$ は、左の $3$ と下の $3$ を足したもの。 上の行の $10$ は左の $4$ と下の $6$ を足したもの。足し算だけで、右上に $35$ が現れる。

この方法の強みは $2$ つある。

$1$ つ目: 途中に通れない道があっても使える。 「工事中で通れない交差点」があれば、そこに $0$ を書き込んで先へ進むだけ。公式は通行止めを扱えないが、書き込み法なら何でも来いである。

$2$ つ目: 「必ずこの点を通る」条件も簡単だ。 その点までの数と、その点から $\mathrm{B}$ までの数を掛ければよい。

そして、この表をよく見てほしい。 $1,1,1,1$ / $1,2,3,4$ / $1,3,6,10$ と並んだ数を斜めに読むと、$1,3,3,1$ や $1,4,6,4$ が現れる。格子の上に、パスカルの三角形が現れている。

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

というパスカルの法則は「左から来るか、下から来るか」の $2$ 択を式にしたものだった。組合せの公式と、格子の足し算は、同じ $1$ つの事実の表と裏である。

パスカルの三角形を「意味のない数の並び」として覚えた人は多い。しかしこの数の並びは道の数え上げを表していた。