C++で前半と後半のビット合計が等しい偶数長バイナリ列の個数を求める方法

問題概要

バイナリ列(0と1からなる数列)に対して、その半分の長さにあたるビット数 n が入力として与えられます。求めたいのは、前半 n ビットの合計(1の個数)と後半 n ビットの合計が一致する、長さ 2n のバイナリ列の総数です。

バイナリ列なので、各位置に入れられる値は 0 か 1 のみです。まず、n ビットの中に含まれる 1 の個数ごとの組み合わせ数を整理してみましょう。

• 1 が 0 個:nC0 = 1 通り
• 1 が 1 個:nC1 通り
• 1 が 2 個:nC2 通り
• ……
• 1 が n 個:nCn 通り

次に、長さ 2n の列全体を考えます。前半と後半で合計が一致するためには、両方の半分で同じ個数の 1 を選べばよいので、組み合わせは次のように積の形で表せます。

• 前半に 1 が 0 個・後半に 1 が 0 個:nC0 × nC0
• 前半に 1 が 1 個・後半に 1 が 1 個:nC1 × nC1
• 前半に 1 が 2 個・後半に 1 が 2 個:nC2 × nC2
• ……
• 前半に 1 が n 個・後半に 1 が n 個:nCn × nCn

したがって、条件を満たすバイナリ列の総数は次の式で表されます。

nC0×nC0 + nC1×nC1 + … + nCn×nCn =(nC0)² +(nC1)² + … +(nCn)²

なお、数学的にはこの二項係数の二乗和は恒等式 Σ(nCk)² = ₂ₙCₙ と等しいことが知られているため、中央の二項係数を直接計算することでも同じ答えが得られます。

入力例と出力例

入力例 1

n=1

出力例 1

Sequences with same sum of first and second half bits: 2

解説: 長さ 2×1=2 のバイナリ列は 00、01、10、11 の4通り存在します。このうち、前半と後半の合計がどちらも 1 で一致しているのは 01 と 10 の2通りです。

入力例 2

n=2

出力例 2

Sequences with same sum of first and second half bits: 6

解説: 長さ 2×2=4 のバイナリ列は 0000 から 1111 までの16通り存在します。このうち、前半2ビットと後半2ビットの合計が一致するのは以下の6通りです。

0000、0101、0110、1001、1010、1111 → 合計 6 通り

アルゴリズムの考え方

• 整数 bits にビット数 n を格納します。
• 関数 findSeq(int n) は n を引数に取り、条件を満たす長さ 2n のバイナリ列の個数を返します。
• 変数 nCi は二項係数を保持し、初期値は nC0 = 1 です。
• 答えを格納する ans を 1 で初期化します(nC0×nC0 = 1 の分に相当)。
• i = 1 から n までループし、漸化式 nCi = nC(i-1) × (n+1-i) / i を使って各二項係数を順に計算しながら、nCi × nCi を ans に加算していきます。
• ループ終了後、ans の値を結果として返します。

この手法により、階乗を直接計算することなくオーバーフローのリスクを抑えつつ、時間計算量 O(n) で効率的に答えを求められます。

C++による実装例

#include<iostream>
using namespace std;

// 条件を満たす偶数長バイナリ列の個数を返す
int findSeq(int n){
    int nCi = 1; // nC0 = 1
    int ans = 1;
    for (int i = 1; i <= n; i++){
        // 漸化式:nCi / nC(i-1) = (n+1-i) / i
        nCi = (nCi * (n+1-i)) / i;
        ans += nCi * nCi;
    }
    return ans;
}

int main(){
    int bits = 2;
    cout << "Count of binary sequences such that sum of first and second half bits is same: " << findSeq(bits);
    return 0;
}

実行結果

Count of binary sequences such that sum of first and second half bits is same: 6

まとめ

本記事では、前半 n ビットと後半 n ビットの合計が等しい長さ 2n のバイナリ列の個数を、二項係数の二乗和 Σ(nCk)² として定式化し、漸化式を用いた O(n) の C++ 実装で求める方法を解説しました。組合せ論の恒等式 ₂ₙCₙ との関係を理解しておくと、より深い考察にも役立ちます。