順列，組合せ，重複組合せ
本記事では，順列，重複順列，組合せ，重複組合せについて基礎的な内容をまとめます．
順列
有限個のものを順序をつけて並べる配列を順列といいます．
例えば，1から9までの数字がそれぞれ書かれた紙から5枚を選び，一列に並べたものなどが順列です．
異なるn個から，異なるr個を選んで並べるとき，その順列の総数を{}_n \mathrm{P}_{r}と表します．{}_n \mathrm{P}_{r}の計算方法は以下の通りです．3通りの書き方をしてみました．
\begin{aligned} {}_n \mathrm{P}_{r} &= n(n-1) \cdots \cdots (n-r+1) \\ &= \prod_{x=n-r+1}^{n} x \\ &= \frac{n!}{(n-r)!} \end{aligned}総乗の記号\prodについては，以下の記事に解説があります．
高校ではほとんどお目にかかりませんが，知っておくと便利なので気になる人はぜひ読んでみてください．（気にならない人は，上の式の2行目を無視してください）
3行目の記述方法は，後述の「組合せ」で重要になります．
先ほどの例，1から9までの数字がそれぞれ書かれた紙から5枚を選び，一列に並べた順列の総数を求めると，
\begin{aligned}
{}_9 \mathrm{P}_{5} &= 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \\
&= 15120
\end{aligned}
となり，15120通りあることが分かります．
このような計算式になる理由を，この例を用いて説明します．
まず，一番左に並べる数字は1〜9のどの数字でもよいため9通りあります．その右隣に並べる数字は，最初に並べなかった8種の数字から選ぶので8通り，同様に次は7通りとなっていき，それらを掛け合わせたものが順列の総数となるわけです．
重複順序
異なるn個のものから，r個を選んで並べることを考えます．ただし，同じものを選んでも構いません．このような順列を重複順列といい，重複順列の総数はn^rとなります．
例えば，1から9の数字を3つ並べてできる数字の総数は9^3=729通りです．
組合せ
異なるn個のものから，順序に関係なく，異なるr個を選んで取り出したものを組合せといいます．異なるn個のものから，異なるr個のものを取り出した組合せの総数を{}_n \mathrm{C}_{r}1この記法のCはCombinationの頭文字のCです．と書き2\binom{n}{k}，\mathrm{C}(n,k)，\mathrm{C}_{k}^{n}，\mathrm{C}_{k,n}などの記法もあります．以下のように計算します．
\begin{aligned} {}_n \mathrm{C}_{r} &= \frac{{}_n \mathrm{P}_{r}}{r!} \\ &= \frac{n!}{r!(n-r)!} \end{aligned}組み合わせの総数は，順序に影響を受けませんから，順列の総数{}_n \mathrm{P}_{r}を，取り出したr個の順列の総数r!で割ったものになります．
また以下の性質を持ちます．
命題．
0 \leqq r \leqq nのとき，
\begin{aligned}
{}_n \mathrm{C}_{r} &= {}_n \mathrm{C}_{n-r}
\end{aligned}
証明．
\begin{aligned}
{}_n \mathrm{C}_{n-r} &= \frac{n!}{(n-r)! \{ n-(n-r)\}! } \\
&= \frac{n!}{(n-r)!r!} \\
&= {}_n \mathrm{C}_{r}
\end{aligned}
組合せに関しては，他にも重要な定理が多くありますが，二項定理と合わせて考えると理解しやすいため，別の記事で解説したいと思います．
重複組合せ
異なるn個のものから，重複を許して，r個を選んで取り出したものを重複組合せといいます．重複組合せの総数は{}_n \mathrm{H}_{r}で表され，
\begin{aligned}
{}_n \mathrm{H}_{r} &= {}_{n+r-1} \mathrm{C}_{r}
\end{aligned}
で計算します．
大学に入ってからも，組合せ数学が必要になったときに計算することがありますので，知っておいて損はないでしょう．
