パスカルの法則

パスカルの法則は直感的な組合せ論的意味を持ち、それは数え上げによる証明において明確に示される^[2](p44)。

(証明)

二項係数${\displaystyle {\tbinom {n}{k}}}$は、組合せ論においては ${\displaystyle n}$ 個の要素からなる集合から ${\displaystyle k}$ 個の要素だけからなる部分集合の個数に一致するのであった。今、集合からある要素を取り出し、それに ${\displaystyle X}$ というラベルをつけるとする。今、${\displaystyle k}$ 個の元からなる部分集合を構築する際に、${\displaystyle X}$ のラベルがある要素が含まれているか否かで場合分けをする。

まず、${\displaystyle X}$ を含むような部分集合は、 要素 ${\displaystyle X}$ と、それ以外の ${\displaystyle n-1}$ の要素の中から ${\displaystyle k-1}$ 個の要素を選択することによって構成される必要がある。よって、${\displaystyle X}$ を含むような部分集合は ${\displaystyle {\tbinom {n-1}{k-1}}}$ だけ存在する。

一方、${\displaystyle X}$ を含まないような部分集合は、${\displaystyle X}$ 以外の ${\displaystyle n-1}$ の要素からのみで ${\displaystyle k}$ 個の要素を選ぶことによって構成される。よって、そのような部分集合は${\displaystyle {\tbinom {n-1}{k}}}$ だけ存在する。

任意の部分集合は ${\displaystyle X}$ を含むか含んでいないかのどちらかであるので、${\displaystyle n}$ 個の要素の部分集合であって、${\displaystyle k}$ 個の要素からなるものの個数は、 ${\displaystyle k}$ 個の要素の中に ${\displaystyle X}$ を含むものの個数と、含まないものの個数の和として表現される。

以上より、示すべき式${\displaystyle {\tbinom {n}{k}}={\tbinom {n-1}{k-1}}+{\tbinom {n-1}{k}}}$が得られる。 (証明終)

二項係数が階乗表示により定義される場合、パスカルの法則を以下のようにして証明できる:$${\displaystyle {\begin{aligned}{n-1 \choose k}+{n-1 \choose k-1}&={\frac {(n-1)!}{k!(n-1-k)!}}+{\frac {(n-1)!}{(k-1)!(n-k)!}}\\&=(n-1)!\left[{\frac {n-k}{k!(n-k)!}}+{\frac {k}{k!(n-k)!}}\right]\\&=(n-1)!{\frac {n}{k!(n-k)!}}\\&={\frac {n!}{k!(n-k)!}}\\&={\binom {n}{k}}\end{aligned}}}$$

さらに、二項係数が${\displaystyle {\tbinom {n}{k}}={\frac {n(n-1)\cdots (n-k+1)}{k!}}}$によって定義されている場合であっても、同様の証明が可能である:

$${\displaystyle {\begin{aligned}{n-1 \choose k}+{n-1 \choose k-1}&={\frac {(n-1)\cdots ((n-1)-k+1)}{k!}}+{\frac {(n-1)\cdots ((n-1)-(k-1)+1)}{(k-1)!}}\\&={\frac {(n-1)\cdots (n-k)}{k!}}+{\frac {(n-1)\cdots (n-k+1)}{(k-1)!}}\\&={\frac {(n-1)\cdots (n-k+1)}{(k-1)!}}\left[{\frac {n-k}{k}}+1\right]\\&={\frac {(n-1)\cdots (n-k+1)}{(k-1)!}}\cdot {\frac {n}{k}}\\&={\frac {n(n-1)\cdots (n-k+1)}{k!}}\\&={\binom {n}{k}}\end{aligned}}}$$

${\displaystyle {\tbinom {z}{k}}={\frac {z(z-1)\cdots (z-k+1)}{k!}}}$ という定義は ${\displaystyle z}$ を複素数とする場合の拡張で利用される。したがって、この証明法はパスカルの法則が ${\displaystyle n}$ を一般の任意の複素数へと読みかえても成立することを示している。

パスカルの法則を、多項係数に対して拡張することができる^[2](p144)。 ${\displaystyle p\geq 2}$ なる整数 ${\displaystyle p}$ と、${\displaystyle k_{1},k_{2},k_{3},\dots ,k_{p}\in \mathbb {Z} ^{+}\!,n=k_{1}+\cdots +k_{p}\geq 1}$に対して、

${\displaystyle {n-1 \choose k_{1}-1,k_{2},k_{3},\dots ,k_{p}}+{n-1 \choose k_{1},k_{2}-1,k_{3},\dots ,k_{p}}+\cdots +{n-1 \choose k_{1},k_{2},k_{3},\dots ,k_{p}-1}={n \choose k_{1},k_{2},k_{3},\dots ,k_{p}}}$

が成立する。ただし、多項係数 ${\displaystyle {n \choose k_{1},k_{2},k_{3},\dots ,k_{p}}}$ は、${\displaystyle (x_{1}+x_{2}+\dots +x_{p})^{n}}$を展開した際の ${\displaystyle x_{1}^{k_{1}}x_{2}^{k_{2}}\cdots x_{p}^{k_{p}}}$ 項の係数として定義されるものとする。

この一般化されたパスカルの法則も、代数的に示すことができる^[2](p144): $${\displaystyle {\begin{aligned}&{}\quad {n-1 \choose k_{1}-1,k_{2},k_{3},\dots ,k_{p}}+{n-1 \choose k_{1},k_{2}-1,k_{3},\dots ,k_{p}}+\cdots +{n-1 \choose k_{1},k_{2},k_{3},\dots ,k_{p}-1}\\&={\frac {(n-1)!}{(k_{1}-1)!k_{2}!k_{3}!\cdots k_{p}!}}+{\frac {(n-1)!}{k_{1}!(k_{2}-1)!k_{3}!\cdots k_{p}!}}+\cdots +{\frac {(n-1)!}{k_{1}!k_{2}!k_{3}!\cdots (k_{p}-1)!}}\\&={\frac {k_{1}(n-1)!}{k_{1}!k_{2}!k_{3}!\cdots k_{p}!}}+{\frac {k_{2}(n-1)!}{k_{1}!k_{2}!k_{3}!\cdots k_{p}!}}+\cdots +{\frac {k_{p}(n-1)!}{k_{1}!k_{2}!k_{3}!\cdots k_{p}!}}={\frac {(k_{1}+k_{2}+\cdots +k_{p})(n-1)!}{k_{1}!k_{2}!k_{3}!\cdots k_{p}!}}\\&={\frac {n(n-1)!}{k_{1}!k_{2}!k_{3}!\cdots k_{p}!}}\\&={\frac {n!}{k_{1}!k_{2}!k_{3}!\cdots k_{p}!}}={n \choose k_{1},k_{2},k_{3},\dots ,k_{p}}.\end{aligned}}}$$

• パスカルの三角形
• ホッケースティック恒等式