1.1 順列と組み合わせ

1.1.1 順列

異なる $n$ 個のものを右から全てを一列に一つずつ並べていくとして，その並び方は何通りあるだろうか．この場合は，最初の一つは $n$ 通り，次の一つは $n-1$ 通り，と続いていく．このようにある整数 $n$ について， $n \times (n-1) \times \cdots \times 2 \times 1$ とししたものが，並べ方の場合の数となる．これを順列と呼ぶ．また，この計算のことを $n!$ と表し $n$ の階乗と呼ぶ．

$\begin{align} n! = \prod_{k=1}^{n} k = n \times (n-1) \times \cdots \times 2 \times 1 \end{align}$

次に， $n$ 個のうち $r > 0$ 個を右から一列に並べていくことを考えよう．明らかに，計算上は $n \times (n-1) \times \cdots \times (n-r+2) \times (n-r+1)$ とすれば良い．これを $_n P_r$ と表す．これは， $n!$ を $(n-r)!$ で割ったものとして表せるので

$\begin{align} _n P_r = \frac{n!}{(n-r)!} \end{align}$

と表現されることが多い．

次に $n$ 個のうち，同じものがいくつかあった場合を考える．例えば赤玉が $n_{\text{red}}$ ，白玉が $n_{\text{white}}$ とする．これらを全て並べた時の場合の数はどうなるだろうか．この場合は，一度全てを異なるものとみなしておいて，その後で同じものの並び順を考慮するのが良い．

全てを異なると見なす場合，明らかに $n = n_{\text{red}} n_{\text{white}}$ の順列 $n!$ である．しかし，実際には赤玉，白玉は同じものなので，同じ並べ方を重複して数え上げていることになる．同じ色だけに着目した時，その並べ方はそれぞれ $n_{\text{red}}!, n_{\text{white}}!$ 通りあるので，これだけ重複して数え上げていることがわかる．すなわち，この場合は

$\begin{align} \frac{n!}{n_{\text{red}}!n_{\text{white}}!} \end{align}$

と計算すれば良いことがわかる．さらに一般化すれば， $k$ 種類のものがそれぞれ $n_k$ 個ずつある場合，全てを一列に並べる時の場合の数は

$\begin{align} \frac{n!}{\prod_{i=1}^{k} n_i!} \end{align}$

と計算することができる．

1.1.2 組み合わせ

次に組み合わせの数について考える．まずこれを表す記号として $_n C_r$ や $\displaystyle \binom{n}{r}$ が用いられる．さて $n$ 個の異なるものから $r$ 個選ぶ時，その場合の数は幾つになるだろうか．

ここまでに見てきた順列 $_n P_r$ は，

$n$ 個のものから $r$ 個のものを取り出す
取り出した $r$ 個のものを全て並べる

という２段階の行為として分解できる．それぞれ $_n C_r$ 通り， $r!$ 通りあることを考えると，

$\begin{align} _n P_r = _n C_r \times r! \Longleftrightarrow _n C_r = \frac{_n P_r}{r!} = \frac{n!}{(n-r)! r!} \end{align}$

とできる．これが組み合わせの場合の数を求める公式である．

Exercise 1.1 (誕生日問題)

A~Fまでの数字が書かれたカードが1枚ずつある．このとき，この6枚を一列に並べる時の並べ方の総数はいくつか．
ある箱に赤玉が6個，白玉が5個，黒玉が8個あるとする．このとき，全てを一つずつ取り出して一列並べたとき，その並べ方の総数はいくつか．
25人のクラスで，誕生日が全員異なる場合の数と全ての場合の数を求めて，その割合を求めよ．このとき簡単のため閏年は無視する．また計算にはRを用いて良い．