順列では「使ったものは使えない」が原則でした。
この制限を外すと、数え方の構造がガラリと変わり、$n^r$ という驚くほどシンプルな公式が現れます。
6-2で学んだ順列 $_nP_r$ は、「$n$ 個の異なるものから $r$ 個を取り出して並べる」ものでした。 このとき、一度選んだものは二度と使えません。 では、同じものを何度でも使ってよいとしたら、並べ方は何通りになるでしょうか？
具体的に考えてみましょう。 $\text{a}, \text{b}, \text{c}$ の3文字から、同じ文字を何度使ってもよいものとして、2文字を選んで並べます。
1文字目は $\text{a}, \text{b}, \text{c}$ の 3通り。 2文字目も、使った文字をまた使えるので、やはり 3通り。 積の法則により、$3 \times 3 = 3^2 = 9$ 通りです。
通常の順列なら $_3P_2 = 3 \times 2 = 6$ 通りですから、 $\text{aa}, \text{bb}, \text{cc}$ の3つが加わって9通りになったわけです。
重複順列の核心は、各位置での選択肢が常に $n$ 通りで変わらないことです。
通常の順列では、1番目に $n$ 通り、2番目に $n-1$ 通り、3番目に $n-2$ 通り……と、 使うたびに選択肢が1つずつ減っていきます。だから $_nP_r = n(n-1)(n-2)\cdots(n-r+1)$ という「下がっていく掛け算」になります。
重複順列では、使っても減らないので、毎回 $n$ 通りです。 $r$ 回分を掛け合わせて $\underbrace{n \times n \times \cdots \times n}_{r} = n^r$ となります。
$n^r$ の指数が $r$（取る個数）、底が $n$（選択肢の数）です。ここを逆にしないよう注意してください。
異なる $n$ 個のものから、重複を許して $r$ 個取り出して1列に並べる順列（重複順列）の総数は
$$n^r \text{ 通り}$$$n$ 個の異なるものから重複を許して $r$ 個を取り出し、1列に並べることを考えます。
1番目のものの選び方は $n$ 通り。
2番目のものの選び方も $n$ 通り（1番目と同じものを選んでよい）。
3番目のものの選び方も $n$ 通り。
$\vdots$
$r$ 番目のものの選び方も $n$ 通り。
したがって、積の法則により、
$$\underbrace{n \times n \times n \times \cdots \times n}_{r \text{ 個}} = n^r \text{ (通り)}$$重複順列でよくある間違いが、底と指数を逆にしてしまうことです。
✕ 誤：5種類のものから3個取る重複順列は $3^5 = 243$ 通り
○ 正：5種類のものから3個取る重複順列は $5^3 = 125$ 通り
覚え方：「底 = 選択肢の数（$n$）」「指数 = 選ぶ回数（$r$）」。 「毎回 $n$ 通りの選択を $r$ 回繰り返す」と考えれば、$n$ を $r$ 回掛けるのは自然です。
通常の順列 $_nP_r$ は $r \leq n$ でなければ成り立ちません。$n$ 個しかないのに $r$ 個取り出せないからです。
しかし重複順列は違います。同じものを繰り返し使えるので、$r > n$ でも問題なく成り立ちます。
✕ 誤：「3文字から5文字並べる？ $3 < 5$ だから不可能」
○ 正：重複を許すなら、$\text{aabca}$ のように並べられる。総数は $3^5 = 243$ 通り。
重複順列の公式 $n^r$ は、指数法則 $n^{r_1} \times n^{r_2} = n^{r_1 + r_2}$ と整合します。 「$r_1$ 個並べてから $r_2$ 個並べる」ことは「合計 $r_1 + r_2$ 個並べる」ことに等しく、 $n^{r_1} \times n^{r_2} = n^{r_1+r_2}$ が成り立ちます。
このように、重複順列の公式は指数関数 $f(r) = n^r$ の性質そのものを反映しています。 大学の組合せ論では、重複順列の考え方が指数型母関数（exponential generating function）の基礎になります。
重複順列 $n^r$ と通常の順列 $_nP_r$ の違いを、はっきり整理しておきましょう。 混同すると入試で致命的なミスになります。
| 通常の順列 $_nP_r$ | 重複順列 $n^r$ | |
|---|---|---|
| 同じものを繰り返し使えるか | 使えない | 使える |
| $r$ と $n$ の関係 | $r \leq n$ が必要 | $r > n$ でもよい |
| 公式 | $n(n-1)(n-2)\cdots(n-r+1)$ | $\underbrace{n \times n \times \cdots \times n}_{r}$ |
| 各位置の選択肢 | 1つずつ減る | 常に $n$ 通り |
| 典型例 | 5人から3人を選んで並べる | 数字 0〜9 から4桁の暗証番号を作る |
「$_nP_r$ を使うか $n^r$ を使うか」は、問題の条件で決まります。
判断基準は1つだけ：一度使ったものをもう一度使えるかどうか。
問題文に「同じ数字を何度使ってもよい」「重複を許して」「繰り返し用いることを許して」 などの表現があれば重複順列。なければ通常の順列です。
ただし、問題によっては明示されず、状況から判断が必要な場合もあります。 例えば「暗証番号」なら同じ数字を使えるのが自然、「委員の選出」なら同一人物は選べないのが自然です。
例1：5種類の文字 $\text{a}, \text{b}, \text{c}, \text{d}, \text{e}$ から3文字を取り出して並べる。
重複を許さない場合：$_5P_3 = 5 \times 4 \times 3 = 60$ 通り
重複を許す場合：$5^3 = 125$ 通り
重複順列のほうが多くなるのは当然です。使い回しが許されるぶん、並べ方が増えるからです。
問題文に「異なる $n$ 個のものから」と書いてあっても、それだけでは通常の順列とは限りません。
✕ 誤：「異なる3個の文字から4個並べる」→「異なるって書いてあるから通常の順列。$_3P_4$ は……あれ、計算できない？」
○ 正：「異なる $n$ 個のもの」は選択肢が $n$ 種類あるという意味。並べ方で重複を許すかどうかは別の条件。 この問題は「重複を許して」が前提なので、$3^4 = 81$ 通り。
コンピュータのパスワードは、まさに重複順列です。 例えば、英小文字26文字から8文字のパスワードを作ると $26^8 \approx 2.09 \times 10^{11}$ 通り。 英大小文字＋数字の62種なら $62^8 \approx 2.18 \times 10^{14}$ 通りに跳ね上がります。
情報理論では、パスワードの強度をエントロピー（$\log_2 n^r = r \log_2 n$ ビット）で測ります。 文字種を増やすか、文字数を増やすか、どちらがパスワードを強くするか── これは $n$ を増やすか $r$ を増やすかの問題であり、重複順列の構造そのものです。
重複順列は、入試で出題されるパターンがほぼ決まっています。 問題文の表現は異なっても、根底にある構造は同じ──「毎回 $n$ 通りの選択を $r$ 回繰り返す」です。 以下の4つのパターンを押さえておけば、ほとんどの問題に対応できます。
最も基本的なパターンです。「$0, 1, 2, 3, 4$ の数字から、同じ数字を何度使ってもよいものとして、3桁の整数を作る」のような問題です。
ここで注意すべきは、最高位（百の位）に $0$ が入れないことです。 百の位は $0$ 以外の数字から選ぶので $4$ 通り、十の位と一の位はそれぞれ $5$ 通り。 よって $4 \times 5 \times 5 = 100$ 個です。
3桁の整数を作るとき、百の位が $0$ だと2桁以下の数になってしまいます。
✕ 誤：$0, 1, 2, 3, 4$ から3桁の整数は $5^3 = 125$ 個
○ 正：百の位は $0$ 以外の4通り、十の位・一の位は各5通り。$4 \times 5^2 = 100$ 個
整数を作る問題では、最高位を別に考えるのが鉄則です。
「6人がじゃんけんを1回するとき、手の出し方は全部で何通りか」── これも重複順列です。 各人がグー・チョキ・パーの3通りから1つを出し、6人分の選択を並べるので $3^6 = 729$ 通り。
同様に、「〇×式の問題が10問あるとき、答え方は何通りか」は、各問に〇か×の2通りがあるので $2^{10} = 1024$ 通りです。
「5人を A, B, C の3部屋に入れるとき、入り方は何通りか（空室があってもよい）」── これも重複順列の問題です。
各人について「A に入る」「B に入る」「C に入る」の3通りの選択肢があり、 5人分の選択を独立に行うので $3^5 = 243$ 通りです。
パターンA〜Cの共通点を見抜きましょう。 どのパターンも、「$r$ 個の要素それぞれに、$n$ 種類の中から1つのラベルを貼る」という構造です。
パターンA：各桁（$r$ 個の位置）に、$n$ 種の数字から1つを割り当てる
パターンB：各人（$r$ 人）に、$n$ 種の選択肢から1つを割り当てる
パターンC：各人（$r$ 人）に、$n$ 個の部屋から1つを割り当てる
各要素の選択が互いに独立で、毎回同じ $n$ 通りの選択肢がある── この構造を見抜けば、「これは重複順列だ」と判断できます。
「集合 $A = \{a, b, c, d, e\}$ の部分集合は全部で何個あるか」── 実はこれも重複順列の考え方で解けます。
各要素について「部分集合に含める（〇）」か「含めない（×）」の2通りの選択があります。 5個の要素に対して独立に〇/×を決めるので、$2^5 = 32$ 個です（空集合を含む）。
各要素が「入る / 入らない」の2択を独立にもつので、$2^n$ 個です。
これは「2種類のラベル（〇と×）を $n$ 個の要素に貼る重複順列」にほかなりません。
なお、空でない部分集合の個数は $2^n - 1$（空集合を除く）です。
| パターン | 問題の典型例 | $n$（選択肢） | $r$（選ぶ回数） |
|---|---|---|---|
| A：整数を作る | 0〜9から4桁の暗証番号 | 数字の種類数 | 桁数 |
| B：独立な選択 | じゃんけん・〇×問題 | 選択肢の数 | 人数・問題数 |
| C：部屋割り | $n$ 人を $k$ 部屋に分ける | 部屋の数 | 人数 |
| D：部分集合 | 集合の部分集合の個数 | $2$（入る/入らない） | 要素数 |
重複順列には、数学的に深い見方があります。 それは、重複順列と関数（写像）が1対1に対応するということです。
集合 $X = \{1, 2, 3\}$（3個の位置）から集合 $Y = \{a, b\}$（2種の文字）への関数 $f$ を考えます。 $f(1) = a, f(2) = b, f(3) = a$ のように、$X$ の各要素に $Y$ の要素を1つずつ割り当てる── これはまさに「2種の文字から3個取る重複順列 $aba$」を作ることと同じです。
一般に、$r$ 個の要素をもつ集合 $X$ から $n$ 個の要素をもつ集合 $Y$ への関数の総数は $n^r$ です。 これは重複順列の公式そのものです。
$X = \{x_1, x_2, \ldots, x_r\}$、$Y = \{y_1, y_2, \ldots, y_n\}$ とします。
関数 $f: X \to Y$ は、$X$ の各要素に $Y$ の要素を1つ対応させるもの。
$f(x_1)$ の決め方は $n$ 通り。$f(x_2)$ の決め方も $n$ 通り（$f(x_1)$ と同じでもよい）。
$\vdots$
$f(x_r)$ の決め方も $n$ 通り。
よって、関数の総数は $n^r$ 通り。
これは「$Y$ の $n$ 個から重複を許して $r$ 個並べる」重複順列の総数と一致します。
この対応を知っておくと、パターンCの部屋割り問題がよりクリアに見えます。 「5人を3部屋に割り当てる」は、「集合 $\{$人1, 人2, 人3, 人4, 人5$\}$ から集合 $\{A, B, C\}$ への関数」です。 各人にどの部屋を対応させるかを決めるので、$3^5 = 243$ 通りです。
大学数学では、関数を全射（すべての $y$ に対応する $x$ がある）、 単射（異なる $x$ には異なる $y$ が対応）、 全単射（全射かつ単射）に分類します。
全関数の総数（重複順列）= $n^r$
単射の総数（通常の順列）= $_nP_r$（$r \leq n$ が必要）
全単射の総数 = $n!$（$r = n$ のとき）
部屋割りで「空室なし」の条件は全射に対応し、通常の順列は単射に対応します。 高校の「場合の数」は、関数の分類と完全に対応しているのです。
$0$ から $n-1$ までの $n$ 種の数字を使って $r$ 桁の列を作ることは、 $0$ 以上 $n^r - 1$ 以下の整数を $n$ 進法で表すことに対応します。
例えば、$0, 1$ の2文字から3文字の列を作ると $2^3 = 8$ 通り。 これは $000, 001, 010, 011, 100, 101, 110, 111$ の8つであり、 まさに $0$ から $7$ までの整数を2進法で表したものです。
重複順列は位取り記数法の数学的基礎なのです。
重複順列は、「場合の数」の中でどこに位置づけられるのでしょうか。 順列と組合せの全体像を整理しましょう。
| 順序あり（順列） | 順序なし（組合せ） | |
|---|---|---|
| 重複なし | $_nP_r = \dfrac{n!}{(n-r)!}$ | $_nC_r = \dfrac{n!}{r!(n-r)!}$ |
| 重複あり | $n^r$（重複順列） | $_{n+r-1}C_r$（重複組合せ） |
順序を考えるかどうか（順列 vs 組合せ）と、重複を許すかどうか── この2つの軸で「場合の数」の公式は4種類に分類されます。 今回学んだ重複順列は「順序あり × 重複あり」の領域です。
Q1. $1, 2, 3, 4$ の4個の数字から、重複を許して3個取り出して並べる方法は何通りですか？
Q2. 重複順列 $n^r$ と通常の順列 $_nP_r$ の最大の違いは何ですか？
Q3. 5人がじゃんけんを1回するとき、手の出し方は全部で何通りですか？
Q4. 集合 $\{1, 2, 3, 4, 5, 6\}$ の部分集合は全部で何個ですか？
Q5. $0, 1, 2, 3$ の4個の数字から、重複を許して3桁の整数を作ると何個できますか？
この記事で学んだ内容を、入試形式の問題で確認しましょう。
$1, 2, 3, 4, 5, 6$ の6個の数字から、同じ数字を何度使ってもよいものとして4個選び、4桁の整数を作る。このとき、4桁の整数は全部で何個できるか。
$1296$ 個
方針：6個の数字から重複を許して4個並べる重複順列。ただし $0$ が含まれないので、最高位の制約はない。
千の位、百の位、十の位、一の位それぞれについて、$1, 2, 3, 4, 5, 6$ の6通りの選び方がある。
よって $6^4 = 1296$ (個)
※ $0$ が選択肢に含まれていないので、最高位を別に考える必要がないことに注目。
集合 $A = \{a, b, c, d, e\}$ について、次の問いに答えよ。
(1) $A$ の部分集合は全部で何個あるか。
(2) $A$ の要素を少なくとも1つ含む部分集合は全部で何個あるか。
(1) $32$ 個 (2) $31$ 個
方針：各要素が「入る/入らない」の2通り。5個の要素に独立に適用する。
(1) 5個の要素それぞれについて、部分集合に「含む」「含まない」の2通り。よって $2^5 = 32$ (個)
(2) (1)の32個には空集合 $\emptyset$ が1つ含まれるから、空でない部分集合は $32 - 1 = 31$ (個)
4桁の自然数について、次の問いに答えよ。ただし、同じ数字を何度使ってもよいものとする。
(1) 各位の数字がすべて偶数（$0, 2, 4, 6, 8$）である4桁の自然数は何個あるか。
(2) (1)のうち、$6300$ より大きいものは何個あるか。
(1) $500$ 個 (2) $200$ 個
方針：(1)は最高位に $0$ が入れない制約つきの重複順列。(2)は場合分けが必要。
(1) 偶数の数字は $0, 2, 4, 6, 8$ の5種。
千の位は $0$ 以外の偶数 $2, 4, 6, 8$ の4通り。百の位・十の位・一の位はそれぞれ5通り。
よって $4 \times 5^3 = 4 \times 125 = 500$ (個)
(2) 各位の数字がすべて偶数で $6300$ より大きい4桁の自然数を場合分けする。
(i) 千の位が $8$ のとき：
百の位・十の位・一の位はそれぞれ $0, 2, 4, 6, 8$ の5通り。$5^3 = 125$ (個)
(ii) 千の位が $6$ のとき：$6\square\square\square > 6300$ となる条件を考える。
百の位が $4, 6, 8$ のとき（百の位 $> 3$）：十の位・一の位は各5通り。$3 \times 5^2 = 75$ (個)
千の位 $2, 4$ の場合は $6200, 6400$ 台なので、$6200$ 台は $6300$ 以下、$6400$ 台以上は百の位 $\geq 4$ に含まれる。ここでは百の位が偶数なので $0, 2$ のときを確認すると、$60\square\square \leq 6099$, $62\square\square \leq 6299$ でいずれも $6300$ 以下。よって追加なし。
よって (ii) は $75$ 個。
(i) + (ii) = $125 + 75 = 200$ (個)
5人を A, B の2つの部屋に入れるとき、次の場合の入り方は何通りあるか。
(1) 空室があってもよい場合
(2) どちらの部屋にも少なくとも1人は入る場合
(1) $32$ 通り (2) $30$ 通り
方針：(1)は重複順列。(2)は(1)から「空室がある場合」を引く余事象の考え方。
(1) 5人それぞれについて、A か B かの2通り。
よって $2^5 = 32$ (通り)
(2) (1)の32通りのうち、空室がある場合を除く。
空室がある場合とは、全員が A に入る（1通り）か、全員が B に入る（1通り）かの2通り。
よって $32 - 2 = 30$ (通り)
※ 一般に、$n$ 人を $k$ 部屋に空室なしで入れる場合は、$k^n$ から空室ありの場合を引く（包除原理）。部屋が2つの場合は特にシンプル。