024組合せの基本

「組合せ」に関する最も基本的な問題です。場合の数において、「順列」と「組合せ」は2大巨頭といってもよいです。順列では $P$、組合せでは $C$ を用いて計算します。

ただし、順列の $P$ は無理に使わなくても、各位置に入るものの個数を順に掛けることで、さまざまな問題を解けます。一方、組合せの $C$ は積極的に使っていくことをおすすめします。

例えば、10人から3人を選んで一列に並べる方法を考えます。1番目は10通り、2番目は9通り、3番目は8通りなので、

$${}_{10}P_3=10\times9\times8$$

となります。数が1つずつ減っていくため、比較的イメージしやすいと思います。

これに対して、10人から順序を区別せずに3人を選ぶ方法は、

$${}_{10}C_3 =\frac{10\times9\times8}{3\times2\times1}$$

となります。

分子の $10\times9\times8$ は、3人を選んで並べる順列の計算そのものです。しかし、組合せでは3人を並べる順番を区別しません。同じ3人を並べ替えた $3!=3\times2\times1$ 通りを1つの選び方にまとめるため、分母の $3\times2\times1$ で割ります。

つまり、組合せの計算には順列の計算が含まれており、そこから並べる順番の違いを取り除く操作が加わります。この「同じ選び方を1つにまとめる」操作が、組合せの難しいところであり、考え方の肝です。