C++で偶数番目の二項係数の合計を求める方法

整数 n が与えられたとき、二項係数のうち偶数番目（インデックス 0, 2, 4, …）の項だけを取り出して、その合計を求める問題を考えます。

数式で表すと次のようになります。

$$\binom{n}{0}+\binom{n}{2}+\binom{n}{4}+\binom{n}{6}+\cdots$$

例として n = 4 の場合を計算してみましょう。

$$\binom{4}{0}+\binom{4}{2}+\binom{4}{4}=1+6+1=8$$

知っておくと便利な数学的性質

実は、偶数番目の二項係数の合計は常に 2^n-1 と等しくなることが二項定理から導けます。(1+1)ⁿ = 2ⁿ はすべての二項係数の合計に相当し、(1−1)ⁿ = 0 は偶数番目と奇数番目の項の差に相当します。したがって、偶数番目と奇数番目の合計は等しくなり、それぞれ 2ⁿ の半分、すなわち 2^n-1 となります。

パスカルの三角形を使った実装

ここでは、動的計画法（DP）でパスカルの三角形を構築し、n 行目の偶数番目の値を合計する方法を紹介します。手順は次のとおりです。

1. 二次元配列にパスカルの三角形を構築する
2. n 行目の偶数番目（0, 2, 4, …）の要素を合計する

C++コード例

#include <iostream>
using namespace std;

int evenIndexedTermSum(int n) {
    int coeff[n + 1][n + 1];
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= min(i, n); j++) {
            if (j == 0 || j == i)
                coeff[i][j] = 1;
            else
                coeff[i][j] = coeff[i - 1][j - 1] + coeff[i - 1][j];
        }
    }
    int sum = 0;
    for (int i = 0; i <= n; i += 2)
        sum += coeff[n][i];
    return sum;
}

int main() {
    int n = 8;
    cout << "Sum of even placed binomial coefficients: " << evenIndexedTermSum(n);
}

出力結果

Sum of even placed binomial coefficients: 128

コードの解説

evenIndexedTermSum 関数では、まず (n+1)×(n+1) の二次元配列 coeff を用意し、パスカルの三角形の値を順に格納していきます。各行の両端（j == 0 または j == i）は 1 とし、それ以外の値は「左上の値 + 右上の値」として計算します。

三角形の構築後、n 行目の要素を 2 つ飛ばし（i += 2）で走査し、偶数番目の要素のみを合計変数 sum に加算して返します。

この実装の計算量は O(n²) ですが、前述の数学的性質を利用すれば、2^n-1 を計算するだけで答えが得られます。たとえば n = 8 の場合、2⁷ = 128 となり、プログラムの出力と一致します。