C++でNを2つ以上の正の整数の和として表す方法の総数を求める

この記事では、「整数 N が与えられたとき、それを 2 つ以上の正の整数の和として表す方法が何通りあるか」を求める問題を取り上げます。

まず、具体例を使って問題を確認しましょう。

入力例

N = 4

出力例

5

説明

4 は次のように和で表せます。
4, 3+1, 2+2, 2+1+1, 1+1+1+1

※上記の答えには「4」そのものも含まれています。これは整数を順序を問わない和に分解する「分割（パーティション）」の総数、いわゆる分割数 p(n) と一致します。

アプローチ：オイラーの漸化式（五角数定理）

この問題は、整数 n の分割数 p(n) を求める問題に帰着できます。分割数を効率よく計算するには、オイラーが発見した漸化式を利用するのが有効です。

母関数を用いると、分割数は次の無限積で表されます。

Σ∞n=0 p(n)xn = Π∞k=1 1/(1−xk)

この式を展開すると、次のような漸化式が得られます。

p(n) = p(n−1) + p(n−2) − p(n−5) − p(n−7) + … + (−1)k−1·p(n − k(3k−1)/2)

ここで現れる 1, 2, 5, 7, 12, 15, … という数列は「一般化五角数」と呼ばれ、g_k = k(3k−1)/2（k = 1, −1, 2, −2, 3, −3, …）によって生成されます。符号は 2 項ごとに +, +, −, − と入れ替わる点に注意してください。

C++による実装例

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

long long positiveSum(int n){
    vector<long long> p(n + 1, 0);
    p[0] = 1;
    for (int i = 1; i <= n; ++i) {
        int k = 1;
        while ((k * (3 * k - 1)) / 2 <= i) {
            p[i] += (k % 2 ? 1 : -1) * p[i - (k * (3 * k - 1)) / 2];
            if (k > 0)
                k *= -1;
            else
                k = 1 - k;
        }
    }
    return p[n];
}

int main(){
    int N = 12;
    cout << N << " を 2 つ以上の正の整数の和として表す方法の数は "
         << positiveSum(N) << " 通りです";
    return 0;
}

出力

12 を 2 つ以上の正の整数の和として表す方法の数は 77 通りです

計算量

各 i について、内側のループは一般化五角数が i 以下である間だけ回るため、およそ O(√i) 回の処理が行われます。したがって、全体の時間計算量は O(n√n)、空間計算量は O(n) となります。全ての分解を実際に列挙する方法に比べて格段に高速で、n がある程度大きくなっても実用的に動作します。