組合せ

ものの集まりからいくつかを選ぶとき、選ぶ順番が関係ないなら、組合せを使います。典型的な問題は数字選択式のくじです。49個の数字が入った箱から6個の数字を引きます（日本のロト6とちがい、数字は49個です）が、引く順番は関係ありません。

公式の導き方

集合 M、たとえば M = {a, b, c, d, e} を考えます。このとき、k 個の組合せとは、ちょうど k 個の要素を含む部分集合 K ⊆ M のことです。K は集合なので、もちろん順番は関係ありません。つまり、集合 M から3個を選ぶ組合せは、たとえば {a, b, d} や {b, c, d} です。

順列とのちがいは、順列では順番が関係したことです。そのため、(a, b, e) と (e, b, a) は異なる順列ですが、組合せとしては同じです。(a, b, e) も (e, b, a) も同じ要素を含んでいて、組合せでは順番がちがうことは問題にしないからです。

しかし、順列を使えば、異なる組合せの総数の公式が得られます。n 個の要素からなる集合から k 個を選ぶ順列の総数は、次の式で表されることがわかっています。

$${}_n{\mathrm{P}}_k=\frac{n!}{(n-k)!}.$$

前の集合 M = {a, b, c, d, e} から3個を選ぶ順列の総数を求めると、{}₅P₃ = 60 通りの異なる順列が得られます。しかし、その中には、それぞれの3つ組について、その並べかえもすべて含まれています。つまり、3つ組 abc だけでなく、3つ組 acb, bac, bca, cab、cba も含まれています。これらは6通りの異なる順列ですが、すべて同じ要素をもつので、組合せとしては1つです。

では、ある3つ組の並べかえは何通りあるでしょうか。3! 通りです。言いかえると、3個を選ぶ順列は、3個を選ぶ組合せの 3! 倍あります。1つの組合せを数えるかわりに、その3つ組のそれぞれの並べかえとして、3! 倍多い順列を数えているのです。したがって、順列の総数を 3! で割れば、組合せの総数が得られます。

この考え方は一般化できます。要素が n 個の集合から k 個を選ぶ異なる組合せの総数を {}_nC_k で表すと、次のようになります。

$${}_n{\mathrm{C}}_k=\frac{{}_n{\mathrm{P}}_k}{k!},$$

つまり、順列の総数を、選んだ k 個の並べかえの数 k! で割ったものです。順列の総数の公式を展開して、式を変形できます。

$${}_n{\mathrm{C}}_k=\frac{{}_n{\mathrm{P}}_k}{k!}=\frac{n!}{(n-k)!}\cdot \frac{1}{k!}=\frac{n!}{(n-k)!\cdot k!}.$$

例：集合 {a, b, c} から2個を選ぶ組合せの総数は

$${}_3{\mathrm{C}}_2=\frac{3!}{1!\cdot 2!}=3$$

で、組合せは {a, b}, {a, c}、{b, c} です。もとの集合 M = {a, b, c, d, e} から3個を選ぶ組合せなら、総数は

$${}_5{\mathrm{C}}_3=\frac{5!}{(5-3)!\cdot 3!}=10$$

で、組合せは {a, b, c}, {a, b, d}, {a, b, e}, {a, c, d}, {a, c, e}, {a, d, e}, {b, c, d}, {b, c, e}, {b, d, e}, {c, d, e} です。

二項係数の書き方

日本の教科書では {}_nC_k と書きますが、海外や大学では、次のような二項係数の書き方もよく使われます。

$$(\genfrac{}{}{0ex}{}{n}{k})$$

分数の線のない分数のような形（つい線を書きたくなりますが）で、かっこで囲みます（かっこは省けません）。英語では「n choose k」と読みます。値は {}_nC_k と同じです。

$${}_n{\mathrm{C}}_k=\frac{n!}{(n-k)!\cdot k!}$$

たとえば、5個の要素からなる集合から4個を選ぶとき、選び方の総数は次のようになります。

$${}_5{\mathrm{C}}_4=\frac{5!}{1!\cdot 4!}=5.$$

基本的な関係

n ∈ ℕ について、次の式が成り立ちます。

$$\begin{array}{rcl}{}_n{\mathrm{C}}_0={}_n{\mathrm{C}}_n={}_0{\mathrm{C}}_0& =& 1\\ {}_n{\mathrm{C}}_1& =& n\end{array}$$

また、n, k ∈ ℕ₀（0以上の整数）、$k\leqq n$ について、次の式が成り立ちます。

$$\begin{array}{rcl}{}_n{\mathrm{C}}_{n-k}& =& {}_n{\mathrm{C}}_k.\end{array}$$

さらに、n, k ∈ ℕ₀（0以上の整数）、k < n について、次の式が成り立ちます。

$$\begin{array}{rcl}{}_n{\mathrm{C}}_k+{}_n{\mathrm{C}}_{k+1}& =& {}_{n+1}{\mathrm{C}}_{k+1}.\end{array}$$

計算ツール

与えられた n と k について、組合せの総数を計算します。

例題

1. 前に挙げたくじから始めましょう。49個の玉が入った箱から、全部で6個の玉を引きます。引き方は何通りあるでしょうか。

   まず、数字を引く順番は関係するでしょうか。関係しません。予想するのは数字だけで、その順番ではないからです。そこで組合せを使います。玉は全部で49個、引くのは6個なので、次のようになります。

   $${}_{49}{\mathrm{C}}_6=\frac{49!}{(49-6)!\cdot 6!}=\frac{49!}{43!\cdot 6!}=\mathrm{13,983,816}$$

   引き方は全部で13,983,816通りあります。ちなみに、ここから、1口買ったときに1等が当たる確率は 1/13,983,816、つまり 0.00000715112% です。

2. 花子さんは、ケーキ屋さんにある13種類のケーキから4種類を選んで買います。4種類の選び方は何通りあるでしょうか。

   これも簡単な組合せの例です。選んだケーキは箱にいっしょに入れるので、順番は関係ありません。つまり、13 種類のケーキから 4 種類を選ぶので、次のようになります。

   $${}_{13}{\mathrm{C}}_4=715.$$

3. 50人のグループがあり、半分が男性、半分が女性です。1つの性別だけからなる3人組（つまり、男性3人や女性3人の3人組）は認めないとき、3人組は何通りできるでしょうか。

   これは少し複雑な組合せです。1つの性別だけの3人組を除くと、3人組の構成は次の2つの場合しか残りません。男性2人と女性1人か、男性1人と女性2人です。男性2人と女性1人の場合の数は、男性1人と女性2人の場合の数と同じです。そこで、男性2人と女性1人の場合の数を計算して、それを2倍すればよいのです。あとはもう簡単です。男性25人から2人を選ぶ組合せの数を求め、それに女性25人から1人を選ぶ選び方の数（上の基本的な関係の2行目より25通り）をかけます。この結果を2倍すれば、答えが得られます。

   $$2\cdot {}_{25}{\mathrm{C}}_2\cdot {}_{25}{\mathrm{C}}_1=15000.$$

4. 箱の中に製品が15個あり、そのうち4個が不良品です。次のような6個の選び方は何通りあるでしょうか。

   • 不良品が1つもない選び方。このときは、不良品でない 15 − 4 = 11 個の製品から6個を選びます。したがって、次のようになります。

     $${}_{11}{\mathrm{C}}_6=462.$$

   • 不良品がちょうど1個の選び方。良品5個と不良品1個を選ぶことになります。良品は全部で11個、不良品は4個です。積の法則を使うと、答えは次のようになります。

     $${}_{11}{\mathrm{C}}_5\cdot {}_4{\mathrm{C}}_1=1848$$

   • 不良品が1個以下の選び方。前の結果を使って解きます。良品をちょうど6個選ぶ方法は 462 通り、良品5個と不良品1個を選ぶ方法は 1848 通りです。和の法則を使ってこれらをたせば、求めたい答え、つまり不良品が1個以下（不良品が0個か、ちょうど1個）の選び方の総数が得られます。答えは 462 + 1848 = 2310 です。