母関数を使って分割数を求める

　iのj分割をa[i][j]として、a[i][j] = a[i][j-1] + a[i-j][j]という漸化式を解けばnの分割数（a[n][n]）を計算できる。
　他にもいくつか計算方法があるようで、母関数を使った計算方法がおもしろそうだったので調べてみた。

母関数を使った分割数の計算

例えば5の分割数を計算することを考える。

f(x) = (1 + x + x² + x³ + x⁴ + x⁵) (1 + x² + x⁴) (1 + x³)(1 + x⁴) (1 + x⁵)

とし、右辺を展開すると、

f(x) = 1 + x + 2x² + 3x³ + 5x⁴ + 7x⁵  ....

となる。このとき、x⁵の係数7が5の分割数となる。
一般に、

f(x) = ∏_{k=1}^{∞} ∑_{i=0}^{∞} x^{ki}

として、x^kの係数を求めると、それがkの分割数となる[1]。

プログラム

100未満の数の分割数を求めるプログラムを書いてみた。O(n³)で遅い。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 100;

vector<int> mul(vector<int> p, vector<int> x) {
    vector<int> ret(N);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j + i < N; j++) {
            ret[i + j] += p[i] * x[j];
        }
    }
    return ret;
}

int main(int argc, char **argv) {
    
    vector<int> p(N);
    p[0] = 1;

    for (int i = 1; i < N; i++) {
        vector<int> x(N);
        
        for (int j = 0; j < N; j += i)
            x[j] = 1;

        p = mul(p, x);
    }

    for_each(p.begin(), p.end(), [](int x) { cout << x << endl; });

    return 0;
}

参考

[1] Partitions of Integers