二項係数
概要
非負整数 $k\leq n$ について、二項係数 (binomial coefficient) $_nC_k$ あるいは $\binom{n}{k}$ とは、$\frac{n!}{k!(n-k)!}$ として表すことのできる数のことをいう。ここで、非負整数 $n$ について、$n!$ とは $n$ の階乗のことをいう。なお、$k$ が $n$ より大きい整数あるいは負の整数のとき $\binom{n}{k}=0$ と定める。
$0\leq k\leq n$ となる整数 $n, k$ について以下の定義はいずれも同値である。なお、$k$ が $n$ より大きい整数あるいは負の整数のとき $\binom{n}{k}=0$ と定める。
$0\leq k\leq n$ となる整数 $n, k$ について
$$\binom{n}{k}=\frac{n!}{k!(n-k)!}$$ と定める。
非負整数 $n$ について
$$\binom{n}{0}=\binom{n}{n}=1$$ と定め、$n\geq k\geq 1$ となる整数 $n, k$ について
$$\binom{n+1}{k}=\binom{n}{k}+\binom{n}{k-1}$$ と定める。
$n\geq k\geq 0$ となる整数 $n, k$ について
$$\binom{n}{k}=\# \{U \mid U\subset \{1, 2, \ldots, n\}, \#U=k\}$$ と定める。
基本的性質
定義3から、
$$ \sum_{k=0}^n \binom{n}{k}=2^n$$ となることがすぐにわかる。このほか、次のような関係式が成り立つ。
$n$ が正の整数のとき、$$\sum_{0\leq 2i \leq n} \binom{n}{2i}=2^{n-1},$$および$$\sum_{k=0}^n k{}_nC_k=n\times 2^{n-1}.$$
（Vandermondeの等式） $n_1, n_2, \ldots, n_p\geq 0$ および $0\leq m\leq n_1+n_2+\cdots +n_p$ となる整数 $n_1, n_2, \ldots, n_p, m$ について
$$\binom{n_1+n_2+\cdots +n_p}{m}=\sum_{k_1+k_2+\cdots +k_p=m}\binom{n_1}{k_1}\times\binom{n_2}{k_2}\times\cdots\times\binom{n_p}{k_p}.$$とくに、$p=2$ のとき
$$\binom{x+y}{m}=\sum_{r=0}^m \binom{x}{r}\times\binom{y}{m-r}$$ が成立し、$x=y=m$ のとき
$$\binom{2m}{m}=\sum_{r=0}^m \binom{m}{r}^2$$ が成立する。$n$ が $1$ 以上の整数で、$m$ が $0\leq m\leq n$ となる整数のとき
$$\sum_{k=0}^m (-1)^k\binom{n}{k}=(-1)^m\binom{n-1}{m}.$$
素数との関連では、次のような性質も成り立つ。
- 素数 $p$ に対して、$0< n< p$ ならば $\binom{p}{n}$ は $p$ の倍数である。
- 素数 $p$ に対して、$n$ が偶数ならば $\binom{p-1}{n}$ を $p$ で割った余りは $1$ である。また $n$ が奇数ならばこの値は $-1$ となる。
- 素数 $p$ について、$v_p(n)$ を、$p$ が $n$ を割り切る指数とすると、$0\leq k\leq n$ となる整数 $n, k$ について
$$v_p\left(\binom{n}{k}\right)=\sum_{e=1}^\infty \left( \floor{\frac{n}{p^e}}-\floor{\frac{k}{p^e}}-\floor{\frac{n-k}{p^e}}\right)$$
となる（なお、右辺の床関数の値は $p^e>n$ のとき $0$ となるので、右辺の和は実際には有限和となる）。
3つめの性質は、素数の分布に関する初等的な議論で重要である。この性質を用いてBertrand–Chebyshevの定理を証明することができる。
