組み合わせの場合の数ₙCₖ｜考え方・求め方・基本性質を攻略

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

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

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

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

組み合わせの場合の数は，順列の場合の数をもとに考えることができます．

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

この記事では，

組み合わせの考え方
$\Co{n}{k}$の求め方
$\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}$を考える．

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

(1)は順列の場合の数の問題で，(2)は組み合わせの場合の数の問題ですね．

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

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

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

(1)の場合の数は順列の公式から$\Pe{9}{3}=9\cdot8\cdot7=504$であることが分かりますから，このことをもとに(2)を２通りの考え方で解いてみましょう．

考え方１（組み合わせ×並べる＝順列）

まずは

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

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

問題の９枚のカード$\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*}$

である．よって，８４通りである．

考え方２（重複する場合の数で割る）

いったん順列を考えてから重複する場合の和で割ることでも求められます．

このように９枚のカード$\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*}$

である．よって，８４通りである．

重複で割るという考え方は円順列でも学びましたね．

組み合わせの場合の数$\Co{n}{k}$の性質

いま考えた具体例の考え方をもとにして，組み合わせの場合の数の性質を考えましょう．

$\Co{n}{k}$と$\Pe{n}{k}$の関係

いまの具体例の１つ目の考え方と同じようにすれば，次の$\Co{n}{k}$と$\Pe{n}{k}$の関係が得られます．

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

$\begin{align*}\Co{n}{k}\times k!=\Pe{n}{k} \iff\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$でも成り立っていて欲しいからだったわけです．

組み合わせの場合の数$\Co{n}{k}$の求め方

さて，順列の場合の数$\Pe{n}{k}$が

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

で求められることを思い出すと，上の$\Co{n}{k}$と$\Pe{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{n}{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}$

は同じことですね．