Title here
Summary here
順列と組合せ
順列とは「順序を考慮して要素を並べる場合の数」であり、組合せとは「並べる順番を考慮せずに要素を選ぶ場合の数」のことです。
ここでは、順列と組合せを定義するとともに、重複順列や円順列、重複組合せといった様々な順列・組合せのパターンを示します。
順列
順列（$\text{permutation}$）とは、順序を考慮して要素を並べる場合の数のことです。同じものの集まりであっても、並べ方が異なれば異なる順列として区別されます。
定義 1.1（階乗）
自然数 $n$ に対して、次の積を階乗（$\text{factorial}$）といい、$n!$ と表す。
$$
\begin{align*} \tag{1.1.1}
n! = n (n-1) (n-2) \cdots 3 \cdot 2 \cdot 1
\end{align*}
$$
ただし、$0! = 1$ とする。
解説（階乗）
階乗の定義
階乗とは、$1$ から $n$ までのすべての自然数の積のことです。階乗は順列を定義する上で必要不可欠な概念です。
$n = 0$ の場合の定義について（ $0! = 1$ ）
定義より、$0! = 1$ です。
本来、階乗は自然数に対して定義されるものですが、$n = 0$ の場合も定義に含め、$0$ の階乗を $1$ とするということです。
このように定義する主な理由は、順列や組合せに関する定義や定理を扱いやすくするためです。順列や組合せに関する定理に $0!$ が現れた場合に、例外や断り書きを設けるよりも、はじめから階乗の定義にこれを含めておいた方が全体として簡潔になります。
また、$0! = 1$ であることは、空集合の並べ方が「何もしない $1$ 通りだけ」であることに対応していると捉えて理解することもできます。
定義 1.2（順列）
$n$ 個の異なるものから $r$ 個を取り出して並べる場合の数を、順列（$\text{permutation}$）といい、${}_nP_r$ と表す。
$$
\begin{align*} \tag{1.1.2}
{}_nP_r = \frac{ n! }{ (n - r)! }
\end{align*}
$$
解説（順列）
順列の定義
順列とは、$n$ 個の異なるものから $r$ 個を取り出して並べる場合の数のことです。
順列が定義されるための条件（前提条件）
上記の定義において、順列が定義されるためには $n$ と $r$ が自然数であり、$r \leqslant n$ である必要があります。
順列の考え方
$n$ 個の異なるものから $r$ 個をとりだして順番に並べることを考えたとき、$1$ 番目の場所に並べるのは、$n$ 個のうちどれを選んでもよいので、選び方は $n$ 通りあります。$1$ 番目の場所に並べるものが決まったら、$2$ 番目の場所には残りの $n-1$ 個から選んで並べる必要があるので、選び方は $n-1$ 通りあります。以下、同様に $r$ 回の選択を繰り返すことで、順列 ${}_nP_r$ の式が得られます。
$$
\begin{align*}
{}_nP_r
&= \frac{ n! }{ (n - r)! } \\
&= n (n-1) (n-2) \cdots (n - r + 1)
\end{align*}
$$
上式の $2$ 行目は、$r$ 個の項の積になっています。これは、順列が、独立な事象に 積の法則を適用した結果であることを端的に表しています。
順列のパターン
順列を用いた場合の数の数え上げには、いくつかのパターンがあります。並べる対象がすべて異なるか、同じものを含むか、あるいは円状に並べるかなどによって考え方が異なります。
以下に、代表的なパターンを示します。
異なるものを並べる順列
$n$ 個の異なるものをすべて並べる順列
$n$ 個の異なるものをすべて並べる場合の数は $n!$ 通りです。これは、$n$ の 階乗の定義そのものです。
$$
\begin{align*}
n! = n (n-1) (n-2) \cdots 3 \cdot 2 \cdot 1
\end{align*}
$$
$n$ 個の異なるものをすべて順番に並べることを考えたとき、$1$ 番目の場所に並べるのは、$n$ 個のうちどれを選んでもよいので、選び方は $n$ 通りあります。$1$ 番目の場所に並べるものが決まったら、$2$ 番目の場所には残りの $n-1$ 個から選んで並べる必要があるので、選び方は $n-1$ 通りあります。以下、同様に $n$ 回の選択を繰り返すことで、$n$ の階乗 $n!$ の式が得られます。
例 1.1（階乗）
異なる $5$ 枚のカード $\fbox{1} \; \fbox{2} \; \fbox{3} \; \fbox{4} \; \fbox{5}$ を使って作れる $4$ 桁の数はいくつある？
$$
\begin{split}
5!
&= 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 \\
&= 120 \; (\small{\text{通り}}) \\
\end{split}
$$
$5$ 枚のカードをすべて使って、左から順番に並べていくことを考えます。万の位、千の位、百の位、十の位、一の位と、選択肢は毎回減っていきます。
- 万の位の数字は、$5$ 枚のカードから選べる → $5$ 通り
- 千の位の数字は、残り $4$ 枚のカードから選べる → $4$ 通り
- 百の位の数字は、残り $3$ 枚のカードから選べる → $3$ 通り
- 十の位の数字は、残り $2$ 枚のカードから選べる → $2$ 通り
- 一の位の数字は、残り $1$ 枚のカードを並べる → $1$ 通り
したがって、場合の数は $5! = 120$ 通りです。
$n$ 個の異なるものから $r$ 個を取り出して並べる順列
$n$ 個の異なるものから $r$ 個を取り出して並べる場合の数は ${}_nP_r$ 通りあります。これは、 順列の定義そのものです。
$$
\begin{align*}
{}_nP_r
&= \frac{ n! }{ (n - r)! } \\
&= n (n-1) (n-2) \cdots (n - r + 1)
\end{align*}
$$
$n$ 個の異なるものから $r$ 個を選び、順番に並べるとき、選択肢は毎回減っていきます。
例 1.2（順列）
$7$ 人の中から $4$ 人を選んで、順位（$1$ 位 $\sim 4$ 位）を付ける場合の数は？
$$
\begin{split}
{}_7P_4
&= \frac{7!}{(7 - 4)!} \\
&= 7 \cdot 6 \cdot 5 \cdot 4 \\
&= 840 \; (\small{\text{通り}}) \\
% &= 840 \; (\footnotesize{\text{通り}}) \\
\end{split}
$$
$7$ 人の中から $4$ 人を選んで $1$ 位、$2$ 位、$3$ 位、$4$ 位の順位をつけるとき、選択肢は毎回減っていきます。
- $1$ 位の人は、$7$ 人から選べる → $7$ 通り
- $2$ 位の人は、残り $6$ 人から選べる → $6$ 通り
- $3$ 位の人は、残り $5$ 人から選べる → $5$ 通り
- $4$ 位の人は、残り $4$ 人から選べる → $4$ 通り
したがって、場合の数は ${}_7P_4 = 7 \cdot 6 \cdot 5 \cdot 4 = 840$ 通りです。
重複順列（$n$ 個の異なるものを重複を許して $r$ 個並べる順列）
一度選んだものが繰り返し使える（重複を許す）場合、各選択に対して選択肢の数は同じになります。したがって、$n$ 個の異なるものを重複を許して $r$ 個並べる場合の数は $n^{r}$ 通りです。
$$
\begin{align*}
n^r = \underbrace{n \cdot n \cdots n \vphantom{()}}_{r \vphantom{b}}
\end{align*}
$$
これは、すべての選択（$r$ 回）において、同じ数（$n$ 通り）の選択肢があるという考え方に基づきます。
例 1.3（重複順列）
$4$ 文字のアルファベット $a \sim d$ を使って、長さ $4$ 文字のパスワード（重複可）を作る場合の数は？
$$
\begin{align*}
4^4 = 256 \; (\small{\text{通り}})
\end{align*}
$$
パスワードの $1$ 文字目から $4$ 文字目まで、各文字に対して $4$ 通りの選択肢があるため、$4 \cdot 4 \cdot 4 \cdot 4 = 256$ 通りのパスワードが作れます。
文字の重複を許さないとすると、場合の数は $4$ つの文字をすべて並べる順列（階乗）になるため、作れるパスワードは $4! = 4 \cdot 3 \cdot 2 \cdot 1 = 24$ 通りになります（ 異なるものを並べる順列を参照）。
同じものを含む順列
区別のつかない同種の要素（同じ文字・記号など）が含まれる場合、それらの位置を入れ替えた順列は同一とみなすため、重複を除く必要があります。
全部で $n$ 個あるものの中に、同じものが $r_1, r_2, \cdots, r_k$ 個ずつ存在するとき、これらをすべて並べる場合の数は、次の式で与えられます。
$$
\begin{align*} \tag{1.1.3}
\frac{ n! }{ r_1! \; r_2! \; \cdots \; r_k! }
\end{align*}
$$
これは、仮に、$n$ 個のものがすべて異なる（区別がつく）として並べた場合の数（$n!$ 通り）に対して、区別がつかない要素を入れ替えた場合の数（$r_1!$ 通り、$r_2!$ 通り、$\cdots$、$r_k!$ 通り）に相当する重複を取り除いたものです。
例 1.4（同じものを含む順列）
「$\text{SUCCESS}$」の文字の並べ方は何通りあるか？
$$
\begin{split}
\frac{7!}{3! \cdot 2! \cdot 1! \cdot 1!}
&= \frac{5040}{12} \\
&= 420 \; (\small{\text{通り}}) \vphantom{\bigg(\bigg)}
\end{split}
$$
仮に、$7$ 文字すべて異なる文字であると仮定すると、これを並べる場合の数は $7! = 5040$ 通りです。
いま、「$\text{SUCCESS}$」の中には、$\text{S}$ が $3$ 回、$\text{C}$ が $2$ 回、$\text{U}$ と $\text{E}$ が $1$ 回ずつ出現します。したがって、$3$ つの $\text{S}$ の位置を入れ替えた文字の並び方は $3! = 6$ 通り、$2$ つの $\text{C}$ の位置を入れ替えた文字の並び方は $2! = 2$ 通りあります。
これら重複する場合の数を、すべて異なると仮定した場合の数から除くことで、同じ文字を含む文字の並べ方の総数が得られます。
円順列（$n$ 個の異なるものを円状に並べる順列）
$n$ 個の異なるものを円状にすべて並べる場合の数は $(n-1)!$ 通りです。
$$
\begin{align*} \tag{1.1.4}
(n - 1)!
\end{align*}
$$
$n$ 個のもの円状に並べる場合、回転させて同じになる並び方は同じものとみなせます。
したがって、$n$ 個の異なるものをすべて並べる場合の数（$n!$ 通り）から、回転させて同じになる並び方（$n$ 通り）に相当する重複を除くことで、$n$ 個の異なるものを円状に並べる場合の数が得られます。
これは、$1$ つのものの位置を固定した上で、残りの $(n - 1)$ 個を並べる場合の数と捉えることもできます。
例 1.5（円順列）
$6$ 人が円卓に座る場合の数は？
$$
\begin{split}
(6 - 1)!
&= 5! \\
&= 120 \; (\small{\text{通り}})
\end{split}
$$
$6$ 人が直線上に並ぶ場合の数は $6! = 720$ 通りです。しかしながら、円状に並ぶ場合、回転による重複が $6$ 通りあるため、これを除くと $5! = 120$ 通りになります。
あるいは、$6$ 人のうち特定の $1$ 人の位置を固定した上で、残りの $5$ 人の並ぶ場合の数は $5! = 120$ 通りであると考えても同じ結果が得られます。
組合せ
組合せ（$\text{combination}$）とは、並べる順番を考慮せずに要素を選ぶ場合の数のことです。選ばれた要素の並び方に意味がない場合は、順列ではなく組合せを用いて場合の数を数え上げる必要があります。
定義 1.3（組合せ）
$n$ 個の異なるものから $r$ 個を順序を区別せずに取り出す場合の数を、組合せといい、次のように表す。
$$
\begin{align*} \tag{1.1.5}
\binom{n}{r} = \frac{n!}{r!(n - r)!}
\end{align*}
$$
解説（組合せ）
組合せの定義
組合せとは、$n$ 個の異なるものから $r$ 個を順序を区別せずに取り出す場合の数です。
組合せが定義される条件
上記の定義より、組合せが定義されるためには $n$ と $r$ が自然数であり、$r \leqslant n$ である必要があります。
組合せの考え方
組合せは、選ぶ対象の順序の意味がない場合の数え方です。たとえば、「Aさん、Bさん、Cさん」の3人を選んでチームを作るとき、「A, B, C」、「B, C, A」、「C, A, B」など、チームに含まれる人は同じで並び方だけ違う場合をすべて同一とみなします。
このように、組合せでは $n$ 個から選ばれた $r$ 個の中での順序（並び方）を考慮しません。したがって、「$n$ 個の異なるものから $r$ 個を取り出して並べる順列」に対して、$r!$ 通りの重複する並べ方を除いたものが「$n$ 個の異なるものから $r$ 個を取り出す組合せ」となります。
このことは、順列と組合せの定義式（ （1.1.2）式と （1.1.5）式）を比べることで得られる、次の関係式からも理解できます。
$$
\begin{align*}
\binom{n}{r}
& = \frac{ n! }{ r!(n - r)! } \vphantom{\frac{\vphantom{\Big(\Big)}}{\vphantom{\Big(\Big)}}} \\
& = \frac{ {}_nP_r }{ r! } \tag{1.1.6}
\end{align*}
$$
組合せと順列の違い
順列と組合せの本質的な違いは、順番を区別するかどうかです。
| 項目 | 順列（Permutation） | 組合せ（Combination） |
|---|---|---|
| 定義 | $n$ 個の異なるものから $r$ 個を取り出して並べる場合の数 | $n$ 個の異なるものから $r$ 個を順序を区別せずに取り出す場合の数 |
| 式 | ${}_nP_r = \displaystyle\frac{ n! }{ (n - r)! }$ | $\displaystyle\binom{n}{r} = \displaystyle\frac{ n! }{ r!(n - r)! }$ |
| 順序の区別 | あり（区別する） 例：$\text{ABC}$ と $\text{ACB}$ は異なる順列 | なし（区別しない） 例：$\text{ABC}$ と $\text{ACB}$ は同じ組合せ |
| 典型的な問題（例） | ・座席の並び順 ・最短経路の列挙 ・ 立方体の色の塗分け | ・委員の選出 ・カード・玉の選び方 ・不定方程式の整数解の個数 |
組合せの表記について
高校数学において、$n$ 個の異なるものから $r$ 個を取り出す組合せは、${}_nC_r$ のように、記号 $C$ を用いて表されてきました。
これに対して、大学数学では、$n$ 個の異なるものから $r$ 個を取り出す組合せは、二項係数を用いて表されることが多いです（ 組合せの定義）。
$$
\begin{align*}
\binom{n}{r} = \frac{n!}{r!(n - r)!}
\end{align*}
$$
これは、二項係数を用いた表記が国際的な標準であるためです。また、組合せのための特別な記号を導入するよりも、二項係数を用いた表記の方が一般的である（二項係数は解析学や代数学をはじめとした幅広い数学分野で現れます）ためでもあると考えられます。
順列についても同様で、順列のための特別な記号 $P$ を用いるよりも、二項係数を用いて、次のように表す教科書も多いです。下記の順列の表し方は、 （1.1.6）式より、直ちに導けます。
$$
\begin{align*}
\binom{n}{r} \cdot r! = \frac{n!}{(n - r)!}
\end{align*}
$$
組合せの表記法は教科書により異なりますが、 [1], [3] では二項係数による表記が、 [4], [5] では記号 $C$ による表記が用いられています。また、 [7] などの英語の教科書では、二項係数による表記を採用しているものがほとんどです。
組合せのパターン
組合せを用いた場合の数の数え上げには、いくつかのパターンがあります。同じものを繰り返し選ぶこと（重複）を許すか許さないか、などによって、考え方が異なります。
以下に、代表的なパターンを示します。
$n$ 個の異なるものから（重複を許さずに）$r$ 個を選ぶ組合せ
$n$ 個の異なるものから（重複を許さずに）$r$ 個を選ぶ場合の数は、次の式で与えられます。これは、 組合せの定義そのものです。
$$
\begin{align*}
\binom{n}{r} = \frac{n!}{r!(n - r)!}
\end{align*}
$$
例 1.6（組合せ）
$10$ 人の中から $3$ 人を選んでチームを作る場合の数は？
$$
\begin{align*}
\binom{10}{3}
&= \frac{10!}{3! \cdot 7!} \\
&= \frac{10 \cdot 9 \cdot 8}{3 \cdot 2 \cdot 1} \\
&= 120 \; (\small{\text{通り}})
\end{align*}
$$
$10$ 人の中から $3$ 人を選ぶ順列の数は ${}_{10}P_3 = 720$ 通りです。このうち、同じ $3$ 人がチームに含まれる場合の数（同じ $3$ 人を選んで並べる場合の数）が $3! = 6$ 通りあります。
したがって、並び方による重複を除いた組合せの数は $720 ÷ 6 = 120$ 通りになります。
重複組合せ（$n$ 個の異なるものから重複を許して $r$ 個を選ぶ組合せ）
$n$ 個の異なるものから、重複を許して $r$ 個を選ぶ場合の数は、次の式で与えられます。
$$
\begin{align*} \tag{1.1.7}
\binom{n + r - 1}{r}
&= \frac{(n + r - 1)!}{r!(n - 1)!}
\end{align*}
$$
重複組合せの考え方
$n$ 個の異なるものから、重複を許して $r$ 個を選ぶ組合せ（重複組合せ）は、「$r$ 個の玉を $n$ 個の箱に入れる場合の数」に対応する考え方により導出されます。
$n$ 個の異なるものから重複を許して $r$ 個を選ぶということは、$r$ 個の「玉」を $n$ 個の「箱」に入れることに対応しています。「玉が入っていない箱」は選ばれなかったもの、「玉が複数個入っている箱」は重複して（複数回）選ばれたものに対応します。そして、「合計 $r$ 個の玉がどの箱に入っているか」は、$n$ 個のものから重複を許して $r$ 個を選んだ結果に対応します。
また、$r$ 個の玉を $n$ 個の箱に入れることは、$r$ 個の玉をまず並べ、それらを $n - 1$ 枚の「仕切り」で区切ることと同じです。$n - 1$ 枚の「仕切りで区切られた区画（両端を含む）」は $n$ 個の「箱」に対応しており、「仕切りの間の玉の数」は重複を許して箱に入れた玉の数に、それぞれ対応しているからです。
このように考えると、「$r$ 個の玉を $n$ 個の箱に入れる場合の数」は、全部で $(n - 1) + r$ 個の場所から、「玉」を入れる $r$ 箇所と「仕切り」を入れる $n-1$ 箇所を選ぶ場合の数に等しいといえます。
これは、通常の 組合せを用いて、次のように表すことができます。
$$
\begin{align*}
\binom{n + r - 1}{r}
&= \frac{(n + r - 1)!}{r!(n - 1)!}
\end{align*}
$$
組合せが定義される条件
重複組合せにおいては、同じものを複数回選んでもよいため、通常の組合せにおいて前提条件となる $r \leqslant n$ を満たす必要がなくなります。
つまり、$r \gt n$ である場合についても、重複組合せを考えることができます。例えば、$3$ 種類の商品から、重複を許して $5$ 個選ぶ場合の数などがあります。
例 1.2（重複組合せ）
$3$ 種類のキャンディー（$\text{A}, \text{B}, \text{C}$）から $5$ 個を選ぶ（同じ種類のキャンディーを複数選んでもよい）場合の数は？
$$
\begin{align*}
\binom{3 + 5 - 1}{5}
&= \binom{7}{5} \\
&= \frac{7!}{5! \cdot 2!} \\
&= \frac{7 \cdot 6}{2} \\
&= 21 \; (\small{\text{通り}})
\end{align*}
$$
順序を考慮する必要がなく、重複を許す選び方なので、重複組合せの考え方を適用します。
重複組合せにおいては、例えば、$\text{A}$ を $2$ 個、$\text{B}$ を $2$ 個、$\text{C}$ を $1$ 個選ぶといった選び方が含まれます。また、順序を考慮しないため、「$\text{AABBC}$」と「$\text{ABABC}$」は同一の組合せとみなします。
参考文献
[1] 舟木直久. 確率論. 朝倉書店. 2004.
[2] 縄田和満. 確率・統計 $\text{I}$. 丸善出版. 2013.
[3] 小針晛宏. 確率・統計入門. 岩波書店. 1973.
[4] 真貝寿明. 徹底攻略 確率統計. 共立出版. 2012.
[5] 東京大学教養学部統計学教室 編. 統計学入門. 東京大学出版会. 1991.
[6] W. Feller. An Introduction to Probability Theory and Its Applications. John Wiley & Sons, Inc.. 1968.
[7] Robert B. Ash. Basic Probability Theory. Dover Publications, Inc.. 2008.
[8] G. Andrews. Special Functions. Cambridge University Press. 1999.
[9] 杉浦光夫. 解析入門 $\text{I}$. 東京大学出版会. 1980.
[10] 吉田伸生. [新装版] ルベーグ積分入門. 日本評論社. 2021.
初版：2025-07-15 | 改訂：2025-08-06