パスカルの三角形による二項係数(nCk)の計算

数学二項係数, 動的計画法, パスカルの三角形

以下のような「上の2つを足して下の数字をつくる三角形」をパスカルの三角形といい、上から \(n\) 行目・左から \(k\) 個目の数は、\(_{n}\mathrm{C}_{k}\) に対応しています。(0-indexed)

\begin{gather}
1 \\
1 ~~~~ 1 \\
1 ~~~~ 2 ~~~~ 1 \\
1 ~~~~ 3 ~~~~ 3 ~~~~ 1 \\
1 ~~~~4 ~~~~ 6 ~~~~ 4 ~~~~ 1 \\
1 ~~~~ 5 ~~~~ 10 ~~~~ 10 ~~~~ 5 ~~~~ 1
\end{gather}

\begin{gather}
_{0}\mathrm{C}_{0} \\
_{1}\mathrm{C}_{0} ~~ _{1}\mathrm{C}_{1} \\
_{2}\mathrm{C}_{0} ~~ _{2}\mathrm{C}_{1} ~~ _{2}\mathrm{C}_{2} \\
_{3}\mathrm{C}_{0} ~~ _{3}\mathrm{C}_{1} ~~ _{3}\mathrm{C}_{2} ~~ _{3}\mathrm{C}_{3}\\
_{4}\mathrm{C}_{0} ~~ _{4}\mathrm{C}_{1} ~~ _{4}\mathrm{C}_{2} ~~ _{4}\mathrm{C}_{3} ~~ _{4}\mathrm{C}_{4} \\
_{5}\mathrm{C}_{0} ~~ _{5}\mathrm{C}_{1} ~~ _{5}\mathrm{C}_{2} ~~ _{5}\mathrm{C}_{3} ~~ _{5}\mathrm{C}_{4} ~~ _{5}\mathrm{C}_{5}
\end{gather}

これを利用することで、二項係数を求めることが可能です。上図から、
$$ {}_{i}\mathrm{C}_{j} = {}_{i-1}\mathrm{C}_{j-1}+{}_{i-1}\mathrm{C}_{j} $$
が成立していることが見て取れます。(例えば \({}_{5}\mathrm{C}_{3} = {}_{4}\mathrm{C}_{2}+{}_{4}\mathrm{C}_{3} \) です。)

アルゴリズム

パスカルの三角形による二項係数の計算:

  • 前処理(パスカルの三角形をつくる):
    1. \({}_{i}\mathrm{C}_{j} = {}_{i-1}\mathrm{C}_{j-1}+{}_{i-1}\mathrm{C}_{j} \) を利用して計算(動的計画法)
  • クエリ(\(_{n}\mathrm{C}_{k}\)を求める):
    1. 前処理で計算した値を利用

※ 前処理での \({}_{i}\mathrm{C}_{j} = {}_{i-1}\mathrm{C}_{j-1}+{}_{i-1}\mathrm{C}_{j} \) は二項係数の有名公式ですし、パスカルの三角形の作り方からも分かります。

※ \({}_{i}\mathrm{C}_{j} = {}_{i-1}\mathrm{C}_{j-1}+{}_{i-1}\mathrm{C}_{j} \) は意味を考えると成立していることが分かります。左辺の意味は「\(i\) 個の中から \(j\) 個選ぶ」で、右辺の意味は「 あるものを1つ入れると決めた時は、残りの \(i-1\) の中から \(j-1\) 個選ぶ。入れないと決めた時は、残りの \(i-1\) の中から \(j\) 個選ぶ」ということを表しています。左辺と右辺は同じ場合の数です。

※ 二項係数は n が大きく k が n/2 に近い時に非常に大きな値になります。固定長の整数型では容易にオーバーフローしてしまう可能性があるので注意してください。(具体的には、\(_{50}\mathrm{C}_{25}\) は約 \(10^{14}\) ほどになり、32bit の整数型では収まりません。64bit 必要になります。)

※ 競技プログラミングなどでは、二項係数を素数で割った余りを求めさせる問題が多いです。求め方はこちらを参照してください。

計算量

  • 前処理:\(O(n^2)\)
  • クエリ:\(O(1)\)

C++ での実装例

標準入力から n と k を受け取って、nCk を返すプログラムです。