順列（permutation）
$n$個の異なるものから、異なる$r$個をとって１列に並べたものを 順列 と呼び
\begin{align}
{}_n \mathrm{ P }_r & = n(n-1)(n-2)\cdots(n-r+1) \\\\[1pt]
& = \frac{n(n-1)(n-2)\cdots (n-r+1)(n-r)(n-r-1)\cdots2 \cdot 1}{(n-r)(n-r-1)\cdots2 \cdot 1} \\\\[1pt]
& = \frac{n!}{(n-r)!}
\end{align}
で表す
$n$ 個の中から繰り返し同じものを取ってくる事を許す順列を特に 重複順列 と呼び
$n$ 個の中から $r$ 回繰り同じものを取ってくる場合は
$$ 重複順列 = n^r $$
円順列
順送りすれば同じ表現になる並び方を同じと考えた場合の順列
例えば、a,b,c,d の４文字の並び方は $_４P_4=4!$ 通りあるが、
$a→b→c→d$
$b→c→d→a$
$c→d→a→b$
$d→a→b→c$
の４種類を同じとみなした場合、
$$ \frac{4!}{4} = 3! \ 通り$$
となる。
$n$個の異なるものから、異なる$r$個をとった円順列は
$$ \frac{_nP_r}{r} $$
通り であり、$r=n$ の場合は
$$ \large{ \frac{_nP_n}{n} = (n-1)!} $$
組み合わせ（combination）
$n$個の異なるものから、異なる$r$個をとって来た場合、その順番を考慮しない（$r!$ 個）パターン数を組み合わせと呼び
\begin{align}
{}_n \mathrm{ C }_r & = \frac{_nP_r}{r!} \\\\[1pt]
& = \frac{n(n-1)(n-2)\cdots (n-r+1)(n-r)(n-r-1)\cdots2 \cdot 1}{r! \ (n-r)(n-r-1)\cdots2 \cdot 1} \\\\[1pt]
& = \frac{n!}{r! \ (n-r)!}
\end{align}
と表現する
例題
例１
男性６人、女性４人の中から、男性を３名、女性を２名選ぶ場合、選び方は何通りあるか？
解
| 性別 | 選び方の数 |
|---|---|
| 男性 | $_6C_3$ |
| 女性 | $_4C_2$ |
なので
\begin{align}
{}_6\mathrm{ C }_3 \times {}_4\mathrm{ C }_2 = \frac{6 \cdot 5 \cdot 4}{3 \cdot2 \cdot 1} \times \frac{4 \cdot 3}{ 2 \cdot 1} = 5 \cdot 4 \times 2 \cdot 3 = 120
\end{align}
例２
１２人を次のように分ける場合、何通りあるか
１）４人ずつ$A,B,C$の３組に分ける
２）４人ずつ３組に分ける
解
１）
A組の４名を選ぶ方法は
\begin{align}
{}_{12}\mathrm{ C }_4
\end{align}
B組の４名を選ぶ方法は、A組以外の８名の中から選ぶので
\begin{align}
{}_{8}\mathrm{ C }_4
\end{align}
C組には残りの４名が自動的に決まるので１通り
よって
\begin{align}
{}_{12}\mathrm{ C }_4 \times {}_{8}\mathrm{ C }_4 \times {}_{4}\mathrm{ C }_4 = \frac{12 \cdot 11 \cdot 10 \cdot 9 }{4 \cdot 3 \cdot 2 \cdot 1} \times \frac{8 \cdot 7 \cdot 6 \cdot 5 }{4 \cdot 3 \cdot 2 \cdot 1} = 34650
\end{align}
２）A,B,C のグループ名を考慮しない事と同じなので
$$ \frac{34650}{3!} = 5775$$
例３
６文字の $a,a,a,b,b,c$ を１列に並べる方法は何通りか？
解
まず、$a$ を配置するパターン数を決める。
６つの場所から３つの場所を選ぶ組み合わせと同じなので $ _6C_3$
同様に、残りの３つの場所に $b$ を配置するパターンは $ _3C_2 $
\begin{align}
{}_{6}\mathrm{ C }_3 \times {}_{3}\mathrm{ C }_2 \times {}_{1}\mathrm{ C }_1 & = \frac{6!}{3! \ (6-3)!} \times \frac{3!}{2! \ (2-1)!} \\\\[1pt]
& = \frac{6!}{3! \ 3!} \times \frac{3!}{2! \ 1!} \\\\[1pt]
& = \frac{6!}{3! \ 2! \ 1!} = 60
\end{align}
一般に $n$ 個のものの中に $p$ 個の同じもの、$q$ 個の同じもの、・・・$r$ 個の同じものがある場合（$ n = p + q + ・・・+ r $）それらを１列に並べる総数は
$$\frac{n!}{p! \ q! \cdots r!} （n = p + q + ・・・+ r ）$$