二項係数

$\newcommand{\floor}[1]{\left\lfloor#1\right\rfloor}$ $\newcommand{\mathmod}[1]{\ \left(\mathrm{mod}\ #1\right)}$

定義

非負整数 $k\leq n$ について、$_nC_k$ あるいは $\binom{n}{k}$ とは、$\frac{n!}{k!(n-k)!}$ として表すことのできる数のことをいう。ここで、非負整数 $n$ について、$n!$ とは $n$ の階乗のことをいう。なお、$k$ が $n$ より大きい整数あるいは負の整数のとき $_nC_k=0$ と定める。

このとき、$_nC_k$ は整数値を取ることが知られている。

基本的な性質

• $1$ 以上の整数 $n$ と $1$ 以上の整数 $k\leq n$ について、$_nC_k={}_{n-1}C_k+{}_{n-1}C_{k-1}$ が成り立つ。

Proof.

$k=n$ のとき、$_nC_k={}_{n-1}C_{k-1}=1, {}_{n-1}C_k=0$ より正しい。$n\geq 1, 1\leq k\leq n-1$ のとき $$\begin{split} _nC_k - _{n-1}C_k= & \frac{n(n-1)\cdots (n-k+1)}{k!}-\frac{(n-1)\cdots (n-k+1)(n-k)}{k!} \\ = & \frac{n(n-1)\cdots (n-k+1)-(n-1)\cdots (n-k+1)(n-k)}{k!} \\ = & \frac{k(n-1)\cdots (n-k+1)}{k!} \\ = & \frac{(n-1)\cdots (n-k+1)}{(k-1)!} \\ = & _{n-1}C_{k-1} \end{split}$$ より正しいことがわかる。

□

• （二項定理）$1$ 以上の整数 $n$ について

$$(x+y)^n=\sum_{k=0}^n {}_nC_k x^k y^{n-k}$$ が成り立つ。とくに $1$ 以上の整数 $n$ と任意の整数 $k$ について $_nC_k$ は $(X+1)^n$ の $X^k$ の係数に等しい（これは $k<0$ あるいは $k>n$ のときも、$_nC_k=0$ と定めていることから成立する）。

Proof.

$$(x+y)^n=\sum_{k=0}^n a_{n, k} x^k y^{n-k}$$ と展開すると、 $$\begin{split} (x+y)^{m+1}= & (x+y)^m(x+y) \\ = & (x+y)\sum_{k=0}^n a_{m, k} x^k y^{m-k} \\ = & \sum_{k=0}^n a_{m, k} x^{k+1} y^{m-k}+\sum_{k=0}^n a_{m, k} x^k y^{m+1-k} \\ = & \sum_{k=1}^{n+1} a_{m, k-1} x^k y^{m+1-k}+\sum_{k=0}^n a_{m, k} x^k y^{m+1-k} \end{split}$$ となるから、$a_{m+1, 0}=a_{m, 0}$, $a_{m+1, m+1}=a_{m, m}$ かつ $1\leq k\leq m$ のとき $$a_{m+1, k}=a_{m, k-1}+a_{m, k}$$ となる。

さて、$n=1$ のとき $$a_{1, 0}=a_{1, 1}=1={}_1C_0={}_1C_1$$ より二項定理が成り立つ。$n=m$ のとき $k=0, 1, \ldots, m$ について $a_{m, k}={}_mC_k$ となるとすると $a_{m+1, 0}=a_{m, 0}=1={}_{m+1}C_0$, $a_{m+1, m+1}=a_{m, m}=1={}_{m+1}C_{m+1}$ かつ $1\leq k\leq m$ のとき $$a_{m+1, k}={}_mC_{k-1}+{}_mC_k={}_{m+1}C_k$$ となるから、$n=m+1$ についても二項定理は正しいことがわかる。

□

• 非負整数 $n$ について、$\sum_{0\leq i \leq n} {}_nC_i=2^n$ が成り立つ。

Proof.

二項定理より $$\sum_{0\leq i \leq n} {}_nC_i=(1+1)^n=2^n.$$

□

• $_nC_r$ は、$n$ 個の要素からなる集合 $S$ の部分集合 $T$ で、$r$ 個の要素からなるものの個数に等しい。

Proof.

$n$ 個の要素からなる集合 $S$ の部分集合 $T$ で、$r$ 個の要素からなるものの個数を $b_{n, r}$ とおく。 また、$S=\{1, 2, \ldots, n\}$ とおいても一般性を失わないので、$S=\{1, 2, \ldots, n\}$ について帰納法で示す。

$n=1$ のとき、$T=\emptyset$ または $T=\{1\}$ だから、$b_{1, 0}=b_{1, 1}=1={}_1C_0={}_1C_1$ なので、定理は正しい。

定理が $n$ のかわりに $n-1$ について正しいと仮定する。 $S$ の部分集合 $T$ で、$r$ 個の要素からなるものをとる。$n\not\in T$ のとき、$T$ は、 $\{1, 2, \ldots, n-1\}$ の部分集合であり、かつ $r$ 個の要素からなる。 $n\in T$ のとき、$T\setminus\{n\}$ は、 $\{1, 2, \ldots, n-1\}$ の部分集合であり、かつ $r-1$ 個の要素からなる。 よって $$b_{n, r}=b_{n-1, r}+b_{n-1, r-1}={}_{n-1}C_{r-1}+{}_{n-1}C_r={}_nC_r$$ となるから、$n$ について定理が正しいことがわかる。

□

• 非負整数 $k\leq n$ について、$_nC_k$ は整数である。

Proof.

次節を参照。

□

二項係数が整数値をとることの証明

数論的方法

非負整数 $k \leq n$ について、$_nC_k$ が整数であるためには、$k!(n-k)!$ が $n!$ の約数であればよい。

準備

整数 $x$ と 素数 $p$ について、$p^i$ が $x$ の約数となる最大の整数 $i$ を $\mathrm{ord}_p(x)$ と表記する。

実数 $r$ について、$n<r$ が成り立つ最大の整数 $n$ を $\floor{r}$ と表記する。

証明

一般の非負整数 $m$ について $\mathrm{ord}_p(m!)$ を計算する。

$1$ 以上 $m$ 以下の整数であって $p^i$ の倍数であるようなものの個数は $\floor{\frac{m}{p^i}}$ 個である。よって、$\mathrm{ord}_p(m!)$ は $$\sum_{i=1}^\infty \floor{\frac{m}{p^i}}$$ と求まる。ただし、この無限和について、実際には有限個の項を除いては $0$ と等しいため、実質的に有限和を表しているものと考える。

$\mathrm{ord}_p(k!(n-k)!)=\mathrm{ord}_p(k!)+\mathrm{ord}_p((n-k)!)$ であるため、この値は $$\sum_{i=1}^\infty \floor{\frac{k}{p^i}}+\floor{\frac{n-k}{p^i}}$$ と等しい。

実数 $r$ と $s$ について $\floor{r}+\floor{s}\leq \floor{r+s}$ が成り立つため、$\floor{\frac{k}{p^i}}+\floor{\frac{n-k}{p^i}}\leq \floor{\frac{n}{p^i}}$ が成り立つ。従って $$\sum_{i=1}^\infty \floor{\frac{k}{p^i}}+\floor{\frac{n-k}{p^i}}\leq \sum_{i=1}^\infty \floor{\frac{n}{p^i}}$$ が示される。ここで左辺は $\mathrm{ord}_p(k!(n-k)!)$ に等しく、右辺は $\mathrm{ord}_p(n!)$ に等しい。

任意の素数 $p$ について $\mathrm{ord}_p(k!(n-k)!)\leq \mathrm{ord}_p(n!)$ が成り立つため、$k!(n-k)!$ は $n!$ の約数である。従って $_nC_k$ は整数である。

この証明から、素数 $p$ が $_nC_k$ を割り切る指数は $$\mathrm{ord}_p (_nC_k)=\sum_{e=1}^{\infty} \left(\floor{\frac{n}{p^e}}-\floor{\frac{k}{p^e}}-\floor{\frac{n-k}{p^e}}\right)$$ によって与えられることがわかる。

群論的方法

$n$ 次対称群 $S_n$ の部分群として $S_k\times S_{n-k}$ と同型な群を取れる。Lagrangeの定理より、$k!(n-k)!$ は $n!$ の約数である。

帰納的な方法

$n$ についての帰納法を回す。

• $n=0$ の場合については明らか。
• $n \leq i$ の場合に $k \leq n$ について $_nC_k$ が整数となることが示されたとする。このとき、$n=i+1$ の場合について、$_nC_k=_{n-1}C_k+_{n-1}C_{k-1}$ より、$1\leq k \leq n$ については $_nC_k$ が整数であることが成り立つ。$k=0$ の場合については明らか。

その他の性質

• 素数 $p$ に対して、$n$ が偶数ならば $_{p-1}C_{n}$ を $p$ で割った余りは $1$ である。また $n$ が奇数ならばこの値は $-1$ となる。

Proof.

$$_{p-1}C_{n}=\frac{(p-1)(p-2)\cdots (p-n)}{n!}$$ だが、 $$(p-1)(p-2)\cdots (p-n)\equiv (-1)(-2)\cdots (-n)=(-1)^n n!\mathmod{p}$$ であるから $$_{p-1}C_{n}\equiv (-1)^n\mathmod{p}$$ となる。

□

• $1$ 以上の整数 $n$ について、$\sum_{0\leq 2i \leq n} {}_nC_{2i}=2^{n-1}$ が成り立つ。

Proof.

二項定理より $$\sum_{0\leq k \leq n} (-1)^k {}_nC_k=(1-1)^n=0$$ だが、$(1+(-1)^k)/2$ は $k$ が偶数のとき $1$、奇数のとき $0$ となるので $$\sum_{0\leq 2i \leq n} {}_nC_{2i}=\sum_{0\leq k \leq n} \frac{1+(-1)^k}{2} {}_nC_k=\frac{2^n+0}{2}=2^{n-1}.$$

□

• $1$ 以上の整数 $n$ について

$$\sum_{k=0}^n k{}_nC_k=n\times 2^{n-1}.$$

Proof.

二項定理より直ちに得られる $$(X+1)^n=\sum_{k=0}^n {}_nC_k X^k$$ の両辺を $X$ で微分し、 $$n(X+1)^{n-1}=\sum_{k=1}^n k{}_nC_k X^{k-1}$$ となる。$X=1$ を代入し、 $$n\times 2^{n-1}=\sum_{k=1}^n k{}_nC_k$$ を得る。$k=0$ のとき $k{}_nC_k=0$ だから、和をとる範囲を $k=0$ から始めても、この等式は成り立つ。

□

• （Vandermondeの等式）

$$_{n_1+n_2+\cdots +n_p}C_m=\sum_{k_1+k_2+\cdots +k_p=m}{}_{n_1}C_{k_1}\times{}_{n_2}C_{k_2}\times\cdots\times{}_{n_p}C_{k_p}.$$

Proof.

$$(X+1)^{n_1+n_2+\cdots n_p}=(X+1)^{n_1}(X+1)^{n_2}\cdots (X+1)^{n_p}$$ に着目すると、この等式の左辺と右辺の $X^m$ の係数は、それぞれ上記の等式の左辺と右辺に等しい。

□

• とくに、$p=2$ のとき

$$_{x+y}C_m=\sum_{r=0}^m {}_xC_r\times{}_yC_{m-r}$$ が成立し、$x=y=m$ のとき $$_{2m}C_m=\sum_{r=0}^m ({}_mC_r)^2$$ が成立する。

• $n$ が $1$ 以上の整数で、$m$ が $0\leq m\leq n$ となる整数のとき

$$\sum_{k=0}^m (-1)^k{}_nC_k=(-1)^m{}_{n-1}C_m.$$

Proof.

各 $n$ について、$m$ に関する帰納法で証明する。 $m=0$ のとき、両辺ともに $1$、$m=1$ のとき $$_nC_0-{}_nC_1=1-n=-{}_{n-1}C_1$$ であるから、上記の等式は成立する。 $2\leq m\leq n$ で、上記の等式が $m-1$ について成立すると仮定すると、 $$\begin{split} \sum_{k=0}^m (-1)^k{}_nC_k= & (-1)^{m-1}{}_{n-1}C_{m-1}+(-1)^m{}_nC_m \\ = & (-1)^m({}_nC_m-{}_{n-1}C_{m-1}) \\ = & (-1)^m _{n-1}C_m \end{split}$$ となって、$m$ について上記の等式が成立する。

□