C++で方程式 x1 + x2 + … + xn = k の整数解の個数を求める方法

この記事では、方程式 x₁ + x₂ + … + xₙ = k を満たす整数解の個数を求める問題を取り上げます。組み合わせの公式を活用することで、すべての解を列挙することなく効率的に計算できます。

解の個数を求める公式

方程式の整数解は、次の2種類に分けて数えることができます。

• 非負整数解（0 以上の整数）の個数：C(n + k − 1, k)
• 正の整数解（1 以上の整数）の個数：C(k − 1, n − 1)

非負整数解の個数は「重複組合せ」（仕切りと玉の並べ方）の考え方から導かれます。また、正の整数解の個数は、各変数にあらかじめ 1 を割り当て、残りの k − n を自由に分配する場合の数として求まります。この2つを足し合わせたものが、求める答えになります。

具体例

入力

n = 4
k = 7

出力

140

n = 4、k = 7 の場合を見てみましょう。非負整数解の個数は C(10, 7) = 120、正の整数解の個数は C(6, 3) = 20 となります。したがって、合計は 120 + 20 = 140 です。

アルゴリズム

• 変数 n と k を初期化します。
• 非負整数解と正の整数解の個数を、それぞれ二項係数として計算します。
• 両者を加算します。
• 答えを出力して終了します。

C++ による実装

以下は、上記のアルゴリズムを C++ で実装した例です。階乗と二項係数を求める補助関数を用意しています。

#include <bits/stdc++.h>
using namespace std;

// 階乗を計算する関数
int factorial(int n) {
    int product = 1;
    for (int i = 2; i <= n; i++) {
        product *= i;
    }
    return product;
}

// 二項係数 nCr を計算する関数
int nCr(int n, int r) {
    return factorial(n) / (factorial(n - r) * factorial(r));
}

int main() {
    int n = 4;
    int k = 7;
    // 非負整数解の個数と正の整数解の個数の和を出力
    cout << nCr(n + k - 1, k) + nCr(k - 1, n - 1) << endl;
    return 0;
}

実行結果

上記のコードを実行すると、次の出力が得られます。

140