オイラーの分割恒等式をPythonで求めます。
単純な自然数の分割（the number of partitions）
まずに単純な自然数の分割についてです。
ある自然数を自然数の和で表します。このとき、その自然数自身も含み、足す順番は大きいものから小さいものへ並べるようにします。例えば5であれば次のように、7つが考えられます。
5==> (5,),(4,1),(3,2),(3,1,1),(2,2,1),(2,1,1,1),(1,1,1,1,1)
5だけというのも含まれｍなおかつ （1,1,3)のように右側が大きくなるものは含まれません。さて、この組み合わせの数を、自然数1から49まで並べると次の通りです。
1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490, 627, 792, 1002, 1255, 1575, 1958, 2436, 3010, 3718, 4565, 5604, 6842, 8349, 10143, 12310, 14883, 17977, 21637, 26015, 31185, 37338, 44583, 53174, 63261, 75175, 89134, 105558, 124754, 147273, 173525 出展 The On-Line Encyclopedia of Integer Sequences A000041
とりあえず、Pythonで1から7まで求めるようにしました。配列は3次元になっており、l1のリストの中で、l2には各自然数の中での組み合わせの1つ1つがl3のリストとして含まれるようにします。
l1=[]
num=8
for i in range(1,num):
l2=[]
l2.append([i])
for j in range (1,i):
for k in (l1[j-1]):
if k[0]<=i-j:
l2.append([(i-j)]+k)
l1.append(l2)
l1 [[[1]],
[[2], [1, 1]],
[[3], [2, 1], [1, 1, 1]],
[[4], [3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]],
[[5], [4, 1], [3, 2], [3, 1, 1], [2, 2, 1], [2, 1, 1, 1], [1, 1, 1, 1, 1]],
[[6],
[5, 1],
[4, 2],
[4, 1, 1],
[3, 3],
[3, 2, 1],
[3, 1, 1, 1],
[2, 2, 2],
[2, 2, 1, 1],
[2, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1]],
[[7],
[6, 1],
[5, 2],
[5, 1, 1],
[4, 3],
[4, 2, 1],
[4, 1, 1, 1],
[3, 3, 1],
[3, 2, 2],
[3, 2, 1, 1],
[3, 1, 1, 1, 1],
[2, 2, 2, 1],
[2, 2, 1, 1, 1],
[2, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1]]]ちなみに55まで求めてリストの要素の数を出力すると次の通りで、正しく計算されているようです。まだまだ粗いプログラムなので、ゆくゆくは再帰関数を使って求めてみたいと思います。
1,2,3,5,7,11,15,22,30,42,56,77,101,135,176,231,297,385,490,627,792,1002,1255,1575,1958,2436,3010,3718,4565,5604,6842,8349,10143,12310,14883,17977,21637,26015,31185,37338,44583,53174,63261,75175,89134,105558,124754,147273,173525,204226,239943,281589,329931,386155これだけなら何も面白くありませんが、ここで求めた数列にはすごい性質があります。
異分割（distinct partition）
前に求めた数列から、同じ数字が含まれるものを除きます。前の5を例にとると(3,1,1)や(1,1,1,1,1)などは、1が複数含まれるので、このような組合せは含まれないようにします。結果残りは、次の3つになります。
5==> (5,),(4,1),(3,2)前に求めた分割の配列l1から次のプログラムで重複するものを除いて、リストd1に追加していきます。
d1=[]
for i in l1:
d2=[]
for k in i:
prev=0
for l in k:
if prev==0:
prev=l
else:
if prev==l:
break
else:
prev=l
else:
d2.append(k)
d1.append(d2)
d1 [[[1]],
[[2]],
[[3], [2, 1]],
[[4], [3, 1]],
[[5], [4, 1], [3, 2]],
[[6], [5, 1], [4, 2], [3, 2, 1]],
[[7], [6, 1], [5, 2], [4, 3], [4, 2, 1]]]後で検証しますが、7まで計算したところでは問題なさそうです。
奇分割（odd partotion）
次に、初めに求めた数列から、奇数のみを使ったものだけを取り出します。例えば5を例にすると(4,1),(2,2,1)のように、１つでも偶数が入っているものは取り除きます。結果は次の通りです。
(5,),(3, 1, 1),(1, 1, 1, 1, 1)Pythonでプログラムを作ってみます。
o1=[]
for i in l1:
o2=[]
for k in i:
for l in k:
if l%2==0:
break
else:
o2.append(k)
o1.append(o2)
o1 [[[1]],
[[1, 1]],
[[3], [1, 1, 1]],
[[3, 1], [1, 1, 1, 1]],
[[5], [3, 1, 1], [1, 1, 1, 1, 1]],
[[5, 1], [3, 3], [3, 1, 1, 1], [1, 1, 1, 1, 1, 1]],
[[7], [5, 1, 1], [3, 3, 1], [3, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1]]]
こちらも7までは問題なさそうです。
異分割と奇分割の関係
ここでようやく、面白いことがわかります。両者の数を55まで求めると次のように一致するのです。
1,1,2,2,3,4,5,6,8,10,12,15,18,22,27,32,38,46,54,64,76,89,104,122,142,165,192,222,256,296,340,390,448,512,585,668,760,864,982,1113,1260,1426,1610,1816,2048,2304,2590,2910,3264,3658,4097,4582,5120,5718
この数列もThe On-Line Encyclopedia of Integer Sequences A000009
単純な自然数の分割（the number of partitions）
最後に再帰関数で単純な分割する関数を作ってみました。考え方は同じです。
def partition(num):
l=[]
l.append([num])
for i in range(1,num):
for j in p(i):
if j[0]<=num-i:
l.append([(num-i)]+j)
return l
p(5)[[5], [4, 1], [3, 2], [3, 1, 1], [2, 2, 1], [2, 1, 1, 1], [1, 1, 1, 1, 1]]
思ったより簡単でした。for文の中で再帰関数を使うのは珍しいです。
