Page List

Search on the blog

2015年1月17日土曜日

2015年1月14日水曜日

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

 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 + x2 + x3 + x4 + x5) (1 + x2 + x4) (1 + x3)(1 + x4) (1 + x5)

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

f(x) = 1 + x + 2x2 + 3x3 + 5x4 + 7x ....

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

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

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

プログラム
100未満の数の分割数を求めるプログラムを書いてみた。O(n3)で遅い。
#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