メタプログラミングで分割数を求める

数学ガール」はもう返してしまったので、あまり正確に覚えていないが、最後の章で分割数を取り上げていた。テトラは自力で数え上げたが、我々にはプログラミングがある。
分割数は、例えば3を自然数で分割すると、


[ 3 ], [ 2, 1 ], [ 1, 1, 1 ]

の3通りあるから、3の分割数は3。これを、


P3 = 3

と書くことにする。前にもやったように、分割を列挙するのは再帰で書けば簡単で、Pythonで書くと、


def divide(n):
if n == 0:
return [ ]

l = [ [ n ] ]
for i in range(n - 1, 0, -1):
for a in divide(n - i):
if a[0] <= i:
l.append([ i ] + a)
return l

print divide(3)

帰ってきたリストの大きさが分割数だから、それを拾えば、


P1 = 1
P2 = 2
P3 = 3
P4 = 5
P5 = 7
P6 = 11
...
P15 = 176
...

となる。
メタプログラミングとなると、何らかの漸化式がほしい。
このように考える。例えば、5を分割するとき、最初4だと1残っているから1の分割数が使える。最初3だと2残っているから2の分割数が使える。最初2だと3残っているが、3の分割数は使えない。最大で2だからである。
ここで、nをm以下で分割する場合の数をQn,mとすると、最大の数をnから順に考えていって、


Pn = 1 + Q1,n-1 + ... + Qn-1,1
Qn,1 = 1
Qn,m = Pn ( n <= m )
Qn,m = Qn-m,m + ... + Qn-1,1
= Qn-m,m + Qn,m-1 ( n > m )
Pn = 1 + Qn,n-1 ( n > 1)
P1 = 1

これをPythonでコード化すると、


def Q(n, m):
if m == 1:
return 1
elif n <= m:
return P(n)
else:
return Q(n - m, m) + Q(n, m - 1)

def P(n):
if n == 1:
return 1
else:
return 1 + Q(n, n - 1)

for n in range(1, 16):
print P(n)

これをC++でテンプレートを使って書いた。


#include

using namespace std;

template
struct Q {
enum { val = Qm)>::val + Q::val };
};

template
struct Q {
enum { val = P::val };
};

template
struct Q {
enum { val = 1 };
};

template
struct P {
enum { val = Q::val + 1 };
};

template<>
struct P<1> {
enum { val = 1 };
};

int main() {
cout << P<15>::val << endl;
}