二項係数と二項定理（パスカルの三角形）

二項係数

前節では組合せの個数とその基本的な性質について考えました。本節では、組合せの個数を二項係数として捉え直した上で、二項係数が二項式の展開における係数として現れることを示します。さらに、二項定理から得られる二項係数に関する恒等式や、二項係数を三角形状に配列したパスカルの三角形について考えます。

\(n\)個の要素を持つ集合から\(k\)個の要素を同時に選ぶことにより得られる組合せの個数を、\begin{equation*} C\left( n,k\right)
\end{equation*}と表記しました。ただし、\(n,k\in \mathbb{Z} _{+}\)かつ\(0\leq k\leq n\)です。これを二項係数（binomial coefficient）と呼び、\begin{equation*} \binom{n}{k}=C\left( n,k\right)
\end{equation*}と表記することもあります。

組合せの個数に関する公式より、\(0\leq k\leq n\)を満たす任意の\(n,k\in \mathbb{Z} _{+}\)について、\begin{equation*} \binom{n}{k}=\frac{n!}{k!\left( n-k\right) !}
\end{equation*}が成り立ち、組合せの個数の対称性より、\begin{equation*}
\binom{n}{k}=\binom{n}{n-k}
\end{equation*}が成り立ちます。また、パスカルの関係式より、\(n\geq 2\)かつ\(1\leq k\leq n-1\)を満たす任意の\(n,k\in \mathbb{N} \)について、\begin{equation*} \binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}
\end{equation*}が成り立ちます。

ここまでの内容だけを見ると、二項係数は組合せの個数を別の記号で表したものに過ぎないように見えます。しかし、二項係数は組合せの問題だけでなく、多項式の展開においても重要な役割を果たします。

二項定理（二項式の展開）

実数\(a,b\in \mathbb{R} \)と非負の整数\(n\in \mathbb{Z} _{+}\)から定義される二項式\(a+b\)の\(n\)乗\begin{equation*} \left( a+b\right) ^{n}
\end{equation*}を展開します。小さな\(n\)について具体的に計算すると、\begin{eqnarray*} \left( a+b\right) ^{0} &=&1 \\
\left( a+b\right) ^{1} &=&a+b \\
\left( a+b\right) ^{2} &=&a^{2}+2ab+b^{2} \\
\left( a+b\right) ^{3} &=&a^{3}+3a^{2}b+3ab^{2}+b^{3}
\end{eqnarray*}などとなります。ただし、\(a=b=0\)かつ\(n=0\)の場合を考慮して、\begin{equation*} 0^{0}=1
\end{equation*}と便宜的に定めます。これらの式を見ると、各項は、\begin{equation*}
a^{n-k}b^{k}
\end{equation*}という形をしており、その係数として二項係数
\begin{equation*}
\binom{n}{k}
\end{equation*}が現れていることが分かります。実際、\begin{eqnarray*}
\left( a+b\right) ^{0} &=&1 \\
&=&\binom{0}{0}a^{0-0}b^{0}
\end{eqnarray*}であり、\begin{eqnarray*}
\left( a+b\right) ^{1} &=&a+b \\
&=&\binom{1}{0}a^{1-0}b^{0}+\binom{1}{1}a^{1-1}b^{1}
\end{eqnarray*}であり、\begin{eqnarray*}
\left( a+b\right) ^{2} &=&a^{2}+2ab+b^{2} \\
&=&\binom{2}{0}a^{2-0}b^{0}+\binom{2}{1}a^{2-1}b^{1}+\binom{2}{2}a^{2-2}b^{2}
\end{eqnarray*}であり、\begin{eqnarray*}
\left( a+b\right) ^{3} &=&a^{3}+3a^{2}b+3ab^{2}+b^{3} \\
&=&\binom{3}{0}a^{3-0}b^{0}+\binom{3}{1}a^{3-1}b^{1}+\binom{3}{2}a^{3-2}b^{2}+\binom{3}{3}a^{3-3}b^{3}
\end{eqnarray*}です。この関係を一般化したものが二項定理（binomial theorem）です。

二項係数の和

二項定理の\(a,b\)に特別な値を代入することにより、二項係数に関する様々な恒等式を得ることができます。まずは二項係数の総和に関する恒等式です。

先の命題から得られた関係\begin{equation*}
\sum_{k=0}^{n}\binom{n}{k}=2^{n}
\end{equation*}には組合せ論的な意味もあります。\(n\)個の要素を持つ集合\(A\)について、その部分集合は、要素の個数が\(0\)個であるもの、\(1\)個であるもの、\(\ldots \)、\(n\)個であるものに分類できます。\(k\)個の要素を持つ部分集合の個数は、\begin{equation*} \binom{n}{k}
\end{equation*}であるため、集合\(A\)の部分集合の総数は、 \begin{equation*}
\sum_{k=0}^{n}\binom{n}{k}
\end{equation*}です。一方、\(n\)個の各要素について、それを部分集合に含めるか含めないかという2通りの選択が可能であるため、積の法則より、部分集合の総数は、\begin{equation*} 2^{n}
\end{equation*}です。したがって、\begin{equation*}
\sum_{k=0}^{n}\binom{n}{k}=2^{n}
\end{equation*}が得られます。

二項係数の交代和

以下も成り立ちます。

重み付きの二項係数の和

二項係数の和について、\begin{equation*}
\sum_{k=0}^{n}\binom{n}{k}=2^{n}
\end{equation*}が成り立つことが明らかになりました。一方、それぞれの二項係数に\(k\)を掛けた和\begin{equation*} \sum_{k=0}^{n}k\binom{n}{k}
\end{equation*}を重み付きの和と呼びますが、これをどのように表現できるでしょうか。まずは以下の補題を示します。

以上の命題を踏まえた上で以下を示します。

先の命題から得られた関係\begin{equation*}
\sum_{k=0}^{n}k\binom{n}{k}=n2^{n-1}
\end{equation*}には組合せ論的な意味もあります。\(n\)個の要素を持つ集合\(A\)について、その部分集合の中から1つの特別な要素を指定する場合の数について考えます。まず、\(k\)個の要素を持つ部分集合を選ぶ場合、その選び方は、\begin{equation*} \binom{n}{k}
\end{equation*}通りです。さらに、その\(k\)個の要素の中から1つの特別な要素を指定する方法は\(k\)通りあるため、そのような選び方の総数は、\begin{equation*} k\binom{n}{k}
\end{equation*}です。部分集合に含まれる要素の個数\(k\)は\(0 \)から\(n\)まで取り得るため、すべての場合を合わせると、\begin{equation*} \sum_{k=0}^{n}k\binom{n}{k}
\end{equation*}通りとなります。一方、同じものを別の順序で数えることもできます。まず、特別な要素を\(A\)の\(n\)個の要素から1つ選びます。その選び方は\(n\)通りです。特別な要素を1つ固定すると、残りの\(n-1\)個の各要素について、それを問題としている部分集合に含めるか含めないかを自由に選ぶことができます。したがって、残りの要素の選び方は\(2^{n-1}\)通りです。よって、特別な要素を1つ含む部分集合と、その中の特別な要素を指定する方法の総数は、\begin{equation*} n2^{n-1}
\end{equation*}通りです。以上の2通りの数え方は同じ対象を数えているため、\begin{equation*}
\sum_{k=0}^{n}k\binom{n}{k}=n2^{n-1}
\end{equation*}が得られます。

パスカルの三角形

二項係数\(\binom{n}{k}\)を\(n\)ごとに並べると、次のような三角形状の表が得られます。\begin{equation*} \begin{array}{ccccccccc}
& & & & \binom{0}{0} & & & & \\
& & & \binom{1}{0} & & \binom{1}{1} & & & \\
& & \binom{2}{0} & & \binom{2}{1} & & \binom{2}{2} & & \\
& \binom{3}{0} & & \binom{3}{1} & & \binom{3}{2} & & \binom{3}{3} & \\
\binom{4}{0} & & \binom{4}{1} & & \binom{4}{2} & & \binom{4}{3} & &
\binom{4}{4}\end{array}\end{equation*}それぞれの値を具体的に計算すると、
\begin{equation*}
\begin{array}{ccccccccc}
& & & & 1 & & & & \\
& & & 1 & & 1 & & & \\
& & 1 & & 2 & & 1 & & \\
& 1 & & 3 & & 3 & & 1 & \\
1 & & 4 & & 6 & & 4 & & 1\end{array}\end{equation*}となります。このように二項係数を三角形状に並べたものをパスカルの三角形（Pascal’s triangle）と呼びます。

第\(n\)行を\(n=0\)から数えるものとすると（一番上の行が第\(0\)行）、パスカルの三角形の第\(n\)行には、 \begin{equation*}
\binom{n}{0},\binom{n}{1},\ldots ,\binom{n}{n}
\end{equation*}が左から順に並びます。例えば、第4行には、\begin{equation*}
\binom{4}{0},\binom{4}{1},\binom{4}{2},\binom{4}{3},\binom{4}{4}
\end{equation*}すなわち、\begin{equation*}
1,4,6,4,1
\end{equation*}が並びます。

パスカルの関係式\begin{equation*}
\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}
\end{equation*}より、パスカルの三角形の両端以外の数は、その左上と右上に位置する2つの数の和として求めることができます。また、
\begin{equation*}
\binom{n}{0}=\binom{n}{n}=1
\end{equation*}であるため、各行の両端は常に1です。

パスカルの三角形と二項定理の関係

パスカルの三角形の第\(n\)行に並ぶ数は、\begin{equation*} \binom{n}{0},\binom{n}{1},\ldots ,\binom{n}{n}
\end{equation*}です。一方、二項定理より、\begin{equation*}
\left( a+b\right) ^{n}=\binom{n}{0}a^{n}+\binom{n}{1}a^{n-1}b+\cdots +\binom{n}{n-1}ab^{n-1}+\binom{n}{n}b^{n}
\end{equation*}が成り立ちます。したがって、パスカルの三角形の第\(n\)行に並ぶ数は、二項式\begin{equation*} \left( a+b\right) ^{n}
\end{equation*}を展開したときの係数そのものです。

二項係数の対称性\begin{equation*}
\binom{n}{k}=\binom{n}{n-k}
\end{equation*}より、パスカルの三角形の各行は左右対称です。さらに、二項係数の和\begin{equation*}
\sum_{k=0}^{n}\binom{n}{k}=2^{n}
\end{equation*}より、第\(n\)行に並ぶ数の総和は\(2^{n}\)となります。
このように、パスカルの三角形には、組合せの個数、二項係数、パスカルの関係式、二項定理など、これまでに得られた様々な結果が一つの形にまとめて表れています。

演習問題