場合の数４<br>組み合わせのₙCₖを考え方から基本性質まで攻略

前々回の記事では順列の場合の数について，「$n$個のものから$k$個選んで並べる場合の数」が

$\begin{align*}n(n-1)(n-2)\dots(n-k+1)\end{align*}$

で計算でき，これを$\Pe{n}{k}$と表すことを説明しました．

場合の数の分野では順列と並んで重要なものに組み合わせがあります．組み合わせは「$n$個のものから$k$個選ぶ場合の数」をいい，これを$\Co{n}{k}$で表します．

例えば，次の問題を考えましょう．

９枚のカード$\fbox{1}\fbox{2}\fbox{3}\dots\fbox{8}\fbox{9}$を考える．

これら９枚のカードから３枚選んで並べる場合の数を求めよ．
これら９枚のカードから３枚選ぶ場合の数を求めよ．

１問目は順列の場合の数の問題で，２問目は組み合わせの場合の数の問題というわけですね．

このように順列の問題と組み合わせの問題を比べると

選んだあとに並べるか
選ぶだけで止めるか

というのが順列と組み合わせの違いであることが分かりますね．

この記事では，順列の場合の数をもとに

組み合わせの考え方
$\Co{n}{k}$の求め方
$\Co{n}{k}$の基本公式

を順に説明します．

「場合の数と確率」の一連の記事

組み合わせの考え方
1. 考え方１
2. 考え方２
$\Co{n}{k}$の求め方
$\Co{n}{k}$の基本性質

組み合わせの考え方

まずは組み合わせの場合の数を表す次の記号を導入しましょう．

$n$個のものから$k$個選ぶ場合の数を$\Co{n}{k}$で表す．また，$k=0$のときは$\Co{n}{0}=1$と定める．

たとえば，

９枚のカード$\fbox{1}\fbox{2}\fbox{3}\dots\fbox{8}\fbox{9}$から３枚選ぶ場合の数は$\Co{9}{3}$
色の違う７個のボールから３個選ぶ場合の数は$\Co{7}{3}$

というわけですね．

$\Co{n}{k}$の$\mrm{C}$は組み合わせという意味の“Combination”の頭文字“C”に由来します．

それでは，冒頭の組み合わせの問題を考えましょう．

９枚のカード$\fbox{1}\fbox{2}\fbox{3}\dots\fbox{8}\fbox{9}$から３枚選ぶ場合の数を求めよ．

考え方１

まずは

組み合わせは「選ぶ」
順列は「選んで並べる」

ということから，組み合わせで選びとったものを並べると順列になるという考え方で解いてみましょう．

問題の９枚のカード$\fbox{1}\fbox{2}\fbox{3}\dots\fbox{8}\fbox{9}$から３枚選ぶ場合の数は，組み合わせなので$\Co{9}{3}$通りある．

さらに，このときに選んだ３枚のカードを並べる場合の数は，選び方それぞれで$3!$通りある．

このように９枚のカード$\fbox{1}\fbox{2}\fbox{3}\dots\fbox{8}\fbox{9}$から３枚選んで並べれば，これは順列なので$\Pe{9}{3}$通りある．

よって，

$\begin{align*}\Co{9}{3}\times3!=\Pe{9}{3}\end{align*}$

だから，求める場合の数$\Co{9}{3}$は

$\begin{align*}\Co{9}{3} =\frac{\Pe{9}{3}}{3!} =\frac{9\cdot8\cdot7}{3\cdot2\cdot1} =84\end{align*}$

である．よって，$84$通りである．

考え方２

順列を考えてから，場合の数で考えると重複する個数で割っても求められます．

このように９枚のカード$\fbox{1}\fbox{2}\fbox{3}\dots\fbox{8}\fbox{9}$から３枚選んで並べれば，これは順列なので$\Pe{9}{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}$

の６つは順番を考えない組み合わせでは同じものである．

同様に$\Pe{9}{3}$通りの順列それぞれで順番を無視すれば，６通りずつ同じ組み合わせができあがる

したがって，求める場合の数は

$\begin{align*}\Pe{9}{3}\div6 =\frac{9\cdot8\cdot7}{6} =84\end{align*}$

である．よって，$84$通りである．

重複で割るという考え方は前回の記事の円順列でも考えましたね．

場合の数３
実はカンタンな円順列・数珠順列の考え方

「一列に」並べる普通の順列に対して，「円状に」並べる順列を円順列といいます．さらに，「円状に」並べて裏返したものも同じとみなす順列を数珠順列といいます．この記事では，円順列・数珠順列を考え方から解説しています．

$\Co{n}{k}$の求め方

いまの１つ目の考え方と同じようにすれば，次の公式が得られます．

$0\leqq k\leqq n$をみたす整数$n$, $k$に対して，

$\begin{align*}\Co{n}{k}=\frac{\Pe{n}{k}}{k!}\end{align*}$

が成り立つ．

$0<k\leqq n$のとき，「$n$個のものから$k$個選ぶ」＋「選んだ$k$個を並べる」＝「$n$個のものから$k$個選んで並べる」なので，

$\begin{align*}\Co{n}{k}\times k!=\Pe{n}{k}\end{align*}$

が成り立ちますから，この両辺を$k!$で割ればいいですね．

$0!=1$, $\Co{n}{0}=1$, $\Pe{n}{0}=1$と定めていましたから，$k=0$の場合に成り立つことは明らかですね．

$\Co{n}{k}$の定義で$\Co{n}{0}=1$としたのは，この等式が$k=0$でも成り立っていて欲しいからだったわけです．

また，前々回の記事で

$\begin{align*}\Pe{n}{k}=&n(n-1)(n-2)\dots(n-k+1) \\=&\frac{n!}{(n-k)!}\end{align*}$

と表せることを説明しました．

場合の数３
実はカンタンな円順列・数珠順列の考え方

上の$\Co{n}{k}$の公式と併せると，次が成り立ちますね．

$0\leqq k\leqq n$をみたす整数$n$, $k$に対して，

$\begin{align*}\Co{n}{k}=\dfrac{n(n-1)(n-2)\dots(n-k+1)}{k!}=\dfrac{n!}{(n-k)!k!}\end{align*}$

が成り立つ．

この公式を使えば，

$\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}{k}$の基本性質

例えば，次はどのように計算できるでしょうか？

$\Co{100}{97}$を計算せよ．

上の公式を使うと，分子も分母もかけられる数が多いので計算が面倒になりそうに思えるかもしれませんが，実はたくさん約分ができて次のように簡単に計算できます．

公式より$\Co{100}{97}$は

$\begin{align*}\Co{100}{97} =&\frac{100\cdot99\cdot98\cdot97\dots\cdot5\cdot4}{97\cdot96\cdot95\cdot\dots4\cdot3\cdot2\cdot1} \\=&\frac{100\cdot99\cdot98}{3\cdot2\cdot1} =161700\end{align*}$

と計算できる．

$97\cdot96\cdot95\dots\cdot5\cdot4$の部分が約分されて簡単になっていますね．

さて，この計算途中で$\dfrac{100\cdot99\cdot98}{3\cdot2\cdot1}$となっていますが，これは$\Co{100}{3}$ですから$\Co{100}{97}=\Co{100}{3}$が成り立っていることが分かります．

実は一般に次が成り立ちます．

$0\leqq k\leqq n$をみたす整数$n$, $k$に対して，$\Co{n}{k}=\Co{n}{n-k}$が成り立つ．

$\Co{n}{k}=\dfrac{n!}{(n-k)!k!}$, $\Co{n}{n-k}=\dfrac{n!}{(n-(n-k))!(n-k)!}$だから

$\begin{align*}\Co{n}{n-k} =&\frac{n!}{\{n-(n-k)\}!(n-k)!} \\=&\frac{n!}{k!(n-k)!} \\=&\Co{n}{k}\end{align*}$

が従う．

この公式を使うと，たとえば

$\Co{7}{5}=\Co{7}{2}$
$\Co{15}{10}=\Co{15}{5}$
$\Co{20}{17}=\Co{20}{3}$

と計算できるわけですね．

確かに２０枚のカード$\fbox{1}\fbox{2}\fbox{3}\dots\fbox{19}\fbox{20}$から

１８枚を選ぶ場合の数$\Co{20}{18}$
「選ばない」２枚を選ぶ場合の数$\Co{20}{2}$

は同じことですね．

場合の数４
組み合わせのₙCₖを考え方から基本性質まで攻略