二項定理

#組合せ論

Contents

二項定理とは

二項定理 (英：binomial theorem) とは、二項式の冪の展開を表す公式のこと。

$(x+y)^n = \sum_{k=0}^n \binom n k x^{n-k} y^k$

二項定理の導出：

次式を仮定し、数学的帰納法を用いる。

$(x+y)^n = \sum_{k=0}^n \binom n k x^{n-k} y^k$

$n=0$ のとき、

$\begin{aligned} (x+y)^0 &= 1 \cr &= \left.\sum_{k=0}^n \binom n k x^{n-k} y^k\right\vert_{n=0} \end{aligned}$

$n=1$ のとき、

$\begin{aligned} (x+y)^1 &= x + y \cr &= \left.\sum_{k=0}^n \binom n k x^{n-k} y^k\right\vert_{n=1} \end{aligned}$

$n+1$ のとき、

$\begin{aligned} (x+y)^{n+1} &= (x+y)\sum_{k=0}^n\binom n k x^{n-k}y^k \cr &= x\sum_{k=0}^n\binom n k x^{n-k}y^k + y\sum_{k=0}^n\binom n k x^{n-k}y^k \cr &= \sum_{k=0}^n\binom n k x^{(n+1)-k}y^k + \sum_{k=0}^n\binom n k x^{n-k}y^{k+1} \end{aligned} \tag{1}$

右辺の第一項より、

$\begin{aligned} \sum_{k=0}^n\binom n k x^{(n+1)-k}y^{k} &= \binom n 0 x^{n+1} + \binom n 1 x^{n}y + \cdots + \binom n n xy^{n} \cr &= \binom n 0 x^{n+1} + \sum_{k=1}^n\binom n k x^{(n+1)-k}y^{k} \end{aligned} \tag{2}$

右辺の第二項より、

$\begin{aligned} \sum_{k=0}^n\binom n k x^{n-k}y^{k+1} &= \binom n 0 x^n y +\cdots + \binom n {n-1} xy^n + \binom n n y^{n+1} \cr &= \sum_{k=1}^{n}\binom n {k-1} x^{(n+1)-k}y^k + \binom n n y^{n+1} \end{aligned} \tag{3}$

$(1),(2),(3)$ より、

$\begin{aligned} (x+y)^{n+1} &= \sum_{k=0}^n\binom n k x^{(n+1)-k}y^k + \sum_{k=0}^n\binom n k x^{n-k}y^{k+1} \cr &= \binom n 0 x^{n+1} + \sum_{k=1}^n\binom n k x^{(n+1)-k}y^{k} + \sum_{k=1}^{n}\binom n {k-1} x^{(n+1)-k}y^k + \binom n n y^{n+1} \cr &= \binom n 0 x^{n+1} + \sum_{k=1}^n\left\lbrack\binom n k +\binom n {k-1}\right\rbrack x^{(n+1)-k}y^{k} + \binom n n y^{n+1} \cr \end{aligned} \tag{4}$

ここで $(4)$ の二項係数の和を求めると、

$\begin{aligned} \binom n k + \binom n {k-1} &= \frac{n!}{k!(n-k)!} + \frac{n!}{(k-1)!(n-(k-1))!} \cr &= \frac{n!(n-k+1)}{k!(n-k+1)!} + \frac{n!k}{k!(n-k+1)!} \cr &= \frac{n!(n+1)}{k!(n-k+1)!} \cr &= \frac{(n+1)!}{k!((n+1)-k)!} \cr &= \binom {n+1} k \end{aligned} \tag{5}$

$(4),(5)$ より、

$\begin{aligned} (x+y)^{n+1} &= \binom n 0 x^{n+1} + \sum_{k=1}^n\left\lbrack\binom n k +\binom n {k-1}\right\rbrack x^{(n+1)-k}y^{k} + \binom n n y^{n+1} \cr &= \binom {n+1} 0 x^{(n+1)-0}y^0 + \sum_{k=1}^n\binom {n+1} k x^{(n+1)-k}y^{k} + \binom {n+1} {n+1} x^{(n+1)-(n+1)} y^{n+1} \cr &= \sum_{k=0}^{n+1} \binom {n+1} k x^{(n+1)-k}y^{k} \cr \cr \therefore (x+y)^n &= \sum_{k=0}^n \binom n k x^{n-k} y^k \end{aligned}$

二項係数

二項定理に現れる係数 $\displaystyle \binom n k$ を二項係数 (英：binomial coefficient) と呼ぶ。二項係数は組合せの総数と等しい。

$\binom n k = \operatorname{C}(n,k) = \frac{n!}{k!(n-k)!} \quad (n,k\in\N_{\ge 0},n\ge k)$

二項係数の諸定理

$\begin{aligned} \text{(B1)} &: \binom n k = \binom n {n-k} \cr \text{(B2)} &: \binom n k = \frac{n}{k}\binom {n-1} {k-1} \cr \text{(B3)} &: \binom n k = \binom {n-1} k + \binom {n-1} {k-1} \cr \text{(B4)} &: \binom n k \binom k l = \binom n l \binom {n-l} {k-l} \cr \end{aligned}$

$\bold{(B1)}$ の証明：

$\begin{aligned} \binom n {n-k} &= \frac{n!}{(n-k)!(n-(n-k))!} \cr &= \frac{n!}{k!(n-k)!} \cr &= \binom n k \cr \cr \therefore \binom n k &= \binom n {n-k} \end{aligned}$

$\bold{(B2)}$ の証明：

$\begin{aligned} \frac{n}{k}\binom {n-1} {k-1} &= \frac{n}{k}\cdot\frac{(n-1)!}{(k-1)!((n-1)-(k-1))!} \cr &= \frac{n}{k}\cdot\frac{(n-1)!}{(k-1)!(n-k)!} \cr &= \frac{n!}{k!(n-k)!} \cr &= \binom n k \cr \cr \therefore \binom n k &= \frac{n}{k}\binom {n-1} {k-1} \end{aligned}$

$\bold{(B3)}$ の証明： $\begin{aligned} \binom {n-1} k + \binom {n-1} {k-1} &= \frac{(n-1)!}{k!((n-1)-k)!} + \frac{(n-1)!}{(k-1)!((n-1)-(k-1))!} \cr &= \frac{(n-1)!}{k!(n-k-1)!} + \frac{(n-1)!}{(k-1)!(n-k)!} \cr &= \frac{(n-k)(n-1)!}{k!(n-k)!} + \frac{k(n-1)!}{k!(n-k)!} \cr &= \frac{n(n-1)!}{k!(n-k)!} \cr &= \frac{n!}{k!(n-k)!} \cr &= \binom n k \cr \cr \therefore \binom n k &= \binom {n-1} k + \binom {n-1} {k-1} \end{aligned}$

$\bold{(B4)}$ の証明：

$\begin{aligned} \binom n l \binom {n-l} {k-l} &= \frac{n!}{l!(n-l)!}\cdot\frac{(n-l)!}{(k-l)!((n-l)-(k-l))!} \cr &= \frac{n!}{l!(n-l)!}\cdot\frac{(n-l)!}{(k-l)!(n-k)!} \cr &= \frac{n!}{(n-k)!}\cdot\frac{1}{l!(k-l)!} \cr &= \frac{n!}{k!(n-k)!}\cdot\frac{k!}{l!(k-l)!} \cr &= \frac{n!}{k!(n-k)!}\cdot\frac{k!}{l!(k-l)!} \cr &= \binom n k \binom k l \cr \cr \therefore \binom n k \binom k l &= \binom n l \binom {n-l} {k-l} \end{aligned}$

二項係数の積和

$\binom{m+n}{\ell} = \sum_{j+k=\ell}\binom m j\binom n k$

二項係数の積和の公式の導出：

$\begin{aligned} (1+x)^m(1+x)^n &= \sum_{j=0}^m\binom{m}{j}x^j\sum_{k=0}^n\binom{n}{k}x^k \\ &= \sum_{j=0}^m\sum_{k=0}^n\binom m j\binom{n}{k} x^{j+k} \\ &= \sum_{\ell=0}^{m+n}\left[x^\ell\sum_{j+k=\ell}\binom m j\binom n k\right] \\ \\ (1+x)^{m+n} &= \sum_{\ell=0}^{m+n}\binom{m+n}{\ell}x^\ell \\ \\ (1+x)^{m+n} &= (1+x)^{m}(1+x)^{n} \\ \sum_{\ell=0}^{m+n}\binom{m+n}{\ell}x^\ell &= \sum_{\ell=0}^{m+n}\left[x^\ell\sum_{j+k=\ell}\binom m j\binom n k\right]\\ \\ \therefore \binom{m+n}{\ell} &= \sum_{j+k=\ell}\binom m j\binom n k \end{aligned}$

負の二項係数

負の二項係数 (英：negative binomial coefficient) とは、二項係数の第一引数を負の整数まで拡張したもの。

$\binom{-n}{k} = (-1)^k\binom{n+k-1}{k} \quad (n,k\in\N_{\ge 0})$

負の二項係数の導出：

$\begin{aligned} \binom n k &= \frac{n!}{k!(n-k)!} \cr &= \frac{\overbrace{n(n-1)(n-2)\cdots(n-k+1)}^{k\text{ times}}}{k!} \cr \cr \binom{-n}{k} &= \frac{-n(-n-1)(-n-2)\cdots(-n-k+1)}{k!} \cr &= \frac{(-1)^k\cdot\overbrace{n(n+1)(n+2)\cdots(n+k-1)}^{k\text{ times}}}{k!} \cr &= (-1)^k\frac{(n+k-1)!}{k!((n+k-1)-k)!} \cr &= (-1)^k\binom{n+k-1}{k} \cr \cr \therefore \binom{-n}{k} &= (-1)^k\binom{n+k-1}{k} \end{aligned}$

参考文献

基礎から学ぶトラヒック理論

posted with amazlet at 19.09.29

稲井寛
森北出版
売り上げランキング: 43,700

Amazon.co.jpで詳細を見る