パスカルの三角形を用いてコンビネーション(組み合わせ)のクラスを実装する

コンビネーション(組み合わせ)とは

nCk = n! / k! * (n - k)!

n個の中からk個取り出す場合の数を算出するものである。

パスカルの三角形とは

２項展開における係数を三角形状に並べたものである。

パスカルの三角形 - Wikipedia

それぞれの値はnCkの計算結果になっている。例えば5C3(n=5, k = 3)の場合は三角形の５段目の左から３番目の値が答えになっている。

コンビネーションのクラスを実装する

パスカルの三角形を作成する際、以下の漸化式が成り立つ。

dp[n][k] = dp[n-1][k-1] + dp[n-1][k]

これはパスカルの三角形の各要素は一段上の２つの要素の和になっていることから成り立つ。 この性質を利用し、動的計画法を行うことでO(n²)で三角形を作る事ができる。

以下は上記のコードを実行した時のコンソールの様子である。