組み合わせCの計算結果が整数になる理由

※ この記事はnoteをやっていた頃に投稿した記事です。こちらのブログに移しました。
（note投稿時期：2023年3月14日）

事前知識
組み合わせCについて
パスカルの三角形
Cが整数になる理由

事前知識

組み合わせCについて

$_{n} C_{k} = \frac{_{n} P_{r}}{k!} = \frac{n \times (n - 1) \times \dots \times (n - (k - 1))}{k \times (k - 1) \times \dots \times 1}$

だった。

この

$\frac{n \times (n - 1) \times \dots \times (n - (k - 1))}{k \times (k - 1) \times \dots \times 1}$

を少し変形すると、

$\begin{aligned} \frac{n \times (n - 1) \times \dots \times (n - (k - 1)) \times (n - k) \times \dots \times 1}{(k \times (k - 1) \times \dots \times 1) \times ((n - k) \times \dots \times 1)} = & \frac{n!}{k! (n - k)!} \end{aligned}$

となる。つまり、

$_{n} C_{k} = \frac{n!}{k! (n - k)!} =_{n} C_{n - k}$

また、 $k = 0$ のとき、

$_{n} C_{0} = 1$

である。

※ $0! = 1$ についての話はしていないので、今回はあまり触れないが、 $_{n} C_{0} = 1$ はこのようにした方が都合がいいからである。

$_{n} C_{n} = \frac{n \times (n - 1) \times \dots \times 1}{n \times (n - 1) \times \dots \times 1} = 1$

なので、

$_{n} C_{k} =_{n} C_{n - k}$

を $k = 0$ まで拡張すると、

$_{n} C_{0} =_{n} C_{n} = 1$

となる。

パスカルの三角形

パスカルの三角形とは以下のようなものである。

図2のように、各段の両端は1であり、それ以外は隣り合い通しの数の和が下の段の数になる。

そして、これらの数字は「C」を用いて以下のように書き換えることができる。

例えば、図2と図3の上から6, 左から4つ目の数(図2の青色の所)に注目すると、

$_{5} C_{3} = \frac{5 \times 4 \times 3}{3 \times 2 \times 1} = 10$

で図2と図3が一致していることがわかる。

なぜ一致しているのか？

まず、各段の両端に着目してみると、

$_{n} C_{0} =_{n} C_{n} = 1$

となり、図2と図3が一致している事がわかる。

なので、あとは $k = 1, \dots, n - 1$ に対して、

$_{n} C_{k} =_{n - 1} C_{k - 1} +_{n - 1} C_{k}$

となっている事を確かめることができればいい。

$_{n} C_{k} = \frac{n!}{k! (n - k)!}$

だったので、

$_{n - 1} C_{k - 1} = \frac{(n - 1)!}{(n - k)! (k - 1)!},_{n - 1} C_{k} = \frac{(n - 1)!}{(n - k - 1)! k!}$

となる。よって、

$\begin{aligned} _{n - 1} C_{k - 1} +_{n - 1} C_{k} & = \frac{(n - 1)!}{(n - k)! (k - 1)!} + \frac{(n - 1)!}{(n - k - 1)! k!} \\ = \frac{(n - 1)! (n - k - 1)! k! + (n - 1)! (n - k)! (k - 1)!}{(n - k)! (k - 1)! (n - k - 1)! k!} \\ = \frac{(n - 1)! (n - k - 1)! k (k - 1)! + (n - 1)! (n - k) (n - k - 1)! (k - 1)!}{(n - k)! (k - 1)! (n - k - 1)! k!} \\ = \frac{(n - 1)! (n - k - 1)! (k - 1)! (k + (n - k))}{(n - k)! (k - 1)! (n - k - 1)! k!} \\ = \frac{n!}{(n - k)! k!} \\ =_{n} C_{k} \end{aligned}$