『組み合わせ』に関する基本的な公式と証明のまとめ
集合 $S$ を $n$ 個の異なる要素からなる有限集合とする。
$S$ の部分集合で、要素数が $k$ であるものの個数を $\binom{n}{k}$ と書き、
$$
\binom{n}{k} := \#\{ A \subseteq S \mid \#A = k \}
$$
と定義する。このとき、$\binom{n}{k}$ は次のように与えられる。
$$
\binom{n}{k} = \frac{n!}{k!(n - k)!}
$$
$n,k$を自然数とし、$1 \leq k \leq n$とする。
まず、順序を区別して $n$ 個のものから $k$ 個を選び出し、並べる方法の総数は
$$
P(n,k)=\frac{n!}{(n-k)!}
$$
であった(
順列の定義はコチラ
)。
これは、「第$1$段階で $n$ 通り、第$2$段階で $n-1$ 通り、…、第 $k$ 段階で $n-k+1$ 通り」を掛け合わせたものである。
$ $
「組合せ」は選んだ $k$ 個の順序を区別しない選び方である。
一方、順列 $P(n,k)$ は同じ $k$ 個を取り出しても、異なる並べ方をすべて別のものとして数えている。
$ $
すなわち、順序を区別しない組合せを求める上で、順列全体を「同じ $k$ 個の集合を持つもの同士」でまとめると、
$1$つの集合（組合せ）あたり必ず $k!$ 個の順列が対応する。
例えば、
$$
S = \{A, B, C, D\}
$$
という集合に対して、順列（順序あり）を求めると、$P(4,2) = 12$ 通りである。実際に書き並べると、
$$
\begin{aligned}
\text{AB} &\rightarrow \{A, B\} \\
\text{BA} &\rightarrow \{A, B\} \\
\text{AC} &\rightarrow \{A, C\} \\
\text{CA} &\rightarrow \{A, C\} \\
\text{AD} &\rightarrow \{A, D\} \\
\text{DA} &\rightarrow \{A, D\} \\
\text{BC} &\rightarrow \{B, C\} \\
\text{CB} &\rightarrow \{B, C\} \\
\text{BD} &\rightarrow \{B, D\} \\
\text{DB} &\rightarrow \{B, D\} \\
\text{CD} &\rightarrow \{C, D\} \\
\text{DC} &\rightarrow \{C, D\}
\end{aligned}
$$
組合せ（順序なし）にまとめると、
$$
\begin{aligned}
\{A, B\} &\leftarrow \text{AB, BA} \quad（2\text{通り}）\\
\{A, C\} &\leftarrow \text{AC, CA} \quad（2\text{通り}）\\
\{A, D\} &\leftarrow \text{AD, DA} \quad（2\text{通り}）\\
\{B, C\} &\leftarrow \text{BC, CB} \quad（2\text{通り}）\\
\{B, D\} &\leftarrow \text{BD, DB} \quad（2\text{通り}）\\
\{C, D\} &\leftarrow \text{CD, DC} \quad（2\text{通り}）
\end{aligned}
$$
このように、同じ集合（組合せ）からできる順列は常に $k! = 2$ 通りある。よって、
$$
\begin{aligned}
\binom{4}{2}
= \frac{P(4,2)}{2!}
= \frac{12}{2}
= 6
\end{aligned}
$$
以上より、組み合わせの総数を求めるには、
$$
\bigl|\text{組合せの数}\bigr|
\;=\;
\frac{\bigl|\text{順列の数}\bigr|}{k!}
\;=\;
\frac{P(n,k)}{k!}
\,.
$$
を計算すればよい。以上より、
$$
{}_{n}C_{k}
=\frac{P(n,k)}{k!}
=\frac{\displaystyle\frac{n!}{(n-k)!}}{k!}
=\frac{n!}{k!\,(n-k)!}
$$
を得る。
$$ \Box$$
より形式的には、次のように示す事ができる。
$ $
$X$ を「$S$ の要素を重複なく並べた長さ $k$ の列（順列）」全体の集合とする。すなわち、
$$
|X| = P(n,k)
$$
$Y$ を「$S$ の $k$ 要素部分集合全体の集合」とする。すなわち、
$$
|Y| = \binom{n}{k}
$$
$ $
ここで、写像
$$
f : X \to Y, \quad f(a_1,\dots,a_k) = \{a_1,\dots,a_k\}
$$
を考える($\{a_1,\dots,a_k\}$は順番が考慮されない)。
固定した $A \in Y$ に対し、$f^{-1}(A)$ の元は「$A$ の要素を並べた順列」なので、ちょうど $k!$ 個。
よって
$$
|X| = \sum_{A \in Y} |f^{-1}(A)| = \sum_{A \in Y} k! = k! \cdot |Y|
$$
すなわち
$$
P(n,k) = k! \binom{n}{k}
$$
これを解いて
$$
\binom{n}{k} = \frac{P(n,k)}{k!} = \frac{n!}{k!(n-k)!}
$$
を得る。
$$ \Box$$
順序を考慮しないで、$n$個のものから$k$個を選び出す方法の総数を組み合わせという。
組み合わせの総数を計算する場合、$n$個のものから$k$個を選び取る組み合わせの総数は、次のように表される。
$$
\begin{align*}
\displaystyle _{n}\mathrm{C}_{k} := \binom{n}{k} := \frac{n!}{k!(n-k)!}
\end{align*}
$$
ここで、$ n $ は全体の要素の数、$ k $ は選び取る要素の数、$ n! $ は $ n $ の階乗を表し、
$$
\begin{aligned}
n! = n \times (n-1) \times (n-2) \times \dots \times 1
\end{aligned}
$$
で定義される。ただし、$0!= 1$ と定める。
順列と組み合わせの違いは、順序を考慮するかどうかである。
$ $
■ 順序を考慮する場合。
例: 「$A$、$B$、$C$」のうち $2$ つを選び、順序を考えて並べる場合。
・ $A$, $B$ と $B$, $A$ は 異なる順列とみなされる。
・ 順列の数式は次のように表す。
$$
\begin{aligned}
P(n, k) = \frac{n!}{(n-k)!}
\end{aligned}
$$
・ 具体例: $6$個の物から$2$個を選び順番に並べる場合、
$$
\begin{aligned}
P(6, 2) = \frac{6!}{(6-2)!} = 30
\end{aligned}
$$
である。
$ $
■ 順序を考慮しない場合。
例: 「$A$、$B$、$C$」のうち $2$ つを選ぶ場合。
・ $A$, $B$ と $B$, $A$ は 同じ組み合わせとみなされる。
・ 組み合わせの数式は次のように表す。
$$
\begin{aligned}
{}_{n}\mathrm{C}_k = \frac{n!}{k!(n-k)!}
\end{aligned}
$$
・ 具体例: $6$個の物から$2$個を選ぶ場合、
$$
\begin{aligned}
{}_6\mathrm{C}_2 = \frac{6!}{2!(6-2)!} = 15
\end{aligned}
$$
である。
任意の自然数 $ n \in \mathbb{N} $ に対して、
$$
\binom{n}{0} = \binom{n}{n} = 1
$$
が成り立つ。
$n \in \mathbb{N}$とする。まず$\binom{n}{0}$を、定義に従って計算すると、
$$
\begin{aligned}
\binom{n}{0}
&= \frac{n!}{0!(n-0)!}
\\
&= \frac{n!}{0! \cdot n!}
\quad \because n - 0 = n
\\
&= \frac{n!}{1 \times n!}
\quad \because 0! = 1
\\
&= 1
\end{aligned}
$$
となる。以上の変形により$\binom{n}{0} = 1$が示された。
次に$\binom{n}{n}$を、同様の手順で計算すると、
$$
\begin{aligned}
\binom{n}{n}
&= \frac{n!}{n!(n-n)!}
\\
&= \frac{n!}{n! \cdot 0!}
\quad \because n - n = 0
\\
&= \frac{n!}{n! \times 1}
\quad \because 0! = 1
\\
&= 1
\end{aligned}
$$
となる。以上の変形により$\binom{n}{n} = 1$が示された。
以上により、任意の$n \in \mathbb{N}$に対して$\binom{n}{0} = \binom{n}{n} = 1$であることが示された。
$$ \Box$$
自然数$n$が$2$以上のとき
$$
\binom{n}{2}=\dfrac{n(n-1)}{2}
$$
である。
二項係数の定義を用いると、
$$
\binom{n}{2}:=\dfrac{n!}{2!(n-2)!}
$$
ここで階乗の定義より$n!=n(n-1)(n-2)!$および$2!=2$を代入すると
$$
\binom{n}{2}=\dfrac{n(n-1)(n-2)!}{2(n-2)!}=\dfrac{n(n-1)}{2}
$$
が得られる。
自然数$n$と$k$について$1\le k\le n$とする。恒等式
$$
k\binom{n}{k}=n\binom{n-1}{k-1}
$$
が成り立つ。
左辺を定義で展開する。
$$
k\binom{n}{k}=k\dfrac{n!}{k!(n-k)!}=\dfrac{n!}{(k-1)!(n-k)!} \quad\ \because\ \frac{k}{k!}=\frac{k}{k(k-1)!}=\frac{1}{(k-1)!}
$$
一方
$$
\begin{align}
n\binom{n-1}{k-1}
&= n \cdot \frac{(n-1)!}{(k-1)! \bigl((n-1)-(k-1)\bigr)!} \\[4pt]
&= n \cdot \frac{(n-1)!}{(k-1)!(n-k)!} \\[4pt]
&= \frac{n!}{(k-1)!(n-k)!} \quad \because\ n! = n(n-1)!
\end{align}
$$
両辺が一致するので恒等式は成り立つ。
任意の自然数$ n $に対して、$$ \binom{n}{1} = \binom{n}{n-1} = n $$が成り立つ。
$n \in \mathbb{N}$とする。二項係数の定義を用いて直接的に示す。二項係数は
$$
\binom{n}{k} = \frac{n!}{k!(n-k)!}
$$
で、$n!$は$n$が非負整数の場合に定義され、$n! = n \times (n-1) \times \cdots \times 1$ とし、$0! = 1$とする。
$ $
まず$\binom{n}{1}$を計算すると
$$
\begin{aligned}
\binom{n}{1}
&= \frac{n!}{1!(n-1)!} \\
&= \frac{n \times (n-1)!}{(n-1)!} \quad \because\,n!=n\times(n-1)!,\;1!=1 \\
&= n \cdots①
\end{aligned}
$$
一方で$\binom{n}{n-1}$を同様に計算する。すると、
(二項係数の対称性$\binom{n}{k} = \binom{n}{n-k}$からも$\binom{n}{n-1} = \binom{n}{1}$と結論できるが、以下では直接計算を行う。)
$$
\begin{aligned}
\binom{n}{n-1}
&= \frac{n!}{(n-1)!(n-(n-1))!}\\
&= \frac{n!}{(n-1)!\times 1!} \quad \because\,1!=1 \\
&= \frac{n \times (n-1)!}{(n-1)!\times 1} \quad \because\,n!=n\times(n-1)! \\
&= n\cdots②
\end{aligned}
$$
以上の式$①$と$②$により、$\binom{n}{1}$と$\binom{n}{n-1}$は共に$n$となる。すなわち
$$
\binom{n}{1} = \binom{n}{n-1} = n
$$
が得られる。
$$ \Box$$
二項係数$_{n}\mathrm{C}_{k}$について、次が成り立つ。
ただし、$n \geq 2, k \geq 1$とする。
$$
\begin{align*}
1)\quad &k\cdot_{n}\mathrm{C}_{k} = n\cdot _{n-1}\mathrm{C}_{k-1} \\
2)\quad &_{n-1}\mathrm{C}_{k} + _{n-1}\mathrm{C}_{k-1} = _{n}\mathrm{C}_{k}
\end{align*}
$$
- $1\leq k \leq n$とする。直接計算すれば、二項係数の定義より
$$ \begin{align*} \displaystyle k_{n}\mathrm{C}_{k} &= k \cdot \frac{n!}{k!(n-k)!} \\ \displaystyle &=\frac{n \cdot (n-1)!}{(k-1)!(n-k)!} \because n!=n \times (n-1)!\\ \displaystyle &= n \cdot \frac{(n-1)!}{(k-1)!((n-1)-(k-1))!} \because (n-k)!=\{(n-1)-(k-1)\}! \\ \displaystyle &= n _{n-1}\mathrm{C}_{k-1} \because 二項係数の定義\\ \end{align*} $$$\Box$$$ $$ - $1\leq k \leq n-1$とする。直接計算すれば、二項係数の定義より
$$ \begin{align*} \displaystyle _{n-1}\mathrm{C}_{k} + _{n-1}\mathrm{C}_{k-1} &= \frac{(n-1)!}{k!(n-1-k)!} + \frac{(n-1)!}{(k-1)!(n-k)!} \end{align*} $$
ここで$(\{n-k\}-1)! = \dfrac{(n-k)!}{n-k}$ なので、第$1$項には $(n-k)$ を掛け、
また第$2$項には $k$ を掛けて、分母をそろえると、
$$ \begin{align*} \displaystyle \frac{(n-1)!}{k!(n-1-k)!} + \frac{(n-1)!}{(k-1)!(n-k)!} &= \frac{(n-1)!}{k!(n-1-k)!} + \frac{(n-1)!}{(k-1)! \cdot (n-k)!} \\[6pt] &= \frac{(n-1)!}{k!(n-1-k)!} + \frac{k \cdot (n-1)!}{k! \cdot (n-k)!} \qquad \because k! = k \cdot (k-1)! \\[6pt] &= \frac{(n-1)! \cdot (n-k)}{k! \cdot (n-k)!} + \frac{k \cdot (n-1)!}{k! \cdot (n-k)!} \qquad \because (n-1-k)! = \frac{(n-k)!}{n-k} \\[6pt] &= \frac{(n-k) \cdot (n-1)! + k \cdot (n-1)!}{k! \cdot (n-k)!} \\[6pt] &= \frac{[(n-k) + k] \cdot (n-1)!}{k! \cdot (n-k)!} \\[6pt] &= \frac{n \cdot (n-1)!}{k! \cdot (n-k)!} \\[6pt] &= \frac{n!}{k! \cdot (n-k)!} \qquad \because n \cdot (n-1)! = n! \\[6pt] &= {}_{n}\mathrm{C}_{k} \qquad \because \text{二項係数の定義} \end{align*} $$$\Box$
$n$ を自然数、$k$ を整数で $0 \le k \le n-1$ とする。このとき、次の等式が成り立つ。
$$
\binom{n}{k+1} = \frac{n}{k+1} \binom{n-1}{k}
$$
二項係数 $\binom{n}{k}$ は次のように定義される。
$$
\binom{n}{k} = \frac{n!}{k!(n-k)!}
$$
ここで、二項係数の定義より、
$$
\binom{n}{k+1} = \frac{n!}{(k+1)!(n-k-1)!}
$$
$$
\binom{n-1}{k} = \frac{(n-1)!}{k!(n-k-1)!}
$$
であるが、$\binom{n}{k+1}$ を次のように変形する。
$$
\begin{align}
\binom{n}{k+1} &= \frac{n!}{(k+1)!(n-k-1)!} \\
&= \frac{n \cdot (n-1)!}{(k+1) \cdot k!(n-k-1)!} \ \because\ n!=n・(n-1)!\\
&= \frac{n}{k+1} \cdot \frac{(n-1)!}{k!(n-k-1)!} \\
&= \frac{n}{k+1} \cdot \frac{(n-1)!}{k!(\{n-1\}-k)!} \\
&= \frac{n}{k+1} \binom{n-1}{k}\ \because\ \binom{n}{k} = \frac{n!}{k!(n-k)!}
\end{align}
$$
したがって、$n$ を自然数、$k$ を整数で $0 \le k \le n-1$ に対して、次の等式が成り立つ。
$$
\binom{n}{k+1} = \frac{n}{k+1} \binom{n-1}{k}
$$
が成り立つ。
$$ \Box$$
$\binom{n}{k+1}$ → $0 \le k+1 \le n$ なので $ -1 \le k \le n-1$、自然数なら $0 \le k \le n-1$
$\binom{n-1}{k}$ → $0 \le k \le n-1$
したがって、この恒等式が「定義どおりの二項係数」で成り立つ範囲は
$n$ を自然数、$k$ を整数で $0 \le k \le n-1$ とする必要がある。
$n$ は正整数、$k$ は整数で $1 \le k \le n-1$ のとき
$$
\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}
$$
が成り立つ。
二項係数 $\binom{n}{k}$ は次のように定義される。
$$
\binom{n}{k} = \frac{n!}{k!(n-k)!}
$$
二項係数の定義を用いて、$\binom{n-1}{k-1}$ と $\binom{n-1}{k}$ を次のように表す。
$$
\binom{n-1}{k-1} = \frac{(n-1)!}{(k-1)!(n-k)!}
$$
$$
\binom{n-1}{k} = \frac{(n-1)!}{k!(n-1-k)!}
$$
これらの二項係数の和を計算すると、
$$
\binom{n-1}{k-1} + \binom{n-1}{k} = \frac{(n-1)!}{(k-1)!(n-k)!} + \frac{(n-1)!}{k!(n-1-k)!}
$$
分母を揃えるために、$\binom{n-1}{k-1}$ の分母と分子に $k$ を掛け、$\binom{n-1}{k}$ の分母と分子に $(n-k)$ を掛ければ、
$$
\binom{n-1}{k-1} = \frac{k(n-1)!}{k(k-1)!(n-k)!} = \frac{k(n-1)!}{k!(n-k)!}\ \because\ k・(k-1)=k!
$$
$$
\begin{align}
\binom{n-1}{k} &= \frac{(n-k)(n-1)!}{k!(n-k)(n-1-k)!} \\
&= \frac{(n-k)(n-1)!}{k!(n-k)(n-k-1)!} \\
&=\frac{(n-k)(n-1)!}{k!(n-k)!}\ \because\ (n-k)(n-k-1)!=(n-k)!
\end{align}
$$
これらを足し合わせると、
$$
\begin{align}
\binom{n-1}{k-1} + \binom{n-1}{k} &= \frac{k(n-1)!}{k!(n-k)!} + \frac{(n-k)(n-1)!}{k!(n-k)!} \\
&= \frac{(k + (n-k))(n-1)!}{k!(n-k)!} \\
&= \frac{n(n-1)!}{k!(n-k)!} \\
&= \frac{n!}{k!(n-k)!}\\
&= \binom{n}{k}
\end{align}
$$
$$ \Box$$
二項係数を
$$
\binom{m}{\ell} = \frac{m!}{\ell!(m-\ell)!}
$$
$(0\le \ell \le m)$ で定義しているので、右辺が意味を持つには
$\binom{n-1}{k-1}$ のために $0 \le k-1 \le n-1 \Rightarrow 1 \le k \le n$
$\binom{n-1}{k}$ のために $0 \le k \le n-1$ が必要で、両方を満たすのは
$$
1 \le k \le n-1
$$
のときである。
任意の自然数 $n$ と $0 \leq k \leq n$ なる整数 $k$ に対して
$$
\begin{aligned}
\binom{n}{k} &= \binom{n}{n-k}
\end{aligned}
$$
である。
まず、$n$ を $0$ も含む自然数とし、$k$ を$0 \leq k \leq n$の整数とする。
さらに、各非負整数 $n$ に対して、$n!$ は
$$
n! = n\cdot(n-1)\cdot(n-2)\cdots1 \quad (0! = 1)
$$
と定義される。次に、二項係数の定義より、
$$
\begin{aligned}
\binom{n}{k} &= \frac{n!}{\, k!(n-k)!}\cdots①
\end{aligned}
$$
同様にして、
$$
\begin{aligned}
\binom{n}{n-k} &= \frac{n!}{\,(n-k)!\bigl(n-(n-k)\bigr)!}\cdots②
\end{aligned}
$$
である。ここで、$n-(n-k)$を以下のように変形する。
$$
\begin{aligned}
n-(n-k) &= n-n+k \\
&= (n-n)+k \\
&= 0+k \\
&= k
\end{aligned}
$$
となる。したがって、
$$
\begin{aligned}
\binom{n}{n-k} &= \frac{n!}{\,(n-k)! \, k!}
\end{aligned}
$$
と書き直される。さらに、$k!(n-k)!$ と $(n-k)!k!$ は乗法の交換法則により等しいため、式①と式②の分母は一致する。すなわち、
$$
\begin{aligned}
\frac{n!}{\, k!(n-k)!} = \frac{n!}{\,(n-k)!k!}
\end{aligned}
$$
となる。以上より、二項係数の定義と整数の基本的な演算の性質から、任意の自然数 $n$ と $0 \leq k \leq n$ のもとで
$$
\binom{n}{k} = \binom{n}{n-k}
$$
が成り立つことが示された。
$$ \Box$$
自然数 $n$ に対して、
$$
(p + q)^n = \sum_{k=0}^{n} \binom{n}{k} p^k q^{n-k} = \sum_{k=0}^{n} \binom{n}{k} p^{n-k} q^k
$$
が成り立つ。これを 二項定理 (binomial theorem) という。
数学的帰納法によって、任意の $n = 1, 2, \cdots$ に対して、
$$
(p + q)^n = \sum_{k=0}^{n} \binom{n}{k} p^k q^{n-k}
$$
が成り立つことを証明する。
はじめに$n=1$の場合を示す。組み合わせの定義より
$$
\binom{n}{k} := \frac{n!}{(n-k)!k!}
$$
加えて、$0! = 1$ と定義されることから、
$$
\binom{1}{0} = \frac{1!}{1!0!} = 1
$$
$$
\binom{1}{1} = \frac{1!}{0!1!} = 1
$$
であるので、
$$
\sum_{k=0}^{1} \binom{1}{k} p^k q^{1-k} = \binom{1}{0} p^0 q^1 + \binom{1}{1} p^1 q^0 \\
= p + q
$$
が成り立つ。これは、$n=1$のとき左辺は$p+q$であるから、$n = 1$ の場合は二項定理が成立する。
$$ $$
続いて、$n = m$ の場合の二項定理
$$
(p + q)^m = \sum_{k=0}^{m} \binom{m}{k} p^k q^{m-k}
$$
が成り立つと仮定した上で、$n = m + 1$ 場合にも
$$
(p + q)^{m+1} = \sum_{k=0}^{m+1} \binom{m+1}{k} p^k q^{m+1-k}
$$
が成り立つことを証明する(数学的帰納法)。
$$ $$
まず $(p + q)^{m+1}$ は仮定より、
$$
\begin{align*}
(p + q)^{m+1} &= (p + q)(p + q)^m \\
&= (p + q) \sum_{k=0}^{m} \binom{m}{k} p^k q^{m-k} \\
&= \sum_{k=0}^{m} \binom{m}{k} p^{k+1} q^{m-k} + \sum_{k=0}^{m} \binom{m}{k} p^k q^{m+1-k}
\end{align*}$$
と表せるが、右辺の第一項は、
$$
\begin{align*}
\sum_{k=0}^{m} \binom{m}{k} p^{k+1} q^{m-k}&=\binom{m}{0} p^1 q^m + \binom{m}{1} p^2 q^{m-1} + \cdots + \binom{m}{m-1} p^m q^1 + \binom{m}{m} p^{m+1} q^0 \\
&= \sum_{k=1}^{m} \binom{m}{k-1} p^k q^{m-(k-1)} + \binom{m}{m} p^{m+1}
\end{align*}
$$
と表せ、第二項は、
$$
\begin{align*}
\sum_{k=0}^{m} \binom{m}{k} p^k q^{m+1-k} &= \binom{m}{0} p^0 q^{m+1} + \binom{m}{1} p^1 q^m + \cdots + \binom{m}{m-1} p^{m-1} q^2 + \binom{m}{m} p^m q^1 \\
&= \binom{m}{0} p^0 q^{m+1} + \sum_{k=1}^{m} \binom{m}{k} p^k q^{m+1-k}
\end{align*}
$$
と表せる。したがって、
$$
\begin{align*}
(p + q)^{m+1}&= \sum_{k=0}^{m} \binom{m}{k} p^{k+1} q^{m-k} + \sum_{k=0}^{m} \binom{m}{k} p^k q^{m+1-k} \\
&= \sum_{k=1}^{m} \binom{m}{k-1} p^k q^{m-(k-1)} + \binom{m}{m} p^{m+1} + \binom{m}{0} p^0 q^{m+1} + \sum_{k=1}^{m} \binom{m}{k} p^k q^{m+1-k}\\
&= \binom{m}{m} p^{m+1} + \sum_{k=1}^{m} \binom{m}{k-1} p^k q^{m-(k-1)}+ \sum_{k=1}^{m} \binom{m}{k} p^k q^{m+1-k}+\binom{m}{0} p^0 q^{m+1} \\
&= \binom{m}{m} p^{m+1} + \sum_{k=1}^{m} \binom{m}{k-1} p^k q^{m+1-k}+ \sum_{k=1}^{m} \binom{m}{k} p^k q^{m+1-k}+\binom{m}{0} p^0 q^{m+1} \\
&= \binom{m}{0} p^0 q^{m+1} + \sum_{k=1}^{m} \left( \binom{m}{k-1} + \binom{m}{k} \right) p^k q^{m+1-k} + \binom{m}{m} p^{m+1}\\
\end{align*}
$$
と表せる。ここで第$2$項は組合せの定義より、
$$
\begin{align*}
\binom{m}{k-1} + \binom{m}{k}&= \frac{m!}{(m-(k-1))!(k-1)!} + \frac{m!}{(m-k)!k!} \\
\end{align*}
$$
ここで、第$1$項については$m!$を展開すると、分母の$(m-(k-1))!$以降が通分される。
同様に、第$2$項についても$m!$を展開すると、分母の$(m-k)!$以降が通分されるから、
$$
\begin{align*}
\frac{m!}{(m-(k-1))!(k-1)!} + \frac{m!}{(m-k)!k!}&= \frac{m(m-1) \cdots \{ m-(k-1)+1 \}}{(k-1)!} + \frac{m(m-1) \cdots (m-k+1)}{k!}\\
&= \frac{m(m-1) \cdots \{ m-(k-1)+1 \}}{(k-1)!} +\frac{m(m-1) \cdots (m-k+1)}{ k・(k-1)!}\\
&= \frac{m(m-1) \cdots (m-k+2)}{(k-1)!} +\frac{m(m-1) \cdots (m-k+2)(m-k+1)}{ k・(k-1)!}\\
\end{align*}
$$
ここで2つの項を第1項の$\displaystyle \frac{m(m-1) \cdots (m-k+2)}{(k-1)!}$で括ると、
$$
\begin{align*}
\frac{m!}{(m-(k-1))!(k-1)!} + \frac{m!}{(m-k)!k!}&= \frac{m(m-1) \cdots \{ m-(k-1)+1 \}}{(k-1)!} \left\{ 1 + \frac{1}{k}(m-k+1) \right\} \\
&= \frac{m(m-1) \cdots \{ m-(k-1)+1 \}}{(k-1)!} \left( \frac{m+1}{k} \right) \\
\end{align*}
$$
階乗の定義より、$k・(k-1)!=k!$であるから、分母は$k!$がまとめることができて、
$$
\begin{align*}
\frac{m!}{(m-(k-1))!(k-1)!} + \frac{m!}{(m-k)!k!}&= \frac{(m+1)m(m-1) \cdots (m-(k-1)+1)}{k!}\\
&= \frac{(m+1)m(m-1) \cdots (m+1-k+1)}{k!}\\
\end{align*}
$$
ここで、分子を$(m+1)!$で無理やり置き換えると、$(m+1)!$の中で$(\{m+1\}-k)$以降が消えなければならないから、
分母に$(\{m+1\}-k)!$を掛ければよい、したがって、
$$
\begin{align*}
\frac{(m+1)m(m-1) \cdots (\{m+1\}-k+1)}{k!}&= \frac{(m+1)!}{(m+1-k)!k!}\\
&= \binom{m+1}{k}\\
\end{align*}
$$
が成り立つので、まとめると
$$
\binom{m}{k-1} + \binom{m}{k}= \binom{m+1}{k}
$$
である。ゆえに、
$$
\begin{align*}
(p + q)^{m+1}&= \binom{m}{0} p^0 q^{m+1} + \sum_{k=1}^{m} \left( \binom{m}{k-1} + \binom{m}{k} \right) p^k q^{m+1-k} + \binom{m}{m} p^{m+1}\\
&= \binom{m}{0} p^0 q^{m+1} + \sum_{k=1}^{m} \binom{m+1}{k} p^k q^{m+1-k} + \binom{m}{m} p^{m+1}\\
&= \sum_{k=0}^{m+1} \binom{m+1}{k} p^k q^{m+1-k}\\
\end{align*}
$$
が成り立つ。
これは $n = m+1$ の場合の二項定理である。ここで、3つめの等号で
$$
\binom{m}{0} = 1 = \binom{m+1}{0}
$$
$$
\binom{m}{m} = 1 = \binom{m+1}{m+1}
$$
であることを用いた。
$$ $$
以上から、数学的帰納法によって、任意の $n = 1, 2, \cdots$ に対して、
$$
(p + q)^n = \sum_{k=0}^{n} \binom{n}{k} p^k q^{n-k}
$$
が成り立つことが証明された。
最後に、
$$
\sum_{k=0}^{n} \binom{n}{k} p^k q^{n-k} = \sum_{k=0}^{n} \binom{n}{k} p^{n-k} q^k
$$
を証明する。左辺に対して $n-k = m$ と置くと、$k = n-m$であるから、
$$
\sum_{k=0}^{n} \binom{n}{k} p^k q^{n-k} = \sum_{m=0}^{n} \binom{n}{n-m} p^{n-m} q^m
$$
であるが、$\binom{n}{n-m}$は組合せの定義より、
$$
\binom{n}{n-m} = \frac{n!}{(n-(n-m))!(n-m)!} = \frac{n!}{m!(n-m)!} = \binom{n}{m}
$$
が成り立つので、
$$
\sum_{k=0}^{n} \binom{n}{k} p^k q^{n-k} = \sum_{m=0}^{n} \binom{n}{m} p^{n-m} q^m \\
$$
ここで、$m,k$はいずれも$0$から$n$に渡る変数であるから、$k=m$と見なせば
$$
\sum_{k=0}^{n} \binom{n}{k} p^k q^{n-k} = \sum_{k=0}^{n} \binom{n}{k} p^{n-k} q^k
$$
が成り立つ。以上より、
$$
(p + q)^n = \sum_{k=0}^{n} \binom{n}{k} p^k q^{n-k}= \sum_{k=0}^{n} \binom{n}{k} p^{n-k} q^k
$$
であることが示された。
$n = 1, 2, 3, 4, 5$ の場合、以下の通りである。
$$
\begin{align*}
(p + q)^1 &= \sum_{k=0}^{1} \binom{1}{k} p^{1-k} q^k \\
&= \binom{1}{0} p^1 q^0 + \binom{1}{1} p^0 q^1 \\
&= p + q\\
(p + q)^2 &= \sum_{k=0}^{2} \binom{2}{k} p^{2-k} q^k \\
&= \binom{2}{0} p^2 q^0 + \binom{2}{1} p^1 q^1 + \binom{2}{2} p^0 q^2 \\
&= p^2 + 2pq + q^2\\
(p + q)^3 &= \sum_{k=0}^{3} \binom{3}{k} p^{3-k} q^k \\
&= \binom{3}{0} p^3 q^0 + \binom{3}{1} p^2 q^1 + \binom{3}{2} p^1 q^2 + \binom{3}{3} p^0 q^3 \\
&= p^3 + 3p^2q + 3pq^2 + q^3\\
(p + q)^4 &= \sum_{k=0}^{4} \binom{4}{k} p^{4-k} q^k \\
&= \binom{4}{0} p^4 q^0 + \binom{4}{1} p^3 q^1 + \binom{4}{2} p^2 q^2 + \binom{4}{3} p^1 q^3 + \binom{4}{4} p^0 q^4 \\
&= p^4 + 4p^3q + 6p^2q^2 + 4pq^3 + q^4\\
(p + q)^5 &= \sum_{k=0}^{5} \binom{5}{k} p^{5-k} q^k \\
&= \binom{5}{0} p^5 q^0 + \binom{5}{1} p^4 q^1 + \binom{5}{2} p^3 q^2 + \binom{5}{3} p^2 q^3 + \binom{5}{4} p^1 q^4 + \binom{5}{5} p^0 q^5 \\
&= p^5 + 5p^4q + 10p^3q^2 + 10p^2q^3 + 5pq^4 + q^5\\
\end{align*}
$$
自然数$n$に対して
$$
\displaystyle\sum_{k=0}^{n}\binom{n}{k}=2^{\,n}
$$
が成り立つ。
二項定理より、
$$
(1+1)^{n}=\sum_{k=0}^{n}\binom{n}{k}1^{\,k}1^{\,n-k}
$$
の左辺は$2^{n}$、右辺は和そのものだから
$$
\sum_{k=0}^{n}\binom{n}{k}=2^{\,n}
$$
が従う。
$$ \Box$$
任意の$ n \in \mathbb{N} $ 及び $ k \in \mathbb{Z} $で $ 1 \le k \le n $ を満たすとき、
$$
\begin{aligned}
\binom{n+1}{k} &= \binom{n}{k-1} + \binom{n}{k}
\end{aligned}
$$
が成り立つ。
左辺の$\binom{n+1}{k}$および右辺の$\binom{n}{k-1}$と$\binom{n}{k}$をすべて定義に展開して比較する。
まず左辺から展開する。
$$
\binom{n+1}{k} = \frac{(n+1)!}{k! (n+1-k)!}
$$
一方、右辺のそれぞれも展開すると
$$
\binom{n}{k-1} = \frac{n!}{(k-1)! (n-(k-1))!} = \frac{n!}{(k-1)! (n-k+1)!}
$$
$$
\binom{n}{k} = \frac{n!}{k! (n-k)!}
$$
よって、右辺全体は
$$
\binom{n}{k-1} + \binom{n}{k} = \frac{n!}{(k-1)! (n-k+1)!} + \frac{n!}{k! (n-k)!}
$$
これを通分してまとめることを考える。分母を揃える。
$(k-1)!$と$k!$の関係に注意すると、
$$
k! = k \times (k-1)!
$$
また、$(n-k)!$と$(n-k+1)!$の関係にも注意すると、
$$
(n-k+1)! = (n-k+1)(n-k)!
$$
これらを使うと、$\binom{n}{k-1}$は
$$
\binom{n}{k-1}=\frac{n!}{(k-1)! (n-k+1)!} = \frac{n!}{(k-1)! (n-k+1)(n-k)!} = \frac{n!}{(k-1)!(n-k)!} \times \frac{1}{n-k+1}
$$
であり、$\binom{n}{k}$はそのまま
$$
\binom{n}{k}=\frac{n!}{k!(n-k)!}
$$
である。ここで、$k! = k (k-1)!$だから、
$$
\binom{n}{k}=\frac{n!}{k!(n-k)!} = \frac{n!}{k (k-1)! (n-k)!}
$$
となる。したがって、右辺の和は
$$
\binom{n}{k-1}+\binom{n}{k}=\frac{n!}{(k-1)!(n-k)!} \times \frac{1}{n-k+1}+\frac{n!}{k (k-1)! (n-k)!}
$$
であるから、
$$
\frac{n!}{(k-1)!(n-k)!} \left( \frac{1}{n-k+1} + \frac{1}{k} \right)
$$
となる。括弧内を通分すると、
$$
\frac{1}{n-k+1} + \frac{1}{k} = \frac{k + (n-k+1)}{k(n-k+1)} = \frac{n+1}{k(n-k+1)}
$$
よって、右辺全体は
$$
\frac{n!}{(k-1)!(n-k)!} \times \frac{n+1}{k(n-k+1)}
$$
ここで、分子と分母をまとめると
$$
\frac{(n+1) n!}{k (k-1)! (n-k+1)(n-k)!}
$$
となる。ここでさらに、$(n-k+1)(n-k)! = (n-k+1)!$なので、分母は
$$
k (k-1)! (n-k+1)!
$$
となる。また、$k(k-1)! = k!$なので、分母は
$$
k! (n-k+1)!
$$
である。同様に、
$$
(n+1)\times n!=(n+1)!
$$
である。以上をまとめると、右辺は
$$
\frac{(n+1)!}{k! (n-k+1)!}
$$
であり、これは左辺$\binom{n+1}{k}$の展開のままである。よって、命題
$$
\binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k}
$$
が証明された。
$$ \Box$$
任意の自然数 $n \in \mathbb{N}$ と任意の整数 $k \in \mathbb{Z}$ について、$1 \leq k \leq n-1$ を満たすならば、次の等式が成立する。
$$
\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}
$$
すべての項を展開して比較する。組み合わせの定義より、
$$
\binom{n}{k} = \frac{n!}{k! (n-k)!}
$$
$$
\binom{n-1}{k} = \frac{(n-1)!}{k! (n-1-k)!}
$$
$$
\binom{n-1}{k-1} = \frac{(n-1)!}{(k-1)! (n-k)!}
$$
である。まず、右辺
$$
\binom{n-1}{k} + \binom{n-1}{k-1}
$$
を計算する。それぞれを分母を揃えて通分するために、共通の分母を求める。
まず、$\binom{n-1}{k}$は
$$
\binom{n-1}{k} = \frac{(n-1)!}{k!(n-1-k)!}
$$
であり、$\binom{n-1}{k-1}$は
$$
\binom{n-1}{k-1} = \frac{(n-1)!}{(k-1)!(n-k)!}
$$
である。 このままでは分母が異なるため、それぞれ分母の形を変換する。
まず、$(k-1)!$と$k!$の関係に注意する。
$$
k! = k \times (k-1)!
$$
また、$(n-1-k)!$と$(n-k)!$の関係に注意する。
$$
(n-1-k)! = (n-k-1)! = \frac{(n-k)!}{n-k}
$$
なぜなら、
$$
(n-k)! = (n-k)(n-k-1)!
$$
であるから、両辺を$(n-k)$で割れば
$$
(n-k-1)! = \frac{(n-k)!}{n-k}
$$
である。以上より、
$$
(n-1-k)! = \frac{(n-k)!}{n-k}
$$
が成り立つ。これらを用いて、それぞれの項を変形する。
まず、$\binom{n-1}{k}$を変形すると、
$$
\binom{n-1}{k} = \frac{(n-1)!}{k! \cdot (n-1-k)!} = \frac{(n-1)!}{k!} \times \frac{n-k}{(n-k)!}
$$
よって
$$
\binom{n-1}{k} = \frac{(n-1)!(n-k)}{k!(n-k)!}
$$
同様に、$\binom{n-1}{k-1}$は
$$
\binom{n-1}{k-1} = \frac{(n-1)!}{(k-1)!(n-k)!}
$$
であるが、$k! = k(k-1)!$より、変形すれば $(k-1)! = \frac{k!}{k}$ だから
$$
\binom{n-1}{k-1} = \frac{(n-1)! \times k}{k! (n-k)!}
$$
である。したがって、右辺の和は
$$
\binom{n-1}{k} + \binom{n-1}{k-1} = \frac{(n-1)!(n-k)}{k!(n-k)!} + \frac{(n-1)!k}{k!(n-k)!}
$$
である。分母が共通なのでまとめると、
$$
= \frac{(n-1)!}{k!(n-k)!} \left( (n-k) + k \right)
$$
括弧内を計算すると
$$
(n-k)+k = n
$$
よって
$$
= \frac{(n-1)!}{k!(n-k)!} \times n
$$
すなわち
$$
= \frac{n (n-1)!}{k!(n-k)!}
$$
ここで、$n(n-1)! = n!$なので、
$$
= \frac{n!}{k!(n-k)!}
$$
これはまさに、左辺の$\binom{n}{k}$の定義そのものである。
よって、
$$
\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}
$$
が示された。
$$ \Box$$
任意の自然数 $n$ に対して
$$
\displaystyle\sum_{k=0}^{n}\binom{n}{k}^{2}=\binom{2n}{n}
$$
が成り立つ。
二項定理より、
$$
(1+x)^{n}= \sum_{k=0}^{n}\binom{n}{k}x^{\,k}
$$
が成り立つ。ここで$x$は任意の実数とする。
$ $
この等式の両辺を自乗すると、左辺は
$$
\bigl((1+x)^{n}\bigr)^{2}=(1+x)^{n}(1+x)^{n}
$$
指数法則より
$$
(1+x)^{2n} \quad\because\ \text{指数法則}\ (a^{m})^{\,p}=a^{\,mp}
$$
この$(1+x)^{2n}$に対して、二項定理を適用すれば
$$
\begin{align}
(1+x)^{2n}
&= \sum_{r=0}^{2n} \binom{2n}{r} 1^{\,2n-r} x^{\,r}
\quad \because\ \text{二項定理 }(a+b)^m
= \displaystyle\sum_{r=0}^{m} \binom{m}{r} a^{\,m-r} b^{\,r} \\[4pt]
&= \sum_{r=0}^{2n} \binom{2n}{r} x^{\,r}
\end{align}
$$
一方で$(1+x)^{n}$を二項展開した式
$$
\sum_{k=0}^{n}\binom{n}{k}x^{\,k}
$$
を二つ掛け合わせると、ある次数 $r$ の項 $x^r$ の係数は、$k+\ell=r$ となるペアの和であるから(補足を参照)
$$
\Bigl(\sum_{k=0}^{n}\binom{n}{k}x^{\,k}\Bigr)\Bigl(\sum_{\ell=0}^{n}\binom{n}{\ell}x^{\,\ell}\Bigr)
=\sum_{r=0}^{2n}\Bigl(\sum_{k=0}^{r}\binom{n}{k}\binom{n}{\,r-k}\Bigr)x^{\,r}
$$
$ $
以上で左辺の二通りの展開が得られたので、係数比較を行う。
次数$r$の$x^{r}$に付随する係数が両展開で一致することから
$$
\sum_{k=0}^{r}\binom{n}{k}\binom{n}{\,r-k}= \binom{2n}{r}
$$
ここで$r=n$を代入すると
$$
\sum_{k=0}^{n}\binom{n}{k}\binom{n}{\,n-k}= \binom{2n}{n}
$$
さらに二項係数の対称性
$$
\binom{n}{\,n-k}= \binom{n}{k}
$$
を用いれば左辺は
$$
\sum_{k=0}^{n}\binom{n}{k}\binom{n}{k}= \sum_{k=0}^{n}\binom{n}{k}^{2}
$$
となる。したがって
$$
\sum_{k=0}^{n}\binom{n}{k}^{2}= \binom{2n}{n}
$$
が示された。
$$ \Box$$
$2$つの多項式
$$
A(x) = \sum_{k=0}^{n}\binom{n}{k}x^{k},\qquad
B(x) = \sum_{\ell=0}^{n}\binom{n}{\ell}x^{\ell}
$$
において、その積は
$$
A(x)B(x)
= \left(\sum_{k=0}^{n}\binom{n}{k}x^{k}\right)
\left(\sum_{\ell=0}^{n}\binom{n}{\ell}x^{\ell}\right)
$$
である。分配法則に従ってすべて掛け合わせると
$$
\begin{aligned}
&\Bigl(\sum_{k=0}^{n}\binom{n}{k}x^{k}\Bigr)
\Bigl(\sum_{\ell=0}^{n}\binom{n}{\ell}x^{\ell}\Bigr)\\
&= \left(\binom{n}{0}x^0 + \binom{n}{1}x^1 + \cdots + \binom{n}{n}x^n\right)
\left(\binom{n}{0}x^0 + \binom{n}{1}x^1 + \cdots + \binom{n}{n}x^n\right).
\end{aligned}
$$
すなわち、
$$
\begin{aligned}
A(x)B(x)&=\Bigl(\sum_{k=0}^{n}\binom{n}{k}x^{k}\Bigr)
\Bigl(\sum_{\ell=0}^{n}\binom{n}{\ell}x^{\ell}\Bigr)\\
&= \sum_{k=0}^{n}\sum_{\ell=0}^{n}
\binom{n}{k}\binom{n}{\ell}x^{k+\ell}
\end{aligned}
$$
となる。ここで、出てくる項はすべて $x^{k+\ell}$ の形をしている。
したがって、ある次数 $r$ の項 $x^r$ が生まれるのは、ちょうど $k+\ell = r$ となる組合せだけである。
$ $
例えば
$$
(a_0 + a_1 x + a_2 x^2)(b_0 + b_1 x + b_2 x^2)
$$
を展開すると
$$
\begin{aligned}
&= a_0b_0
+(a_0b_1 + a_1b_0)x
+(a_0b_2 + a_1b_1 + a_2b_0)x^2
+\cdots+ (a_1b_2 + a_2b_1)x^3
+ a_2b_2x^4
\end{aligned}
$$
- ($x^0$) の係数：$a_0b_0$（$(0+0=0)$ のペア）
- ($x^1$) の係数：$a_0b_1 + a_1b_0$（$(0+1,1+0)$のペア）
- ($x^2$) の係数：$a_0b_2 + a_1b_1 + a_2b_0$（$(0+2,1+1,2+0)$ のペア）
- …
となっているのが、「$(k+\ell=r)$ となるペアの和」という主張そのものになっている。
$ $
また、$k,\ell$ はどちらも $0,1,\dots,n$ のいずれかなので、指数 $k+\ell(=r)$ は $0$ から $2n$ までの整数をとる。
したがって、$A(x)B(x)$ 全体は
$$
A(x)B(x)
= \sum_{r=0}^{2n} c_r x^{r}
$$
と書ける。ここで、$c_r$ は $x^{r}$ の係数である。
$x^{r}$ の係数 $c_r$ は、元の係数$\binom{n}{k}\binom{n}{\ell}$のうち、$k+\ell=r$ となるペア $(k,\ell)$ からなる項だけの和になるから、
$$
c_r = \sum_{k+\ell=r} \binom{n}{k}\binom{n}{\ell}
$$
となる。
例えば、$(1+x)^2 = \binom{2}{0}x^0 + \binom{2}{1}x^1 + \binom{2}{2}x^2=1 + 2x + x^2$ を例に取ると、
$$
\begin{aligned}
&(\binom{2}{0}x^0 + \binom{2}{1}x^1 + \binom{2}{2}x^2)
(\binom{2}{0}x^0 + \binom{2}{1}x^1 + \binom{2}{2}x^2) \\
&= \underbrace{\binom{2}{0}\binom{2}{0}x^{0+0}}_{\text{$x^0$ の項}} \\[4pt]
&\quad + \underbrace{\bigl(
\binom{2}{0}\binom{2}{1}x^{0+1}
+ \binom{2}{1}\binom{2}{0}x^{1+0}
\bigr)}_{\text{$x^1$ の項}} \\[4pt]
&\quad + \underbrace{\bigl(
\binom{2}{0}\binom{2}{2}x^{0+2}
+ \binom{2}{1}\binom{2}{1}x^{1+1}
+ \binom{2}{2}\binom{2}{0}x^{2+0}
\bigr)}_{\text{$x^2$ の項}} \\[4pt]
&\quad + \underbrace{\bigl(
\binom{2}{1}\binom{2}{2}x^{1+2}
+ \binom{2}{2}\binom{2}{1}x^{2+1}
\bigr)}_{\text{$x^3$ の項}} \\[4pt]
&\quad + \underbrace{\binom{2}{2}\binom{2}{2}x^{2+2}}_{\text{$x^4$ の項}}
\end{aligned}
$$
次に変数$k$だけの形に書き換えるため、ここで改めて $\ell = r-k$ とおけば、$0\le \ell \le n$ だから
$$
c_r = \sum_{k+\ell=r} \binom{n}{k}\binom{n}{\ell}
= \sum_{\substack{0\le k,\ell \le n\\ k+\ell=r}} \binom{n}{k}\binom{n}{\ell}
= \sum_{\substack{0\le k\le n\\ 0\le r-k\le n}} \binom{n}{k}\binom{n}{r-k}
$$
条件を整理すると、
- $0 \le k$
- $k \le n$
- $0 \le r-k \iff k \le r$
- $r-k \le n \iff r-n \le k$
-これを全部まとめると
$$
\max(0,,r-n) \le k \le \min(r,,n)
$$
である。したがって、
$$
c_r
= \sum_{k=\max(0,r-n)}^{\min(r,n)} \binom{n}{k}\binom{n}{r-k}
$$
この式は、どの $r$ に対しても（$0\sim 2n$ のどれを取っても）成り立つ。
したがって、$r=n$ の場合を考えると、その場合 $0$ から $n$ まででちょうど一致するから、
よって、積全体は
$$
\left(\sum_{k=0}^{n}\binom{n}{k}x^{k}\right)
\left(\sum_{\ell=0}^{n}\binom{n}{\ell}x^{\ell}\right)
= \sum_{r=0}^{2n}\left(\sum_{k=0}^{r}\binom{n}{k}\binom{n}{r-k}\right)x^{r}
$$
となる。
任意の自然数 $ n \geq 1 $ に対して、
$$
\sum_{k=0}^n (-1)^k \binom{n}{k} = 0
$$
が成り立つ。
二項定理によれば、任意の整数 $n \geq 0$ に対して、
$$
(1 + x)^n = \sum_{k=0}^{n} \binom{n}{k} x^k
$$
が成り立つ。
ここで $x = -1$ を代入すると、
$$
\begin{align}
(1 + (-1))^n &= \sum_{k=0}^{n} \binom{n}{k} (-1)^k \\
0^n &= \sum_{k=0}^{n} (-1)^k \binom{n}{k}
\end{align}
$$
左辺は $n \geq 1$ のとき $0^n = 0$ であるから、
$$
\sum_{k=0}^n (-1)^k \binom{n}{k} = 0
$$
が示された。
$$ \Box$$
異なる $n$ 種類のものから重複を許して $r$ 個選ぶ方法の総数は
$$
\binom{n + r - 1}{r}
$$
である。
この問題は、選択できる総数がちょうど $r$ 個選ぶ という制約のもとで、
$n$ 種類のものからいくつでも選択できる組み合わせの総数であるから、
これは以下の条件を満たす非負整数の組 $(x_1, x_2, \dots, x_n)$ の総数を求めることと等価である。
$$
\begin{cases}
x_1 + x_2 + \cdots + x_n = r, \\
x_i \geq 0 \quad (i = 1, 2, \dots, n).
\end{cases}
$$
ここで、各 $x_i$ は種類 $i$ のものを選んだ個数を表す。
非負整数解の総数を求めるために、「仕切りと玉」の方法を用いる。
いま、"仕切り"と"玉"を以下のように定義する。
$$
\text{玉（スター）：選んだものを表す $r$ 個の玉を指す。}
$$
$$
\text{仕切り（バー）：種類の区切りを表す $n-1$ 個の仕切りを指す。}
$$
このとき、玉と仕切りの並べ方一つ一つが、方程式の非負整数解一つ一つに対応する。
このようにして、玉と仕切りを一列に並べ、その並べ方の総数を求める問題に帰着させる。
例えば、$r = 5$, $n = 3$ (区間の数)の場合、図で表すと
$$
\bullet \bullet \ | \ \bullet \ | \ \bullet \bullet
$$
は、非負整数解 $x_1 = 2$, $x_2 = 1$, $x_3 = 2$ に対応する。
仕切りの数は$n=3$のとき、図からも明らかなように$n-1=2$個である。
ここで、"仕切り"と"玉"の総数が、"仕切り"と"玉"の配置できる数に相当する。
すなわち、"仕切り"と"玉"は
$$
r+(n-1)
$$
からなる配置箇所がある。玉と仕切りを並べる方法は、次のように考えることができる。
・ 全体の $r+n-1$ 個の位置から、玉を置く位置を選ぶ (玉は $r$ 個ある)
・ 選ばなかった位置には仕切りが入る。
ここで、玉同士は区別できない(どの玉も同じものとして扱う)、
また仕切り同士も区別できない(どの仕切りも同じものとして扱う)。
したがって、玉と仕切りの配置パターンだけが重要で、同種の玉や仕切りの並び順は重要ではない。
そのため、(順列ではなく)"組み合わせ"によって求めると、
玉 $r$ 個と仕切り $n - 1$ 個を全て並べる方法の総数は、
$$
\text{玉と仕切りを合わせた $r + n - 1$ 個の位置から、玉を配置する位置を選ぶ組み合わせの数に等しい。}
$$
それはすなわち、組み合わせの表記によって
$$
\binom{n + r - 1}{r}
$$
で与えられる。
$$ \Box$$
また、$n$個の異なるものから重複を許して$r$個を選んだときにできる組み合わせ（重複組み合わせ）の総数を
$$
{}_nH_r := {}_{n+r-1}C_r
$$
などと書くことがある。
「同じものを繰り返し取ってよいという約束のもとで」できる順列を重複順列という。
「同じものを繰り返し取ってよいという約束」は、通常「重複を許して」という言葉で表現される。
これは復元抽出と同義である。
当然だが、重複を許しているため
$n$ 種類のものから $n-1$ 種類が$1$度も選ばれないケースも許容されている事に注意すること。
$ $
すなわち、$1$種類のものだけで$r$個全て埋めてもよく、
それは$1$つの仕切り以外が全て$1$つの玉を内包していない状態である。
要するに、以下のような状態も考えられるという事である。
$$
|\ \ |\ \ |\ \ \bullet \bullet \bullet \bullet\ \bullet
$$
$n$ 個のもののうちで、
$p$ 個が同じ、$q$ 個が同じ、$r$ 個が同じ(したがって$n=p+q+r$)であるとき、
$n$ 個の並べ方の総数は
$$
\begin{aligned}
\frac{n!}{p!q!r!}
\end{aligned}
$$
である。
もっと一般に、$n$ 個のものが $d$ 種類のグループ（各 $p_1, p_2, \ldots, p_d$ 個）に分かれているとき、
それらの並べ方の総数は
$$
\begin{aligned}
\frac{n!}{p_1!p_2! \ldots p_d!}
\end{aligned}
$$
が成り立つ。
全 $n$ 個の位置から $p_1$ 個を選んで種類 $1$ の要素を置く方法は
$$
\binom{n}{p_1}
$$
通り。残り $n-p_1$ 個の位置から $p_2$ 個を選んで種類 $2$ を置く方法は
$$
\binom{n-p_1}{p_2}
$$
通り。この操作を順次繰り返していくと、積の法則により総数は
$$
\binom{n}{p_1}\binom{n-p_1}{p_2}\binom{n-p_1-p_2}{p_3}\dotsm\binom{p_d}{p_d}.
$$
組み合わせの定義
$$
\displaystyle\binom{m}{k}:=\frac{m!}{k!\,(m-k)!}
$$
を用いて順に展開し、分子同士・分母同士を整理すると
$$
\frac{n!}{p_1!\,(n-p_1)!}\cdot\frac{(n-p_1)!}{p_2!\,(n-p_1-p_2)!}\cdot\ldots\cdot\frac{p_d!}{p_d!\,0!}
=\frac{n!}{p_1!\,p_2!\,\dotsm p_d!}.
$$
よって命題は証明された。
$$ \Box$$
この記事を高評価した人
この記事に送られたバッジ
投稿者
