オイラーの分割恒等式をPythonで求める

オイラーの分割恒等式を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だけというのも含まれmなおかつ (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)のように、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文の中で再帰関数を使うのは珍しいです。

この記事を書いた人

目次
閉じる