組合せとその個数

組合せ

標本空間\(\Omega \)に属するすべての標本点が同じ程度の確かさで起こるものと仮定する場合、先験的確率の考えのもとでは、それぞれの事象\(A\subset \Omega \)が起こる確率は、\begin{equation*} \frac{\left\vert A\right\vert }{\left\vert \Omega \right\vert }
\end{equation*}と定義されます。つまり、標本空間\(\Omega \)に属する標本点の個数\(\left\vert \Omega \right\vert \)と事象\(A\)に属する標本点の個数\(\left\vert A\right\vert \)をそれぞれ数え上げた上で、それらの比をとることにより事象\(A\)が起こる確率が得られるということです。ただ、標本点を1つずつ具体的に列挙していては数え落としをしたり同じものを二重に数えてしまう恐れがあるため、標本点を系統的に数える技術が必要です。以下では組合せ（combination）と呼ばれる概念について解説します。標本空間や事象はいずれも集合として定義されるため、そこに含まれる標本点の個数を組合せを用いて系統的に数え上げることにより、事象の先験的確率を正確に求めることができます。
集合\(A\)は有限\(n\in \mathbb{N} \)個の要素を持つものとします。この集合\(A\)から合計\(k\in \mathbb{N} \)個の異なる要素を同時に選びます。ただし、\(1\leq k\leq n\)です。集合\(A\)から\(k\)個の異なる要素を同時に選ぶこととは、\(k\)個の異なる要素からなる\(A\)の部分集合\begin{equation*} \left\{ a_{1},a_{2},\cdots ,a_{k}\right\}
\end{equation*}を選ぶことと実質的に等しいため、このような部分集合を\(n\)個の要素から\(k\)個を同時に選ぶ場合の組合せ（combination）と呼びます。
集合を外延的表記で表現する場合、要素を並べる順番を変えても、集合としては区別されません。したがって、例えば、\begin{equation*}
\left\{ a_{1},a_{2},a_{3}\right\} =\left\{ a_{3},a_{2},a_{1}\right\}
\end{equation*}という関係が成り立つため、これらは等しい組合せとみなされます。

集合を外延的表記で表現する場合、同じ要素を重複して書くことは禁じられていませんが、同じ要素をいくつ書いても効果は1つだけ書いた場合と同じです。したがって、例えば、\begin{equation*}
\left\{ a_{1},a_{1},a_{1},a_{2},a_{2},a_{3}\right\} =\left\{
a_{1},a_{2},a_{3}\right\}
\end{equation*}という関係が成り立つため、これらは等しい組合せとみなされます。

組合せの個数

これまでは\(n,k\in \mathbb{N} \)かつ\(1\leq k\leq n\)である状況を想定しましたが、以降では議論を一般化するために\(n,k\)が\(0\)を値としてとり得る状況を許容し、\(n,k\in \mathbb{Z} _{+}\)かつ\(0\leq k\leq n\)とします。
\(n\)個の要素を持つ集合\(A \)から\(k\)個の要素を同時に選ぶ場合、どの要素を選ぶかに応じて様々な組合せが得られます。そこで、そのようなすべての組合せの個数を、\begin{equation*} C\left( n,k\right) ,\; C_{n,k},\; _{n}C_{k},\; \binom{n}{k}
\end{equation*}などで表記します。

\(k=0\)の場合の組合せの個数については、\(n\)個の中から\(0\)個を選ぶ方法としては「何も選ばない」という1通りだけ存在するものとみなした上で、\begin{equation*} C\left( n,0\right) =1
\end{equation*}と定めます。また、\(n=0\)の場合には\(0\leq k\leq n\)より\(k=0\)であるため、この場合にも、\begin{equation*} C\left( 0,0\right) =1
\end{equation*}となります。

組合せの個数に関して以下の命題が成り立ちます。証明では順列の個数に関する命題を利用します。

順列と組合せの違い

有限個の要素を持つ集合から複数の要素を重複しないように選ぶ場合、選んだ要素の順番を区別するかどうかによって、順列と組合せを使い分けます。

順列と組合せの違いは、現実の問題では、選ばれた要素に役割や順位があるかどうかによって判断できる場合があります。

一般に、\(n\)個の異なる要素から\(k\)個の要素を選ぶ場合、順番を区別すれば順列となり、その個数は、\begin{equation*} P\left( n,k\right)
\end{equation*}です。一方、順番を区別しなければ組合せとなり、その個数は、\begin{equation*}
C\left( n,k\right)
\end{equation*}です。

1つの組合せとして選ばれた\(k\)個の要素について、その並べ方は\(k!\)通り存在します。したがって、1つの組合せには\(k!\)個の順列が対応します。そのため、\begin{equation*} P\left( n,k\right) =C\left( n,k\right) k!
\end{equation*}が成り立ち、したがって、\begin{equation*}
C\left( n,k\right) =\frac{P\left( n,k\right) }{k!}
\end{equation*}となります。このように、順列と組合せは互いに独立した数え上げの方法ではありません。組合せは、順列において選ばれた要素の並び順の違いを区別しないものとしてまとめたものと捉えることができます。

組合せの個数の対称性

\(n\)個の要素を持つ集合から\(k\)個の要素を選ぶ場合、その選び方の個数は、同じ集合から残りの\(n-k\)個の要素を選ぶ場合の選び方の個数と一致するため、\begin{equation*} C\left( n,k\right) =C\left( n,n-k\right)
\end{equation*}が成り立ちます。この性質を、組合せの個数の対称性（symmetry）と呼びます。

パスカルの関係式

\(n\)個の要素を持つ集合から\(k\)個の要素を選ぶ場合、特定の1要素が選ばれる場合と選ばれない場合に分けて考えることができます。特定の1要素が選ばれる場合の組合せの個数は、その要素を除いた\(n-1\)個から残りの\(k-1\)個を選ぶ場合の数\begin{equation*} C\left( n-1,k-1\right)
\end{equation*}に等しく、特定の1要素が選ばれない場合の組合せの個数は、その要素を除いた\(n-1\)個から\(k\)個を選ぶ場合の数\begin{equation*} C\left( n-1,k\right)
\end{equation*}に等しいため、\begin{equation*}
C\left( n,k\right) =C\left( n-1,k-1\right) +C\left( n-1,k\right)
\end{equation*}を得ます。これをパスカルの関係式（Pascal’s identity）と呼びます。

演習問題