分割数を写像から考える

補助関数の導入

補助関数の意味と種類

補助関数の考え方

p(n)のように直接計算するのが難しい時には、計算しやすくするための補助関数(auxiliary function)という別の関数を使う手があります。

補助関数の1つの例としてp(n)を和因子の個数kで分類し、p(n ,k)とする方法があります。補助関数p(n, k)で個数を計算したのち、本丸のp(n)を落としに行く作戦です。例えばn=6、k=3の場合、(4, 1, 1)、(3, 2, 1)、(2, 2, 2)の3つの分割があります。分割の補助関数の値はSymPyライブラリのnT関数を使って計算することができます。

SymPyライブラリのnT関数で分割数の補助関数を計算する

from sympy.functions.combinatorial.numbers import nT
partition_count = nT(6, 3)
partition_count

1.　 nT関数はSympyライブラリのsympy.functions.combinatorial.numbers サブモジュールからimportします。

SymPyライブラリからnT関数をimportします。

上記の3つの分割を正しく計算できています。

補助関数の大体の感覚をつかむため、nT関数を使いn=10、k=10までの一覧表を作成します。配列arrayに分割数を代入し、print_table関数を使い出力します。print_table関数は配列と、表の列の幅を引数として、arrayの値と行の合計を表示します。

nT関数を使い、補助関数の一覧表を作成する

def print_table(array, w):
print(f' ' * (w+2), end='')
for k in range(len(array[0])):
print(f'{k:^{w+2}}', end=' ')
print('sigma')
print(f'-' * (w+1), end='+')
for k in range(len(array)+1):
print('-' * (w+2), end='+')
print()
for n in range(len(array)):
print(f'{n:^{w+1}}', end='|')
sigma = 0
for k in range(len(array[0])):
print(f"{array[n][k]:>{w+2}}", end=' ')
sigma += array[n][k]
print(f"{sigma:>{w+2}}")
n=10;k=10
array = [[0]*(k+1) for _ in range(n+1)]
for i in range(1,n+1):
for j in range(1,k+1):
array[i][j]=int(nT(i,j))
print_table(array, 3)

  次のような表になります。

2.　print関数でendを指定すると、その文字列が行末に表示されますが改行はしません。

この表を見ると、次のことがうかがえます。

n
k=1のときはnが大きくても、nが1つの分割にしか分けられないので1
n=kの場合はn個の1が和因子になる分割が1つしか考えられないので1

さらに表を眺めながら補助関数p(n ,k)の正体を探っていきます。

補助関数の漸化式

p(n, k)を直接求めるのは難しいので、漸化式を考えます。例えば、p(9, 3)の分割数は図の通り7になります。このうち最小（最右端）の要素が1かどうかで、2つの集合、集合$X_1$、集合$X_2$に分類します。

集合$X_1$ 9の分割で和因子数3 最小和因子が1

集合$X_2$ 9の分割で和因子数3最小和因子が1以外

8の分割で和因子数2、つまりp(8, 2)の分割を集合Yとし、集合$X_1$との対応を考えます。集合$X_1$の最小和因子（右端）にある1を削除すると合計と和因子数が1ずつ減るので、集合Yに対応します。一方、集合Yの右端に1を追加すると、合計と和因子数が1ずつ減るので$X_1$に対応します。つまり、両者は逆写像を持ち、全単射（一対一対応）になります。一般化すると、P(n, k)のうち最小和因子が1=p(n-1, k-1)となります。

次に6の分割で和因子数3、つまりp(6, 3)の分割を集合Zとし、集合$X_2$との対応を考えます。集合$X_2$の3つの和因子からそれぞれ1ずつを差し引くと、最小和因子（右端）が2以上なので和因子数は3のままで、合計は引いて6になるので集合Zと対応します。一方、集合Zの3つの和因子に1ずつを加えると、和因子数は3のままで合計は9になり$X_2$に対応します。つまり、両者は逆写像を持ち、全単射（一対一対応）になります。一般化するとP(n, k)のうち最小和因子が2以上=p(n-k, k)となります。

まとめる次のような漸化式になります。

補助関数(p,k)を使った分割式の漸化式

k=1 またはn=kのとき　1

$p (n, k)= p(n-1, k-1) + p(n-k, k)$

さっそく漸化式を使い補助関数の個数を求めるプログラムを作成します。漸化式を再帰関数に落とし込むだけです。

漸化式による計算

def partition_r(n, k):
if n < k:
return 0
if k == 1 or n == k:
return 1
return partion_r(n-1, k-1) + partion_r(n-k, k)
partion_r(6, 3)

6.　n=6、k=3を引数として実行すると、n=5、k=2としてさらに関数partition_rを呼び出し優先して実行します。さらにn=4,k=1としてさらに同じ関数が実行されます。

5.　n=4,k=1として関数partition_rを呼び出すと1を返します。この流れを繰り返すと最終的に分割数3が返り値となります。

こんな簡単なプログラムでp(n, k)を計算することができます。

漸化式を使って分割を生成する

さらに、次の漸化式を用いるとp(n, k)の一覧を生成することも可能です。こちらもp(k-1, n-1) 、p(n-k, k)を同じ関数で生成、これに漸化式の処理を加えるようにしています。

漸化式を使って補助関数の分割数を生成する

def pn_list_func(n, k):
if n < k:
return []
if k==1:
return [[n]]
array = []
for elm in pn_list_func(n-1, k-1):
array.append(elm+[1])
for elm in pn_list_func(n-k, k):
array.append([item+1 for item in elm])
return array
pn_list=pn_list_func(9, 3)
pn_list

[[7, 1, 1], [6, 2, 1], [5, 3, 1], [4, 4, 1], [5, 2, 2], [4, 3, 2], [3, 3, 3]]

7.　p(n-1, k-1)の戻り値を１つ1つelmに代入し、右側に1を付け足すことで①の処理ができます。

9.　p(n-k, k) の戻り値を１つ1つelmに代入し、elmの各要素に1を加える処理をしています。

一見すると、なぜ、こんなプログラムで分割を生成することができるのか不思議な感じがしますが、よくプログラムを見ると補助関数による漸化式を素直に反映してくれています。

最大の和因子がKである補助関数を作成する

もう一つの補助関数

補助関数には別の視点で捉えるものとして組み合わせの最大値で分類する方法があり、ここではq(n, k)とします。

n
k=1のときはk個の和因子全ての和因子が1の分割が1つしか考えられないので1
n=kの場合は和因子がkのみの分割が1つしか考えられないので1

q(9 , 3)は和因子の最大値が3で左端に来るもので、図の通り7個あります。これも、前と同じように分けて考えます。

集合$X_1$ 9の分割で最大和因子が3、 2番目に大きな和因子（左から2番目）が3より小さい

集合$X_2$ 9の分割で最大和因子が3、 2番目に大きな和因子（左から2番目）も3

8の分割で最大和因子2、つまりq(8, 2)の分割を集合Yとし、集合$X_1$と対応させます。集合$X_1$の左端にある最大和因子から1を差し引いて2にしても2番目が2以下なので分割として扱うことができ、対応付けることができます。集合Yの左端に1を加えると$X_1$に対応するので、両者は逆写像を持ち、全単射（一対一対応）になります。

6の分割で最大和因が3、つまりq(6, 3)の分割を集合Zとし、集合$X_2$と対応させます。集合$X_2$の左端の和因子を削除しても2番目も３なので、最大の和因子は3のままで集合Zと対応します。一方、集合Zの左端に最大和因子として3を付け加えると$X_2$に対応するので、両者は逆写像を持ち、全単射（一対一対応）になります。

①2番目に大きな和因子（左から2番目）が1番目より小さな分割　

②2番目に大きな和因子（左から2番目）が1番目と同じ分割

①は左端の和因子から1を差し引きます。結果として左端の和因子が2番目の和因子より小さくなることはないのでq(8, 2)と1対1の対応になります。逆にq(8,2)の左端に1を加えると①になり、全単射（1対1の対応）になります。

一方②は左端から1を引いても2番目が3なので降順であるという分割のルールに違反します。そこで、左端の最大値の3の和因子を削除します。②は2番目の和因子も１番目と同じなので、合計は6となり、最大の和因子が3のまま6の分割になりq(6, 3)と全単射（1対1対応）になります。

上記の関係から、次の漸化式を導くことができます。

補助関数qkの漸化式

k=1 またはn=kのとき　1

$q (n, k)= q(n-1, k-1)+q(n-k, k) $

補助関数qkの漸化式

これはp(n, k)と全く同じ漸化式になります。個数を求めるだけであればpartition_r関数と同じになるのでそのまま流用できます。次に、分割数の生成も再帰関数を使うことができます。

漸化式を使って補助関数の分割数を生成する

def qn_list_func(n, k):
if n < k:
return []
if k==1:
return [[1] * n]
array = []
for elm in qn_list_func(n-1, k-1):
array.append([elm[0] + 1] + elm[1:])
for elm in qn_list_func(n-k, k):
array.append([k] + elm)
return array
qn_list = qn_list_func(9, 3)
qn_list

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

7～8. 　漸化式ｎ左側の部分$q(k-1, n-1) $を組み込んでいます。ここでは一番左側の和因子に1を足すことでq(k,n)の分割を生成しています。同じqn_list_func(n-1, k-1)を引数と変えて呼び出す再帰関数になっています。

9.～10.　漸化式の右側の部分$q(n-k, k)$を組み込んでいます。ここでは、全ての分割の一番左側にkを追加することで、q(k,n)の分割を生成しています。

個数による分類と最大値による分類の1対1対応

前項の漸化式を見るとp(n, k)とq(n, k)の個数が等しいことがわかりましたが、その理由を考えます。

例えばp(6,3)、つまり合計6、和因子数3の1つの例として(4, 2, 1)を取り上げます。この分割に対して、図のようｎ点線を軸に反転させるとq(6,3)つまり、合計は6のままで最大値が3となる(3, 2, 1, 1)の分割になります。さらに、(3, 2, 1, 1)をもう一度反転させると(4, 2, 1)に戻ります。つまり1対1の対応になります。結局p(n, k)とq(n, k)は同じものを見る方向を変えただけということになります。このような関係を共役な分割(partition conjugate）といいます。

要素数が3の組み合わせ(4,2,1)を最大値が3の組み合わせ(3,2,1,1)に変換する関数を作成します。関数名は共役の英語表記からconjugate_funcとし、引数として分割をリストで渡します。戻り値として共役の分割がリストで返ります。ここでは(4,2,1)を例にして考えます。

p(n,k)からq(n,k)への変換

def conjugate_func(elm):
conjugate_elm = [0] * elm[0]
for item in elm:
for i in range(item):
conjugate_elm[i] += 1
return conjugate_elm
pn=[4, 2, 1]
qn=[3, 2, 1, 1]
print(conjugate_func(pn))
print(conjugate_func(qn))

(3, 2, 1, 1)
(4, 2, 1)

2.　最大の和因子は引数elmの0番目の値（例の場合は4）なので、はじめにその長さのリストを定義し、全て0で初期化します。

3.～4. elmの要素を1つ1つ読み込み、その値の個数だけconjugate_elmの値をカウントアップします。例えば、値が4であればインデックスが0から3の4つ、次の2であれば、0から1までの2つの項目に1を足します。

このことにより、最大値が4のリストを生成することができます。また、この逆の変換をすると元に戻ります。同じ関数を使いp(n,k)とq(n,k)を相互に変換させることができます。このような対応を対合写像（たいごう、ついごうinvolution）といいます。

ここで#12で生成したp(n)の分割にconjugate関数を適用した結果と、#13で生成したq(n)のを比較します。

p(n,k)からq(n,k)への変換の確認

conjugate_p = []
for elm in pn_list:
conjugate_p.append(conjugate_func(elm))
print(qn_list == conjugate_p)
conjugate_q = []
for elm in qn_list:
conjugate_q.append(conjugate_func(elm))
print(pn_list == conjugate_q)

True
True

2次元リストの比較は、単純に比較する場合、内側の要素がすべて正しくても並び順が異なると==演算子で比べた場合等しくなりません。この場合にはsorted関数で並べ替えないと正しい計算結果は得られません。ところが#15ではソートをしなくても等しいとの結果になりました。漸化式を使いpnとqnを生成するととると並び順も含めてしっかりと対応してくれます。このことからp(n,k)=q(n,k)であることを確認することができました。