重複順列と重複組み合わせ - 同じものを繰り返し選べるときの場合の数

通常の順列や組み合わせでは、一度選んだものは再び選べません。しかし実際には「同じものを何度でも選べる」場面が多くあります。サイコロを 3 回振るとき、同じ目が何度出てもよいですし、飲み物を 3 本買うとき同じ種類を複数選んでもかまいません。このように重複を許す場合の数を扱うのが、重複順列と重複組み合わせです。

重複順列

重複順列は「 $n$ 種類のものから重複を許して $r$ 個を選び、並べる」場合の数です。

たとえば A, B, C の 3 文字から重複を許して 2 文字を選んで並べるとき、AA, AB, AC, BA, BB, BC, CA, CB, CC の 9 通りがあります。通常の順列なら同じ文字を 2 回使えないので AA, BB, CC は除外されますが、重複順列ではこれらも含まれます。

通常の順列

一度選んだものは使えない。 $n$ 個から $r$ 個選んで並べると $_{n} P_{r} = \frac{n !}{( n - r )!}$ 通り。

重複順列

同じものを何度でも選べる。 $n$ 種類から $r$ 個選んで並べると $n^{r}$ 通り。

なぜ $n^{r}$ になるかを考えてみます。1 個目の選び方は $n$ 通り、2 個目も同じものを選べるので $n$ 通り、3 個目も $n$ 通り……と、 $r$ 個すべてで $n$ 通りの選択肢があります。積の法則により、全体では $n \times n \times \dots \times n = n^{r}$ 通りです。

$重複順列 = n^{r}$

重複順列の具体例

4 桁の暗証番号を 0〜9 の数字で作るとき、何通りの番号があるかを求めてみます。

10 種類の数字から重複を許して 4 個を選び、並べる問題です。各桁で 0〜9 の 10 通りを選べるので、

$1 0^{4} = 10000 通り$

通常の順列との比較

もし同じ数字を繰り返し使えないなら $_{10} P_{4} = 10 \times 9 \times 8 \times 7 = 5040$ 通りです。重複を許すと 10000 通りに増えます。選択肢が減らないぶん、場合の数は大きくなります。

サイコロの例

サイコロを 3 回振ったときの出目のパターンは $6^{3} = 216$ 通りです。各回で 1〜6 の 6 通りが独立に選ばれるので、重複順列そのものになっています。

重複組み合わせ

重複組み合わせは「 $n$ 種類のものから重複を許して $r$ 個を選ぶ（並べない）」場合の数です。順番を考えないところが重複順列との違いになります。

たとえば 3 種類のドーナツ（チョコ・プレーン・抹茶）から重複を許して 4 個を買う場合を考えます。チョコ 2 個・プレーン 1 個・抹茶 1 個も、チョコ 4 個・プレーン 0 個・抹茶 0 個も、どれも有効な買い方です。

この場合の数を求める公式は次のようになります。

$_{n} H_{r} =_{n + r - 1} C_{r} = \frac{( n + r - 1 )!}{r ! ( n - 1 )!}$

仕切りと玉で理解する

重複組み合わせの公式は「仕切りと玉」の考え方で直感的に理解できます。

$r$ 個の玉（選ぶもの）と $(n - 1)$ 個の仕切り（種類の境目）を一列に並べる、と考えます。先ほどのドーナツの例なら、4 個の玉 ○ と 2 個の仕切り | を並べます。

○○|○|○ の場合

仕切りで区切ると「○○ / ○ / ○」となり、チョコ 2 個・プレーン 1 個・抹茶 1 個を意味します。

○○○○|| の場合

仕切りで区切ると「○○○○ / / 」となり、チョコ 4 個・プレーン 0 個・抹茶 0 個を意味します。

玉 $r$ 個と仕切り $(n - 1)$ 個の合計 $(n + r - 1)$ 個の中から、仕切りを置く位置（または玉を置く位置）を選ぶ組み合わせなので、

$_{n + r - 1} C_{r} =_{n + r - 1} C_{n - 1}$

となります。ドーナツの例では $n = 3$ , $r = 4$ なので、

$_{3} H_{4} =_{3 + 4 - 1} C_{4} =_{6} C_{4} = \frac{6 !}{4 ! \cdot 2 !} = 15 通り$

4 つの場合の数の整理

ここまでの内容を、重複の有無と順序の有無で整理します。

区分	順序あり	順序なし
重複なし	順列 $_{n} P_{r}$	組み合わせ $_{n} C_{r}$
重複あり	重複順列 $n^{r}$	重複組み合わせ $_{n} H_{r}$

順序を考えるかどうかと、同じものを繰り返し使えるかどうかの 2 軸で、4 つの場合の数が区別されます。問題文を読んだとき「並べるのか選ぶだけか」「同じものを何度も使えるか」を判断できれば、使うべき公式がわかります。

重複組み合わせの練習問題

5 種類のアイスクリームから重複を許して 3 個を選ぶ方法は何通りですか？

125 通り
10 通り
35 通り
60 通り

__RESULT__

$_{5} H_{3} =_{5 + 3 - 1} C_{3} =_{7} C_{3} = \frac{7 !}{3 ! \cdot 4 !} = 35$ 通りです。 $5^{3} = 125$ は重複順列（並べる場合）の答えなので、選ぶだけなら重複組み合わせを使います。

方程式の非負整数解への応用

重複組み合わせは、方程式の非負整数解の個数を求める問題にも応用できます。

$x + y + z = 10$ （ただし $x, y, z \geq 0$ ）の非負整数解の個数を求めてみます。これは「3 種類の変数に合計 10 を分配する」問題なので、3 種類から重複を許して 10 個選ぶ重複組み合わせと同じ構造です。

$_{3} H_{10} =_{3 + 10 - 1} C_{10} =_{12} C_{10} =_{12} C_{2} = \frac{12 \times 11}{2} = 66 通り$

仕切りと玉で考えると、10 個の玉と 2 個の仕切りを並べる問題として 12 個から仕切り 2 つの位置を選ぶ $12 C_{2} = 66$ 通りとも理解できます。

$x + y + z + w = 6$ （ $x, y, z, w \geq 0$ ）の非負整数解は何通りですか？

56 通り
84 通り
120 通り
210 通り

__RESULT__

4 種類の変数に合計 6 を分配するので $_{4} H_{6} =_{4 + 6 - 1} C_{6} =_{9} C_{6} =_{9} C_{3} = \frac{9 \times 8 \times 7}{3 \times 2 \times 1} = 84$ 通りです。

重複順列と重複組み合わせの見分け方

問題を解くときに迷いやすいのが「順序があるかないか」の判断です。

パスワードや暗証番号のように、選んだものを特定の位置に配置する場合は重複順列です。一方、買い物やボールの分配のように「何を何個選んだか」だけが問題になる場合は重複組み合わせになります。

1234 と 4321 が異なるなら順序あり、同じなら順序なし。

たとえば「赤・青・黄の 3 色から 5 回塗る」なら各回に順番があるので $3^{5} = 243$ 通り（重複順列）ですが、「赤・青・黄の 3 色のボールを合計 5 個選ぶ」なら順番は関係ないので $_{3} H_{5} =_{7} C_{5} = 21$ 通り（重複組み合わせ）です。同じ「3 種類から 5 個」でも、順序の有無で答えが大きく変わることがわかります。