C++で二項係数の2乗の総和を求める方法を解説

二項係数とは

二項係数とは、二項定理に現れる係数で、パスカルの三角形として表現できる数の並びです。n個の要素からr個を選ぶ組み合わせの総数に相当し、nCrと表記されます。定義は以下の公式のとおりです。

nCr = n! / (r!(n-r)!)
または
nCr = n(n-1)(n-2)…(n-r+1) / r!

二項係数の2乗の総和

本記事で扱うのは、二項係数をそれぞれ2乗した値の総和です。具体的には次の式を計算します。

(_nC₀)² + (_nC₁)² + (_nC₂)² + (_nC₃)² + …… + (_nC_n-1)² + (_nC_n)²

入力 : n = 5
出力 : 252

アルゴリズムの解説

このプログラムでは、まずn個の集合からr個を選ぶ場合の二項係数を求め、それぞれの係数を2乗して順に加算していきます。実装のアプローチとしては、階乗を計算する関数を用意し、引数としてnとrを渡して各二項係数を求め、その2乗を合計変数に足し込む方法がシンプルで分かりやすいでしょう。

サンプルコード

#include <iostream>
using namespace std;
int fact(int n){
    int fact = 1, i;
    for (i = 2; i <= n; i++){
        fact *= i;
    }
    return fact;
}
int main(){
    int n = 5;
    int sum = 0;
    int temp = 0;
    for (int r = 0; r <= n; r++){
        temp = fact(n) / (fact(r) * fact(n - r));
        sum += (temp * temp);
    }
    cout << sum;
    return 0;
}

出力

252

補足: ヴァンデルモンドの恒等式による高速化

実は、二項係数の2乗の総和には次のような美しい閉じた公式が成り立ちます。

Σ (nCr)² = (2n)! / (n!)² = 2nCn

これはヴァンデルモンドの恒等式として知られる性質です。n = 5 の場合、10C5 = 252 となり、先ほどのプログラムの出力と一致します。この公式を使えば、ループで各項を計算する必要がなく、O(n) の階乗計算だけで結果を得られるため、より効率的な実装が可能です。