数学A / 場合の数

重複順列

★ 基礎重複順列

問題

A, B, C の3人が、それぞれ赤・青・黄・緑の4色のカードから好きな色を1枚選ぶ。同じ色を何人が選んでもよい。色の選び方は全部で何通りあるか。

ヒントを見る

同じ色を何人が選んでもよい=前の人の選択に左右されない。 $A$ 、 $B$ 、 $C$ それぞれが独立に $4$ 通り — 各自の数をかける。

解答・解説

方針

この問題のポイントは、「同じ色を何人が選んでもよい」という一文だ。

順列では、1人選ぶたびに残りが減った。でもここでは減らない。Aが赤を選んでも、Bはまた赤を選べる。

つまり、A・B・Cのそれぞれが、いつも4色から自由に選べる。だから4通りずつを人数分かける。こういうのを重複順列という。

解答

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

「同じ色を何人が選んでもよい」 — つまり、 $A$ が赤を選んでも、 $B$ の選択肢は減らない。

だから順列のように $4 \times 3 \times 2$ とはならない。

$A$ : $4$ 通り
$B$ : $A$ が何を選ぼうと $4$ 通り
$C$ : やはり $4$ 通り

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

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

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

公式重複順列:

n

通りから重複を許して

r

回選ぶと

n^{r}

通り

「同じ色を何人が選んでもよい」ので、誰かが色を選んでも、次の人はまた4色から選べる。選択肢は減らない。

だからA・B・Cはそれぞれ4通りずつ自由に選べる。かけ算して

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

これは4個から3個を選ぶ重複順列だ。順列 $_{4} 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$ 桁の数字の暗証番号は $1 0^{4} = 10000$ 通り。桁を $1$ つ増やして $5$ 桁にすれば $10$ 万通り — $1$ 桁で $10$ 倍安全になる。パスワードに英大小文字と記号を混ぜて選択肢を $70$ 通りに増やせば、 $8$ 文字で $7 0^{8} \approx 5.8 \times 1 0^{14}$ 通りになる。

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

逆に言えば、総当たりで解ける問題の限界もここで決まる。 $n$ 個のものの並べ方 $n!$ は指数よりさらに速く増え、 $20! \approx 2.4 \times 1 0^{18}$ — 現代のコンピュータでも全部は調べきれない。数え上げの数学は、計算機の限界と隣り合わせにある。

答

64通り

別解

$4^{3}$ と $3^{4}$ の取り違えは、この単元で最も多い事故だ。二度と迷わないための考え方を $2$ つ渡しておく。

考え方1: 「人」を主語にして、 $1$ 人ずつ配る。

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

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

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

「人の数だけ掛け算が並び、色の数が掛けられる数になる」 — 主語を人にすれば、迷いようがない。

考え方2: 対比して覚える。

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

条件	数え方	答え
同じ色を何人選んでもよい	$4^{3}$	$64$
$3$ 人とも違う色	$_{4} P_{3} = 4 \times 3 \times 2$	$24$

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

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

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

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

ポイント

同じものを何度選んでもよい → 選択肢が減らない → 毎回同じ数をかける
$n$ 個から重複を許して $r$ 個 → $n^{r}$ (選択肢の数の、選ぶ回数乗)
順列 $_{n} P_{r}$ (減る)との違いは「同じものを選べるか」の1点

よくある間違い

順列 $_{4} P_{3} = 24$ で計算してしまう(選択肢が減らないのに減らしている)
$4^{3}$ と $3^{4}$ を取り違える(下=選択肢の数、肩=選ぶ回数)
組合せ $_{4} C_{3}$ で計算してしまう(誰がどの色かの区別があるので組合せではない)