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

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

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

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

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}.\)