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

数学 C++ Python

「数学ガール」はもう返してしまったので、あまり正確に覚えていないが、最後の章で分割数を取り上げていた。テトラは自力で数え上げたが、我々にはプログラミングがある。
分割数は、例えば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;

}