パスカル三角形の計算方法(合計と差分)

パスカル三角形は数学上で大変有名です。三角形は内容は一階層ごとに二項式の係数になっています。下の層の係数は上の層の２個の近隣係数の合計です。例えば下のようなものです。

この例はいわば合計のパスカル三角形です。差分のパスカル三角形もあります。一層目は1と-1になるだけです。計算ルールは同じです。例えば下の物です。

詳しく見てみれば、左右から中間へ合計のパスカル三角形の近隣二項の差を取れば、ぴったりと差分のパスカル三角形になります。

パスカル三角形の内容は二項式計数なので、基本的に下記の有名な式で計算できます。

$$
\left( \begin{array}{c} n \\ k \end{array} \right)
=\frac{n!}{(n-k)!k!}
=\frac{n(n-1)(n-2) \ldots (n-k+1)}{k!}
$$

この計算法の問題点としては、分子と分母ともに２個の大きい数字ができてから割り算をします。結果はオーバーフローはより起こりやすいです。このため、パスカル三角形のような足し算だけで計算したほうが穏便です。もう一点では、一般に掛け算が足し算より遅いです。同様な計算回数であれば、一般に足し算の方が早く終わります。これはコンピュータも人間も同じのようです。

指定サイズ(SIZE)のパスカル三角形の最後の層は下記のようなコードで計算できます。