弱組成の単調減少写像としての分割数

弱組成を使い分割数を生成する

分割数の考え方と生成方法

分割数について理解するため次の問題を考えます。

Example 4.1

整数6をいくつかの正の整数の和であらわしてください。ただし、2+2+1+1、1+1+2+2などは区別せず、１つの組合せと考えます。

分割数の考え方

答えは、表の1列目の分割にあるように11通りになります。2+2+1+1、1+1+2+2などは区別しないということは重複も許す広義単純減少写像になります。

分割	弱組成
1 + 1+ 1+ 1+ 1+ 1	(1, 1, 1, 1, 1, 1)
2 + 1+ 1+ 1+ 1	(2, 1, 1, 1, 1, 0)
3 + 1+ 1+ 1	(3, 1, 1, 1, 0, 0)
2 + 2+ 1+ 1	(2, 2, 1, 1, 0 ,0)
4 + 1+ 1	(4, 1, 1, 0, 0, 0)
3 + 2+ 1	(3, 2, 1, 0, 0, 0)
2 + 2+ 2	(2, 2, 2, 0, 0, 0)
5 + 1	(5, 1, 0, 0, 0, 0)
4 + 2	(4, 2, 0, 0, 0, 0)
3 + 3	(3, 3, 0, 0, 0, 0)
6	(6, 0, 0, 0, 0, 0)

このような1つ１つの整数の和の組合せ、例えば2+2+1+1を分割 (partition)、2や1のように分割を構成する個々の正の整数を和因子(part)、2+2+1+1は4つの和因子の組合せになり、この4を和因子数（number of parts）と呼びます。また、正の整数nに対する分割の個数は分割数(partition number)と呼び、p(n)であらわします。例えばp(6)=11 (partition number of 6 is 11)と読みます。分割は2+2+1+1のように降順に並べ、(2, 2, 1,1) と表記することにします。たかだか6のような小さな整数でも、思いつくままに書き出していたのでは正確に数え上げるのは容易ではありません。

この問題を解くために応用できる写像として弱合成が挙げられます。表の2行目にように最大和因子が６なので$n=k=6$の全射・単射の制限がない任意写像である弱合成を当てはめると類似した問題であることに気づきます。

図では１が分割になります。２は$x_1+x_2+x_3 +x_4+x_5+x_6=6\quad(x_i\geqq0)$という条件の弱組成をします。例えば2+2+1+1の場合、$x_1=2,x_2=2,x_3=1,x_4=1,x_5=x_6=0$として、$x_5～x_6$の0を削除することにより分割を生成することができます。つまり、分割は２の弱合成を単純減少写像になるので集合Kを区別のつかいない写像に再構築したものであることがわかります。

単調増加写像を抽出して区別のつかない構造に変換

generate_weak_compositionでn=6、k=6の弱組成をリストweak_composition_listとして生成し、ここからfilter_increasing_map関数を使い、分割の条件である降順でなおかつ同じ数が並んでもよい（広義単調増加：weakly increasing）広義の単純減少写像を抽出します。

Code 4.1　n=k=6の弱組成を生成し広義の単純減少写像を抽出

n = 6
weak_composition_list = generate_weak_composition(n, n)
decreasing_composition_list = filter_increasing_map(
weak_composition_list,
strict = False,
reverse = True
)
decreasing_composition_list

[(1, 1, 1, 1, 1, 1),
 (2, 1, 1, 1, 1, 0),
 (2, 2, 1, 1, 0, 0),
 (2, 2, 2, 0, 0, 0),
 (3, 1, 1, 1, 0, 0),
 (3, 2, 1, 0, 0, 0),
 (3, 3, 0, 0, 0, 0),
 (4, 1, 1, 0, 0, 0),
 (4, 2, 0, 0, 0, 0),
 (5, 1, 0, 0, 0, 0),
 (6, 0, 0, 0, 0, 0)]

2.　任意写像のためn=k=6になるので、n=6として同じ引数を指定します。

3.　減少関数であることからreverse=Trueとし、弱組成であることから広義の単調減少写像であるので、strict=Falseとしてfilter_increasing_map関数を呼びだします。

分割数は11で正しく計算できていますが、弱組成であることから要素に0が入っています。分割としての体をなすために0を削除する必要があります。

要素にある0を削除

decreasing_composition_listは単純減少写像なので、削除する必要がある0はシーケンスの右側に寄っています。このため、読み込んだシーケンスに対して末尾の0を削除すると処理を0の要素がなくなるまで繰り返します。

Code 4.2　増加関数または減少関数の配列を抜き出す

partition_list_from_composition = []
for seq in decreasing_composition_list:
while seq[-1] == 0:
seq = seq[:-1]
partition_list_from_composition.append(seq)
print(
f'count of partition from composition ({n}) : '
f'{len(partition_list_from_composition)}'
)
partition_list_from_composition

count of partition from composition (6) : 11
[(1, 1, 1, 1, 1, 1),
 (2, 1, 1, 1, 1),
 (2, 2, 1, 1),
 (2, 2, 2),
 (3, 1, 1, 1),
 (3, 2, 1),
 (3, 3),
 (4, 1, 1),
 (4, 2),
 (5, 1),
 (6,)]

3.　読み込んだシーケンスの最後の要素をseq[-1]が0である間は、4行目の処理を繰り返します。

4.　seqの最後の要素（つまり0）の1つ手前までをスライスして、新たに同じ名前のseqというタプルを作成し代入します。リストであれば4行目はpopメソッドを使うことができますが、タプルはイミュータブルなので、スライスしたタプルの内容を、同じ名前の変数を新たに作成し代入します。

このように分割は集合N、Kともに区別のつかない全射・単射の制限のない任意写像であることがわかります。これまで、集合N、Kともに相異なる、またはいずれか一方が区別がつかない写像を扱ってきました。最後に、単純かと思いきや、実は非常に複雑で奥深いものがあります。

SymPyライブラリによる分割数の表示

PythonのSymPyライブラリには、分割数の計算や分割の生成をする関数がいくつか用意されています。これらを使い、これまでの上記のプログラムが正しいことを確認します。

分割数を計算するSymPyライブラリのpartition関数

SymPyライブラリが提供するpartition関数を使用することにより、分割数を計算することができます。

Code 4.3　SymPyライブラリで分割数の計算をする

from sympy import partition
sym_partition_cnt = partition(n)
print(type(sym_partition_cnt))
print(f'partition={int(sym_partition_cnt):>3}')


partition= 11

3.　partition関数の戻り値はsympy.core.numbers.Integerクラスという特別な形式の整数の型になります。

4. 　sympy.core.numbers.Integerクラスはf-formatでは使用することができないのでint関数を使用し、整数型に変換します。

SymPyライブラリのpartition関数で、nに応じた分割数の数を計算することができます。N=6の場合、分割数は11個になり、計算結果と一致することがわかります。

分割を生成するSymPyライブラリのpartitions関数

SymPyライブラリには、分割を生成する関数が2つ用意されていますが、いずれも出力結果を加工する必要があります。

SymPyライブラリのpartitions関数

SymPyライブラリのsympy.utilities.iterablesモジュールで提供されるpartitions関数を使用することにより、分割を生成することができます。出力結果はジェネレータとなるので、後の処理を想定してリストに変換します。

Code 4.4　SymPyライブラリのpartitions関数による分割の生成

from sympy.utilities.iterables import partitions
sym_partitions_gen = partitions(n)
print(type(sym_partitions_gen))
sympy_partitions_dict = list(sym_partitions_gen)
sympy_partitions_dict


[{6: 1},
 {5: 1, 1: 1},
 {4: 1, 2: 1},
 {4: 1, 1: 2},
 {3: 2},
 {3: 1, 2: 1, 1: 1},
 {3: 1, 1: 3},
 {2: 3},
 {2: 2, 1: 2},
 {2: 1, 1: 4},
 {1: 6}]

3.　partitions関数の戻り値の形式をtype関数で調べます。ジェネレータ形式になるのでsym_partitions_genという変数に結果を代入します。

4.　生成した結果を確認し、次の処理で比較をするために利用するのでリスト形式に変換します。

分割数は11となり、計算結果も正しいようですが、例えば、(2,2,1,1) は{2: 2, 1: 2}となるように、出力結果は和因子をキー、その和因子の個数をvalueとする辞書形式となっています。自作関数と比較するため、辞書形式をタプルに変換する必要が生じます。

辞書形式をリストに変換する関数

partitions 関数で生成した辞書の分割をタプルやリストのようなシーケンスにへの変換します。は今後も同様の処理が想定されるので、dict_convert_to_seqという関数をして作成します。この関数では{2: 2, 1: 2}のような辞書形式は2が2個と1が2個なので(2, 2, 1, 1)のように変換します。

また引数のoutputは、”tuple”とした場合タプルで、”list”として場合リストで返します。このテキストではシーケンスはタプルにするのが原則なので、省略した場合はtupleとします。なお、outputに’tuple’か’list’以外を指定した場合にはエラーを返すよう工夫します。

Code 4.5　辞書形式をタプルに変換する関数

def dict_convert_to_seq(input_dict, output = 'tuple'):
converted_list = []
for key, value in input_dict.items():
converted_list.extend([key] * value)
if output == 'tuple':
return tuple(converted_list)
elif output == 'list':
return converted_list
else:
raise ValueError("output must be either 'tuple' or 'list'")
sym_partitions_list = []
for partition_dict in partitions(n):
sym_partitions_list.append(dict_convert_to_seq(partition_dict))
sym_partitions_list

 [(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)]

3.　辞書内の全てのkey, value（個数）のペアを取得してループ処理を行います。ここで key は和因子、value はその個数を表す整数です。

4.　keyの値をvalueの数だけ繰り返すリスト [key] * value を生成し、シーケンスを作成するconverted_list の末尾に追加しています。

5.　引数がreturn_list=Falseの場合がデフォルトでタプルを返します。

value

SymPyライブラリordered_partitions関数

SymPyライブラリにはpartitionsのほか、分割を生成する関数としてsympy.utilities.iterablesモジュールで提供されるordered_partitions関数があります。この関数も戻り値はジェネレータなのでlist関数でリストに変換します。

Code 4.6　ordered_partitions関数で分割を生成する

from sympy.utilities.iterables import ordered_partitions
sym_ordered_partitions_list=list(ordered_partitions(n, sort = True))
sym_ordered_partitions_list

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

2.　ordered_partitions関数のsortパラメーターをTrueにすると分割が辞書のように昇順で生成されます。今後の流れで生成された順番で出力されるといわれているので、Trueとしておいた方が無難です。

分割を生成することができましたが、分割を表すシーケンスがリストになっていることと、シーケンスの並びが単純増加写像になってはいるのが気になります。そこで、広義の単純減少写像に変換したのち、convert_to_tuple関数を使いタプルに変換します。

Code 4.7　ordered_partitions関数で分割を生成する

reversed_list = []
for partition in sym_ordered_partitions_list:
reversed_list.append(partition[::-1])
reversed_sym_ordered_partitions_list = convert_to_tuple(
reversed_list
)
reversed_sym_ordered_partitions_list

[(1, 1, 1, 1, 1, 1),
 (2, 1, 1, 1, 1),
 (3, 1, 1, 1),
 (2, 2, 1, 1),
 (4, 1, 1),
 (3, 2, 1),
 (5, 1),
 (2, 2, 2),
 (4, 2),
 (3, 3),
 (6,)]

3.　ordered_partitions関数では、sort=Trueとしているので単調増加写像であることは担保されているので、リストに対して[::-1]とスライスすることにより並びを逆転させることができます。単調増加写像であることが確認できない場合は降順のソートする必要があります。

4.　 convert_to_tuple関数はoutputを省略し、タプルに変換します。

分割の並び順にまちまちなところはありますが、弱組成から抽出したものの、SymPyライブラリが提供する2つの関数の出力結果を比較する準備が整いました。

弱組成から生成した分割とSymPyライブラリの関数の結果を比較

Code 4.8　弱組成から生成した分割とSymPyの2つの関数で生成した分割を比較

if (
sorted(partition_list_from_composition)
== sorted(sym_partitions_list)
== sorted(reversed_sym_ordered_partitions_list)
):
print(
f'list from composition'
f' == SymPy_partitions'
f' == SymPy_ordered_partitions'
)

list from composition == SymPy_partitions == SymPy_ordered_partitions

1.　連鎖比較（chained comparison）を使うことにより、3つのオブジェクトを比較することができます。

任意写像の弱組成を降順のものだけを抜き出すことによって生成した分割はSymPyライブラリのordered_partitions関数およびpartitions関数の結果が等しくなることがわかりました。ただし、ordered_partitions関数とpartitions関数は出力する形式だけではなく、今後の展開において少し異なる挙動を示します。

分割を生成する関数を自作する

組成のプログラムを分割の生成のプルグラムに変更

組成を生成するプログラムをもとに分割を生成するプログラムを作成します。分割は単調減少関数であることから、要素を挿入するときに最大値をstartとして最小値0までを順次、値を1ずつ減らしていきます。startは0番目の要素の時にはnですが、1番目からは、nからこれまで生成した要素の合計と直近に挿入した要素を比べ小さい方の値とすることになるので、組成よりも効率的な処理が可能となることが期待されます。

Code 4.9　増加関数または減少関数の配列を抜き出す

def generate_partition(n):
composition_list = [()]
for i in range(n):
next_composition = []
for seq in composition_list:
remaining = n - sum(seq)
if remaining == 0:
next_composition.append(seq)
else:
if i == 0:
start = n
else:
start = min(seq[-1],remaining)
for num in range(start,0 , -1):
next_composition.append(seq + (num,))
composition_list = next_composition
return composition_list
generate_partition(6)

[(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)]

6.　remainingはnから直近のループで作成したシーケンスの合計を差し引き、残りの和因子の合計を計算しています。

7.　remainingが0の場合、分割は完成しているので、そのままnext_compositionに追加します。

9.　remainingが0でないときは、新たに和因子を追加します。startは追加する和因子の最大値を代入します。一番初めのループではnが最大であり、それ以降のループでは、remainingとseqの最後の値を比較し小さな方を選びます。分割は広義単調減少写像なので、直近の値以下の数値になることが必要です。

14. range(start,0 , -1)でstartから1まで降順に和因子を追加します。

分割を生成することはできましたが、8行目でループの早い段階で分割が完成しても何度もnext_compositionとcompositio_listnを何度も往き来する無駄が発生します。改善の余地はありますが、ここでは計算結果が正しいかを確認するにとどめます。

分割を生成する関数とSymPyライブラリの関数の計算結果を比較

分割については組成から作成したもの、SymPyライブラリの関数で作成し、それぞれ計算結果が一致していることがわかりました。ここでは、自作のプログラムとpartitons関数を比較し、正しく作成されていることを確認します。

Code 4.10　自作の分割を生成する関数とSymPyのpartitions関数の結果を比較

if partition_list==sym_partitions_list:
print('partition_list == SymPy_partitions ')

partition_list == SymPy_partitions

1.　リストsym_partitions_listはCodeで作成

分割については、組成のプログラムに対して、集合Nについて区別されない写像に変換することにより生成することができました。しかし、いかにも力づくとの印象が否めません。また、分割数に至っては、今のところ生成した分割の数を数えるしかありません。そこで、次の章からは、これまで学んできた手法を駆使して、よりスマートに分割に迫っていきたいと思います。

強組成

集合$N$、集合$K$に対して全射・単射の制限のない任意写像である分割の生成のプログラムを作成することができましたが、今一つ切れ味に欠けます。そこで、任意写像であるベル数と全射のスターリング数の関係を応用し、任意写像である分割を、和因子数ごとに整理することにより関係を分析してみます。

K=1から6までを結合して弱組成を生成する

K=1から6までの弱組成を生成する

k=1からk=6までgenerate_strict_composition関数を使い全射の強組成を生成し、その各々についてfilter_increasing_map関数を適用し単純減少写像のものを抽出することにより、和因子数ごとの分割に絞り込みます。細かく分けることにより、うまい計算方法を探します。

Code 4.11　弱組成で要素数が1から6まで計算

composition_list = []
for i in range(1, n+1):
composition_list.append(generate_strict_composition(i, n))
partition_list = []
for l in composition_list:
partition_list.append(filter_increasing_map(l ,strict=False, increase=False))
sigma_composition = 0
sigma_partition = 0
print(f' i |composition| partition |')
print(f'-----+-----------+-----------|')
for num, (cnt_composition, cnt_partition) in enumerate(
zip(composition_list, partition_list), start=1
):
print(f'{num:^5}|{len(cnt_composition):>11}|{len(cnt_partition):>11}|')
sigma_composition += len(cnt_composition)
sigma_partition += len(cnt_partition)
print(f'-----+-----------+-----------|')
print(f'sigma|{sigma_composition:>11}|{sigma_partition:>11}|')
from_composition_list = sum(partition_list,[])
from_composition_list

 
[(6,),
 (3, 3),
 (4, 2),
 (5, 1),
 (2, 2, 2),
 (3, 2, 1),
 (4, 1, 1),
 (2, 2, 1, 1),
 (3, 1, 1, 1),
 (2, 1, 1, 1, 1),
 (1, 1, 1, 1, 1, 1)]

11.　 composition_list と partition_list を zip 関数でタプルの形にまとめ、それぞれの要素を cnt_composition と cnt_partition に順次取り出しています。このとき、enumerate 関数を使うことで、それらの要素に加えてインデックスを num に取得しています。インデックスは 0 からではなく 1 から始めたいので、enumerate の引数 start=1 を指定しています。

強組成と分割の個数の分析

表から次のことが読み取れます。

1からnまでの強合成から単純減少関数

ベル数とスターリング数の分析から、集合Kにおいて区別のつかない写像であれば、全てのkの全射の写像の個数の合計と、任意写像の合計が等しくなることがわかりました。分割も同様に集合Kにおいて区別のつかない写像であるので、同じことがいえるか確認します。前節で計算したようにp(6)=11から分割についても同じことが言えます。このため、全射の写像を生成することができれば分割数もよりスマートに生成することができる見通しが立ちます。

強組成と和因子数ごとの関係

スターリング数を生成する際、全射の重複順列からスターリング数に関わる集合分割を抽出するときk!個が1つに集約されました。

ところが、分割の場合は同じになるので、同じ3個の組み合わせでも、一括して3!とするのではなく重複度に応じて割り返す数が変わってきます。

例えば(3,2,1)の分割は集合Nが相異なる場合も、区別のつかない場合も3!通りが1つの分割に集約されます。これに対して(4, 1, 1)の分割はスターリング数では、(A)(B)(C,D,E,F)と(B)(A)(C,D,E,F)は別のものと認識し3!通りと変わりませんが、分割では和因子1を2つ含む分割では、重複があるため 3! / 2! 通りを1つにまとめる必要があります。さらに図には記載されていませんが、(2,2,2)の場合は同じ和因子の数が3です。ということは集約後も１つの分割となります。となります。このように、スターリング数の場合とは異なり、を1つの分割に集約するときに場合分けをする必要があります。ここが分割の難しさですが、とんでもなく奥が深い世界が待っています。

$x_1+x_2+x_3 \lt6\quad(x_i\geqq1)$の弱組成の解の個数は$\_k H_{n-k} =\ _{n-1} C_{n-k}=\ _{n-1} C_{k-1}$とります。よってk=3の場合は

$x_1+x_2+x_3 = n \\ x_i\geqq 1\quad(i=1,2,\cdots,k)$

$\ _6 H_{6-3} =\ _{5} C_{2}=10$となり計算結果が正しいことがわかります。

ここで１は$x_1+x_2+x_3 \lt6\quad(x_i\geqq1)$を満たす組合せを表すので、強合成（strong composition）に他なりません。ここでは、集合Kに$x_1,x_2,x_3$のラベルありで、3+2+1と1+2+3は別の組み合わせとして計算しています。ところが分割ではこれらは同じものとして数えるので、組み合わせと同じように増加写像の考え方を使い、２のように相異なる（indistinct.）写像に変換する必要があります。