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を用いて良い．