1.1.5.組合せ

$\newcommand{\lnl}{\\[8pt]}$ $\newcommand{\Lnl}{\\[18pt]}$ $\newcommand{\delt}{\mathrm{d}}$ $\newcommand{\comb}{\mathrm{C}}$ $\DeclareMathOperator*{\ssum}{\Sigma}$ $\DeclareMathOperator*{\sprod}{\Pi}$

組合せ

相異なる$n$個の物から相異なる$k$個(もちろん$k \le n$とします)を選ぶことを(重複のない)組合せ(combination)といいます.この場合の組合せの総数を${}_n\mathrm{C}_k$と表します.

どんなときに組合せを考えるのか

どんなときに組合せを考えると便利なのか考えてみましょう.

選挙

12人が選挙に出馬し, 3人が当選するとします.この場合,$n=12 , k=3$と考えれば上記の組合せの定義に沿っていますね.
従って, 3人の選び方の総数は${}_{12}\mathrm{C}_3$で表されます.
具体的に計算すると(計算方法は下記参照), ${}_{12}\mathrm{C}_3=220$です.

組合せの計算

順列は$k$個選んで並べることでしたが, 組合せは$k$個選ぶだけです。
つまり,$1 2 3$と$2 1 3$は異なる順列ですが, 組合せとして考えると同じです.
$1 2 3$と同じ組合せとなるのは階乗の定義から$3!$個あります.

つまり一般の$k$に対して, 組合せの総数は順列の総数を$k!$で割った数となります.

\begin{align}
{}_{n}\mathrm{C}_k &= \frac{{}_{n}\mathrm{P}_k}{k!} = \frac{n!}{k!(n-k)!}
\end{align}

組合せの性質

$n$個から$k$個選ぶことと, $n$個から$n-k$個選ぶことは同じことです.
これはこう説明できます.
選ばれた物をグループA , 選ばれなかった物をグループBに分類すると考えます.

$n$個から$k$個選ぶことはグループAに$k$個, グループBに$n-k$個分類すること.
$n$個から$n-k$個選ぶことはグループAに$n-k$個, グループBに$k$個分類すること.

ですのでグループのラベルを張り替えれば同じ結果になります.
従って当然総数は等しくなり,

\begin{align}
{}_{n}\mathrm{C}_k = {}_{n}\mathrm{C}_{n-k}
\end{align}

が成り立ちます.

別の表現

組合せのことを二項定数と呼ぶことがあります.
これは二項冪$(x+1)^n$を展開した際の$x^k$の係数が${}_{n}\mathrm{C}_k$で表されることに由来します.

また,大学以上では組合せを数式で$\displaystyle \binom{n}{k}$で表すことがあります.
縦ベクトルの表現と同じですので混同しないように気を付ける必要があります.

\begin{align}
{}_{n}\mathrm{C}_k = \binom{n}{k}
\end{align}

まとめ

相異なる$n$個の物から相異なる$k$個($k \le n$)を選ぶことを(重複のない)組合せといい,組合せの総数を${}_n\mathrm{C}_k$と表す.

\begin{align}
{}_{n}\mathrm{C}_k &= \frac{{}_{n}\mathrm{P}_k}{k!} = \frac{n!}{k!(n-k)!} = \binom{n}{k}
\end{align}

組合せの性質
\begin{align}
{}_{n}\mathrm{C}_k = {}_{n}\mathrm{C}_{n-k}
\end{align}

組合せのことを二項係数と呼ぶ場合もある.