この記事の所要時間: 約 3分53秒
二項係数と組み合わせ問題
二項係数に関するいろいろな公式があります.
これらは数式として証明できるだけでなく,組み合わせの数え上げ問題として解釈することができます.今回は,その例をいくつか紹介します.
二項係数:
\begin{align*}
{}_nC_k = \dfrac{n!}{k!(n-k)!}
\end{align*}
\begin{align*}
{}_nC_k = \dfrac{n!}{k!(n-k)!}
\end{align*}
- \(n\) 個のものから \(k\) 個を選ぶ選び方は \({}_nC_k\) 通り.
→ 1 個目の選び方が \(n\) 通り,2個目の選び方が \(n-1\) 通り,…,\(k\) 個目の選び方が \(n+1-k\) 通りと考えると
\begin{align*}
n\cdot(n-1)\cdot\cdots\cdot(n+1-k) = \frac{n!}{(n-k)!}.
\end{align*}
しかし,この数え方では取り出す順番によって同じ組み合わせを \(k!\) ずつ重複して数えているので,選び方は
\begin{align*}
\frac{n!}{(n-k)!}\times \frac{1}{k!} = \frac{n!}{k!(n-k)!}
\end{align*}
通りとなる. - (二項定理)
\((a+b)^n\) を展開したときの \(a^kb^{n-k}\) の係数は \({}_nC_k\).
→\((a+b)^n=(a+b)(a+b)\cdots (a+b)\) を,同類項をまとめずに展開したときに現れる項は,\(n\) 個のカッコのそれぞれから \(a\) または \(b\) を選んでかけ合わせたものとなる.
例えば,\((a+b)^3=(a+b)(a+b)(a+b)\) の場合,展開すると
\(aaa, aab, aba, abb, baa, bab, bba, bbb\)
の 8 項が現れる.
\(a^kb^{n-k}\) の係数は,この中で \(a\) が \(k\) 個,\(b\) が \(n-k\) 個含まれるものの個数となるが,\(n\) 個のカッコから\(k\) 個のカッコのを選んでそこからは \(a\) を,残りのカッコからは \(b\) を選ぶと考えることができるので,\({}_nC_k\) となる. - (二項係数の和)
\begin{align*}
\sum_{k=0}^n {}_nC_k = 2^n.
\end{align*}
→\({}_nC_0\) は \(n\) 個から \(0\) 個選ぶ (つまり,どれも選ばない)
\({}_nC_1\) は \(n\) 個から \(1\) 個選ぶ
︙
\({}_nC_k\) は \(n\) 個から \(k\) 個選ぶ
︙
\({}_nC_n\) は \(n\) 個から \(n\) 個すべてを選ぶこれらすべての場合の数を足し合わせると,\(n\) この中からいくつかを選ぶ(1つも選ばなくてもいいし,すべてを選んでもいい) 方法の数となります.
ところが,これは見方を変えると \(n\) 個のそれぞれについて選ぶか選ばないか,の 2 通りずつあるので,\(2^n\) 通りあります.
つまり,\(\sum_{k=0}^n {}_nC_k = 2^n\) となります.
- \begin{align*}{}_{n+1}C_{k+1} = {}_nC_k + {}_nC_{k+1}.\end{align*}
左辺は \(n+1\) 個から \(k+1\) 個を選ぶ選び方の個数です.
これを,場合分けして数えてみましょう.分かりやすいように,\(n+1\) 個に \(1, 2, \ldots, n+1\) と番号をつけておきます.
・まず,番号 \(n+1\) のものを選ぶとき
番号 \(n+1\) のものを選んで,全体では \(k+1\) 個選ぶためには,残り (\(1, 2, \ldots, n\)) の \(n\) 個の中から \(k\) 個選ぶ必要があります.
つまり,\({}_nC_k\) 通りです.・次に,番号 \(n+1\) のものを選ばないとき
同じように考えると,残り (\(1, 2, \ldots, n\)) の中から \(k+1\) 個を選ぶ必要があるので,\({}_nC_{k+1}\) 通りです.よって,\(n+1\) 個から \(k+1\) 個を選ぶ方法は,これらの和と一致するので,
\({}_{n+1}C_{k+1} = {}_nC_k + {}_nC_{k+1}.\)