　順列組合せ - コンテキストをマイニングするツールを作る

順列

$n$ 個の異なるものから重複を許さずに、一列に並べる順列の数は、

${}_{n}P_{n} = n!$

$n$ 個の異なるものから重複を許さずに、 $r$ 個を選び出し、それを一列に並べる順列の数は、

${}_{n}P_{r} =\frac{n!}{(n-r)!}=\overbrace{n(n-1)\cdots (n-r+1)}^{number = r}$

$n$ 個のうち、 $p$ 個、 $q$ 個がそれぞれ同じものであるとき、これら $n$ 個のものを１列に並べる並べ方の総数は

$\frac{n!}{p! \cdot q! }$

これもある意味当然。まず $n$ 個が全て異なっていたとすると、その並べ方は $n!$ 個になる。

しかし、ここで $p$ 個、 $q$ 個が実は同じものであるとすると、 $p! \times q!$ だけ余分にかけ算している事になるから・・・。割ってやれば良いとなる。

組合せ

ではでは、 $n$ 個の異なるものの中から重複を許さずに $r$ 個を選び出す選び方の総数は、

${}_{n}C_{r} = \frac{{}_{n}P_{r}}{r!} = \frac{n!}{r!(n-r)!}$

なぜか？・・・

図のように、 $\{a,b,c,d,e\}$ の５つから３つを選ぶ場合を考えよう。

もしその３つが、 $(a,b,c)$ だった時、組合せなら $(a,b,c)$ の一組だが、順列は下図のように６通りと計算するわけである。

つまり、１通りを６通りと６倍に換算していることになるので、逆に６で割ってやれば良いのである。

組合せの重要な公式

${}_{n}C_{n}=1\\{}_{n}C_{1}=n\\{}_{n}C_{r}={}_{n}C_{n-r}\\{}_{n}C_{r}={}_{n-1}C_{r-1}+ {}_{n-1}C_{r}\\r \cdot {}_{n}C_{r}=n \cdot {}_{n-1}C_{r-1}$

${}_{n}C_{n}=1$ と ${}_{n}C_{1}=n$ は全く問題なく理解できる。でもその他はちょっとややこしい感じがする。

次の ${}_{n}C_{r}={}_{n}C_{n-r}$ もちょっと考えれば当たり前だろう。

図のように５つのものからどの３つを組にして選ぶかを決めれば、必然的に残りの２つの組合せも決まる。だから、３つを取る組合せの数と、残りを取る組合せの数が同じなのは至極納得。

次の ${}_{n}C_{r}={}_{n-1}C_{r-1}+ {}_{n-1}C_{r}$ については、図のように ${}_{n}C_{r}$ を２つの事象に分解するという考え方をすれば理解できる。

ある特定の要素 $a$ が選ばれているとすると、残りの $n-1$ から $r-1$ 個を選べば良い。

一方、 $a$ が選ばれていないとすると、残りの $n-1$ から今度は $r$ 個を選べば良い。この２つの事象は排反だから、それぞれの組合せの数を加算すれば良い。

次の $r \cdot {}_{n}C_{r} = n \cdot {}_{n-1}C_{r-1}$ は以下のように計算上は明らか。

${}_{n}C_{r} = \frac{{}_{n}P_{r}}{r!} = \frac{n\times (n-1)\times (n-2)\times \cdots \times (n-r+1)}{r\times (r-1)\times (r-2)\times \cdots \times (n-r)}=\frac{n}{r}\times {}_{n-1}C_{r-1}$

計算は確かにそうだとして、この事は一体何を意味しているか？　

$n$ 人の中から $r$ 人の委員を選び、さらにその中から $1$ 人の代表者を選ぶという過程と考える。

図の(a)素直に手順にそって考えた場合。

まず $n$ 人の中から $r$ 人の委員を選ぶ組合せは ${}_{n}C_{r}$ であり、さらにその $r$ 人の中から一人を選ぶ組合せは ${}_{r}C_{1}$ なので、その組合せの総数は、 $r \cdot {}_{n}C_{r}$ である。

図の(b)結果的に $r$ 人の委員とその内の一人の代表者が決まれば良いと考えた場合。

まず $n$ 人の中から $1$ 人の代表者を選ぶ組合せは ${}_{n}C_{1}=n$ である。その人は必然的に委員になる。なので、次にその人を除いた $n-1$ 人から、 $r-1$ 人の委員を選ぶ組合せを計算すると、 ${}_{n-1}C_{r-1}$ 。なので $n \cdot {}_{n-1}C_{r-1}$ である。