デジタル・デザイン・ラボラトリーな日々

アラフィフプログラマーが数学と物理を基礎からやり直す。https://qiita.com/yaju

順列と組合せを理解してみる-組合せ

はじめに

前回、順列を説明しました。今回は組合せとなります。 yaju3d.hatenablog.jp

順列と組合せの違いですが、順列の場合は「順番をつける」、組合せの場合は「順番をつけない」となります。

組合せ

組合せには下記の公式があります。Cはcombination(コンビネーション)の頭文字です。
公式: \displaystyle _n C _r = \frac{_n P _r}{r!}

問題と解説

A、B、C、D、Eの5人から3人を選ぶ

理解するために公式を使わずに問題を解いてみましょう。
3人を選ぶというのは、選ばれた組(3人)と選ばれない組(2人)に分けるということです。
まず、選ばれた組に1人目、2人目、3人目という「席」があると考えて順列と同様に考えます。
 _5 P _3 = 5 \times 4 \times 3 = 60通りとなります。

ところが、これでは「1人目、2人目、3人目」が「A、B、C」のときと「A、C、B」のときは、組としては同じなのに重複して数えられています。
f:id:Yaju3D:20160717113527p:plain

同じ3人が選ばれたときの並び方 3! = 6通り分が重複しています。
これが「B、C、D」…「C、D、E」など他の組合せでも同様となるため、元の式を 3! で割ってしまえばいいです。

 \displaystyle \frac{_5 P _3}{3!} = \frac{5 \times 4 \times 3}{3 \times 2 \times 1} = 10通りとなります。

計算式を一般化

先程の計算式を一般化してみます。

 \displaystyle \frac{_5 P _3}{3!} = \frac{1}{3!} \times \frac{5!}{2!} (←\displaystyle _n P _r = \frac{n!}{(n - r)!}より)
 \displaystyle = \frac{5!}{3! \times (5 - 3)!}

よって、組合せは次の方法で計算できます。
 \displaystyle = \frac{n!}{r!(n-r)!}
最初の式に戻すと公式と同じになります。
 \displaystyle = \frac{_n P _r}{r!}

問題と解説

10人の人間から7人の代表を選ぶとき、選び方の場合の数を求めよ。

公式を使ってみます。
 \displaystyle _{10} C _7 = \frac{10 \times 9 \times 8 \times 7 \times 6 \times 5 \times 4}{7 \times 6 \times 5 \times 4 \times 3  \times 2  \times 1} = \frac{10 \times 9 \times 8}{3  \times 2  \times 1} = 120通りとなります。

これくらいならまだしも、例えば、 _{100} C _{98}だと計算が大変になります。
コンビネーションにはこれを簡単にできる性質があります。
 \displaystyle _n C _r = _n C _{(n-r)}
先程の計算を当てはめてみます。
 \displaystyle _{10} C _7 = _{10} C _{(10-7)} = _{10} C _3 = \frac{10 \times 9 \times 8}{3  \times 2  \times 1} = 120通りで同じとなります。

問題と解説

男6人と、女4人の計10人から4人の代表を選ぶとき、男2人と女2人となる選び方の場合の数を求めよ。

これは積の法則を使います。
 \displaystyle _6 C _2 + _4 C _2 = \frac{6 \times 5}{2 \times 1} \times \frac{4 \times 3}{2 \times 1} = 90通りとなります。

重複組合せ

順列に重複順列があるように組合せにも重複組合せがあります。

重複組合せには下記の公式があります。重複組合せはcombination with repetitionsですが Hを使われています。Hは同次多項式(homogeneous polynomial)がおそらく由来とのことです。
公式: _n H _r = _{n+r-1} C _r

問題と解説

青,赤,黒の三種類の玉がたくさんある。この中から4つ玉を選ぶときに得られる色のパターンが何通りあるか求めよ。

3種類のものから重複を許して4個選ぶ場合の数なので、重複組合せの公式から
 \displaystyle _3 H _4 = _6 C _4 = 15通りとなります。

参考