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

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

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

二項係数：
\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}.$

数学の力

京大生が数学の定理・公式の証明や入試問題の解説をするブログ.

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

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