前々回の記事では,「$n$個のものから$r$個選んで並べる場合の数」である順列について説明しました.
「モノを選びとること」を組み合わせといい,「$n$個のものから$r$個選ぶ場合の数」を$\Co{n}{r}$で表します.
順列$\Pe{n}{r}$と組み合わせ$\Co{n}{r}$の間には関係があり,この両者の間に成り立つ関係式を用いることで組み合わせ$\Co{n}{r}$を計算することができます.
場合の数や確率を通して,「組み合わせ」の$\Co{n}{r}$を用いて考えることになる場面は多いです.
そのため,「組み合わせ」の考え方や公式はしっかり理解しておかなければなりません.
一連の記事はこちら
【場合の数1|[和の法則]と[積の法則]は超アタリマエ!】
【場合の数2|[順列]のnPrの考え方と公式は超カンタン!】
【場合の数3|実はカンタンな円順列と数珠順列の考え方】
【場合の数4|[組み合わせ]のnCrの求め方から性質まで攻略】←今の記事
【場合の数5|同じものを含むと順列の場合の数はどう変わる?】
【場合の数6|[重複組み合わせ]は2パターンでOK!】
【場合の数7|二項定理を理解しよう!場合の数を使って導出!】
【場合の数8|展開が楽にできる「パスカルの三角形」の考え方】
【場合の数9|多項定理とは?実は二項定理と同じ考え方!】
組み合わせの考え方
「組み合わせ」の基本を説明します.
組み合わせの記号
「組み合わせ」については,次のように記号$\Co{n}{r}$を使います.
[組み合わせ] $n$個のものから$r$個選ぶ場合の数を$\Co{n}{r}$で表す.ただし,$\Co{n}{0}=1$とする.
たとえば,
- $\fbox{1}$から$\fbox{9}$までカードから5枚選ぶ場合の数は$\Co{9}{5}$
- 色の違う7個のボールから3個選ぶ場合の数は$\Co{7}{3}$
というわけですね.
なお,$\Co{n}{r}$の$\Co{}{}$は「組み合わせ」という意味の”Combination”の頭文字”C”に由来します.
さて,それでは$\Co{n}{r}$がどのように計算できるかを,次の問題を考えながら説明します.
$\fbox{1}$から$\fbox{4}$までのいずれかの数字が書かれた4枚のカードがある.ただし,どの2枚も同じ数字が書かれていないものとする.このとき,次の場合の数を求めよ.
- 4枚のカードから2枚選ぶ場合の数
- 4枚のカードから3枚選ぶ場合の数
この問題を2つの考え方で解いてみましょう.
考え方1
組み合わせ$\Co{n}{r}$と,前々回の記事で説明した順列$\Pe{n}{r}$を比較すると
- 「$n$個のモノから$r$個選んで並べる場合の数」を$\Pe{n}{r}$
- 「$n$個のモノから$r$個選ぶ場合の数」を$\Co{n}{r}$
ですね.つまり,
- 選んで並べるのが順列$\Pe{n}{r}$
- 選ぶところまでで止めるのが組み合わせ$\Co{n}{r}$
という違いがあるわけですね.そのため,[積の法則]より
「選ぶ場合の数(組み合わせ)」×「並べる場合の数」=「選んで並べる場合の数(順列)」
となることを使います.
ここで,[積の法則]と順列$\Pe{n}{r}$については以下の記事を参照してください.
(1) 求める場合の数は4枚のカードから2枚選ぶ場合の数$\Co{4}{2}$ですね.
- 4枚のカードから2枚を選び($\Co{4}{2}$通り),選んだ2枚を一列に並べる($2!$通り)
- 4枚のカードから2枚選んで並べる($\Pe{4}{2}$)
は同じことをしているので,
となります.よって,求める場合の数$\Co{4}{2}$は6ですね.
(2) (1)と同様に
- 4枚のカードから3枚を選び($\Co{4}{3}$通り),選んだ3枚を一列に並べる($3!$通り)
- 4枚のカードから3枚選んで並べる($\Pe{4}{3}$)
は同じことをしているので,
となります.よって,求める場合の数$\Co{4}{3}$は4ですね.
「選んで」「並べる」のが「順列」なので,(組み合わせ)×(選んだものを並べる場合の数)=(順列)となる.
考え方2
一度並べてから同じものの個数で割ることでも求められます.
(1) まず,4枚のカードから2枚選んで並べる順列($\Pe{4}{2}$通り)でありうるものは
$\fbox{1}\fbox{2}$, $\fbox{1}\fbox{3}$, $\fbox{1}\fbox{4}$,
$\fbox{2}\fbox{1}$, $\fbox{2}\fbox{3}$, $\fbox{2}\fbox{4}$,
$\fbox{3}\fbox{1}$, $\fbox{3}\fbox{2}$, $\fbox{3}\fbox{4}$,
$\fbox{4}\fbox{1}$, $\fbox{4}\fbox{2}$, $\fbox{4}\fbox{3}$
です.一方で,4枚のカードから2枚選ぶだけなら,これらは
- $\fbox{1}\fbox{2}$と$\fbox{2}\fbox{1}$ → $\fbox{1}$と$\fbox{2}$を選ぶ
- $\fbox{1}\fbox{3}$と$\fbox{3}\fbox{1}$ → $\fbox{1}$と$\fbox{3}$を選ぶ
- $\fbox{1}\fbox{4}$と$\fbox{4}\fbox{1}$ → $\fbox{1}$と$\fbox{4}$を選ぶ
- $\fbox{2}\fbox{3}$と$\fbox{3}\fbox{2}$ → $\fbox{2}$と$\fbox{3}$を選ぶ
- $\fbox{2}\fbox{4}$と$\fbox{4}\fbox{2}$ → $\fbox{2}$と$\fbox{4}$を選ぶ
- $\fbox{3}\fbox{4}$と$\fbox{4}\fbox{3}$ → $\fbox{3}$と$\fbox{4}$を選ぶ
とみなせます.つまり,$\Pe{4}{2}$通りの順列の中に同じものを選んでいるパターンが$2!$通りずつあるわけですね.
よって,求める場合の数は
となります.
(2) (1)と同様に,4枚のカードから3枚選んで並べる順列の場合の数は$\Pe{4}{3}$です.このときの順列のなかで
- $\fbox{1}\fbox{2}\fbox{3}$, $\fbox{1}\fbox{3}\fbox{2}$, $\fbox{2}\fbox{1}\fbox{3}$, $\fbox{2}\fbox{3}\fbox{1}$, $\fbox{3}\fbox{1}\fbox{2}$, $\fbox{3}\fbox{2}\fbox{1}$
- $\fbox{1}\fbox{2}\fbox{4}$, $\fbox{1}\fbox{4}\fbox{2}$, $\fbox{2}\fbox{1}\fbox{4}$, $\fbox{2}\fbox{4}\fbox{1}$, $\fbox{4}\fbox{1}\fbox{2}$, $\fbox{4}\fbox{2}\fbox{1}$
- $\fbox{1}\fbox{3}\fbox{4}$, $\fbox{1}\fbox{4}\fbox{3}$, $\fbox{3}\fbox{1}\fbox{4}$, $\fbox{3}\fbox{4}\fbox{1}$, $\fbox{4}\fbox{1}\fbox{3}$, $\fbox{4}\fbox{3}\fbox{1}$
- $\fbox{2}\fbox{3}\fbox{4}$, $\fbox{2}\fbox{4}\fbox{3}$, $\fbox{3}\fbox{2}\fbox{4}$, $\fbox{3}\fbox{4}\fbox{2}$, $\fbox{4}\fbox{2}\fbox{3}$, $\fbox{4}\fbox{3}\fbox{2}$
はそれぞれ同じものを選んでいるので,$\Pe{4}{3}$通りの中には同じものを選んでいるパターンが$3!$通りずつあります.したがって,求める場合の数は
となります.
どちらも本質的には同じことですが,分かりやすい方で理解してください.
「いくつかのものから,いくつかを選ぶこと」を「組み合わせ」という.「組み合わせ」の考え方は,
- 「選んで」「並べる」ことで,「順列」になることを用いる
- 一度順列を考え,重複している分のパターンで割る
という2つの考え方ができる.
組み合わせの求め方
次に組み合わせ$\Co{n}{r}$の
- 基本公式
- 重要な性質
を説明します.
基本公式
今の問題の考え方から,$\Co{n}{r}$と$\Pe{n}{r}$には次の関係があります.
[順列と組み合わせ] 正の整数$n$と0以上の整数$r$は$r\leqq n$をみたすとする.このとき,$r!\times\Co{n}{r}=\Pe{n}{r}$が成り立つ.
$0!=1$, $\Co{n}{0}=1$, $\Pe{n}{0}=1$と定めていましたから,$r=0$の場合に成り立つことは明らかですね.
$\Co{n}{r}$の定義で$\Co{n}{0}=1$としたのは,この等式が$r=0$でも成り立っていて欲しいからだったわけですね.
以下では$r=1,2,\dots,n$の場合を示しましょう.
考え方1
2パターン
- $n$個のモノから$r$個を選び($\Co{n}{r}$通り),選んだ$r$枚を一列に並べる($r!$通り)
- $n$枚のカードから$r$枚選んで並べる($\Pe{n}{r}$)
は同じことをしているので,[積の法則]より
が成り立ちます.
考え方2
「$n$個から$r$個選んで並べる場合の数」は$\Pe{n}{r}$であり,この中には同じものを選んでいるパターンが$r!$通りずつあります.
よって,
が成り立ちますね.
さて,以前の記事で順列$\Pe{n}{r}$は
と2通りで表せるのでした.これといま証明した$r!\times\Co{n}{r}=\Pe{n}{r}$を併せると,以下の等式が成り立ちますね.
[組み合わせの公式] 正の整数$n$と0以上の整数$r$は$r\leqq n$をみたすとする.このとき,
が成り立つ.
この公式を使えば,
- $\Co{7}{2}=\dfrac{7\cdot6}{2\cdot1}=21$
- $\Co{6}{4}=\dfrac{6\cdot5\cdot4\cdot3}{4\cdot3\cdot2\cdot1}=15$
- $\Co{4}{4}=\dfrac{4\cdot3\cdot2\cdot1}{4\cdot3\cdot2\cdot1}=1$
と簡単に計算ができますね.
[組み合わせの公式]は,[順列の公式]と[順列と組み合わせの関係]を考えれば簡単に分かる.
重要な性質
組み合わせ$\Co{n}{r}$の様々な性質は以下の記事で説明するとして,ここでは最も重要な$\Co{n}{r}$の性質
について説明します.
【場合の数8|展開が楽にできる「パスカルの三角形」の考え方】
この記事では触れなかった組み合わせ$\Co{n}{k}$の大切な性質について解説しています.その性質を用いることで,[パスカルの三角形]というものを考えることができます.[パスカルの三角形]を利用すれば,例えば普通に展開すると面倒な$(a+b)^7$のような展開が,簡単な足し算だけで求めることができるようになります.
例えば$\Co{20}{18}$なら,
と計算できます.この計算のポイントは分母と分子でたくさん約分が起きて分母も分子も簡単な式になるところです.
一般に,$n$と$r$が大きいときの$\Co{n}{r}$に対して以下が成り立ちます.
[組み合わせの性質] 正の整数$n$と0以上の整数$r$は$r\leqq n$をみたすとする.このとき,$\Co{n}{r}=\Co{n}{n-r}$が成り立つ.
[組み合わせの公式]から,
が従う.
この[組み合わせの性質]から,たとえば
- $\Co{7}{5}=\Co{7}{2}$
- $\Co{15}{10}=\Co{15}{5}$
- $\Co{20}{17}=\Co{20}{3}$
が成り立つわけですね.
確かに
- $\fbox{1}$から$\fbox{20}$までのカードから18枚を選ぶ場合の数$\Co{20}{18}$
- $\fbox{1}$から$\fbox{20}$までのカードから「選ばない」2枚を選ぶ場合の数$\Co{20}{2}$
は同じですよね.
上で計算した$\Co{20}{18}$も
となっていますね.
なお,組み合わせの性質は以下の記事でも紹介しているので参照してください.
$\Co{n}{r}$の$r$が大きいときは,[組み合わせの性質]を使うと計算がやや楽になる.
【次の記事:場合の数5|同じものを含むと順列の場合の数はどう変わる?】
ABCDEFの6文字の並べ方の総数は$6!$で計算できますが, AAAABBの6文字の並べ方の総数は単純に$\Pe{6}{6}=6!$通りではありません.このように,「同じものを含む順列」は単純に$\Pe{n}{r}$で計算することはできません.「同じものを含む順列」は場合の数と確率の分野では頻出なので,考え方からしっかり公式を理解してください.