二項係数と組み合わせ問題

この記事の所要時間: 353

二項係数と組み合わせ問題

二項係数に関するいろいろな公式があります.

これらは数式として証明できるだけでなく,組み合わせの数え上げ問題として解釈することができます.今回は,その例をいくつか紹介します.

二項係数
\begin{align*}
{}_nC_k = \dfrac{n!}{k!(n-k)!}
\end{align*}
  1. \(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*}
    通りとなる.
  2. (二項定理)
    \((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\) となる.
  3. (二項係数の和)
    \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\) となります.
  4. \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}.\)
スポンサーリンク
sub2
sub2
  • このエントリーをはてなブックマークに追加