分割数　制約なし　N,Kともラベルなし

不定方程式を使い分割数を生成する

分割数の考え方と不定方程式から分割を生成

分割数の考え方

これまで、写像の考え方を使い集合N、Kともに、またはいずれかに区別があるものを扱ってきました。最後に、集合N、Kともに区別がないものを考えます。区別をする必要が無いことから簡単かと思いきや、実は非常に複雑で奥深いものがあります。それではさっそく、次の問題を考えます。

Example 4.1

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

答えは、次の11通りになります。

(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)、 (2+ 2+ 2)

(5+ 1)、(4+ 2)、(3+ 3)

(6)

このような1つ１つの整数の和の組み合わせ、例えば3+ 2+ 1を分割 (partition)といい、3,2や1のように分割を構成する個々の正の整数を和因子(part)といいます。また、正の整数nに対する分割の個数は分割数(partition number)といいp(n)であらわします。例えばp(6)=11 (partition number of 6 is 11)というように表します。分割は3+ 2+ 1のように大きい数の大きいものから小さい数の順（降順）に並べるのが一般的で、通常は (3, 2, 1) のように表記します。たかだか6程度の整数でも、思いつくままに書き出していたのでは正確に数え上げるのは容易ではありません。そこでFigure 4.1のように、写像を使って整理します。

は不定方程式では$x_1+x_2+x_3 \lt6\quad(x_i\geqq1)$を満たす組み合わせを表します。ここでは、集合Kに$x_1,x_2,x_3$のラベルありで、3+2+1と1+2+3は別の組み合わせとして計算しています。ところが分割ではこれらは同じものとして数えるので２のようにラベルなしにする必要があります。このことから組み合わせと同じように増加写像の考え方を使いラベル外すようにして分割を求めていきます。

不定方程式の解の組み合わせを生成

solve_surjective_equation関数を使い、$x_k=3$の和を表す不定方程式の解の組み合わせを生成します

Code 3. 5　不定方程式の関数を使って和がnになるk個の整数を求める

def solve_surjective_equation(k, n):
solution_list = [()]
for kth in range(k):
temp = solution_list
solution_list = []
for elm in temp:
if kth < k - 1:
for nth in range(1, n - k + 2):
if sum(new_elm:=elm + (nth,)) < n:
solution_list.append(new_elm)
else:
break
else:
solution_list.append(elm + (n - sum(elm),))
return solution_list
n = 6
k = 3
equation_surjective_list = solve_surjective_equation(k, n)
equation_surjective_list

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

19.　k個の正の整数の和がnになる不定方程式を求めるのでn=6,k=3としてsolve_surjective_equation関数を呼び出します。

$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$となり計算結果が正しいことがわかります。

増加写像の考え方を使いラベルを外す

filter_increasing_map関数を使うとリストから昇順のものを抜き出すことができますが、

分割数においては降順に並べ、しかも同じ数が並んでもよいという条件なので、これまでのプログラムでは、この条件に対応できません。このためfilter_increasing_map関数を改良します。まず引数を追加してstrict=Trueをデフォルトにしながらも、Falseとすると同じものがあっても抜き出すようにします。またreverse=Trueとすることで、降順の要素を抜き出すことができるようにします。もちろん、この関数は昇順で使うことの方が多いので、reverseを指定しなければFalseとなり昇順の要素を抜き出すようにします。広義単調増加 (weakly increasing, non-decreasing)to狭義単調増加（狭義増加）(strictly increasing)

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

def filter_increasing_map(sequence, k_list = None, strict=True, reverse=False):
array = []
for elm in sequence:
for i in range(len(elm) - 1):
if strict == True and elm[i] == elm[i + 1] :
break
if k_list is None:
elm_cur = elm[i]
elm_next = elm[i + 1]
if elm_cur < elm_next if reverse else elm_cur > elm_next:
break
else:
idx_cur = k_list.index(elm[i])
idx_next = k_list.index(elm[i + 1])
if (idx_cur < idx_next) if reverse else (idx_cur > idx_next):
break
else:
array.append(elm)
return array
filter_increasing_map(equation_surjective_list, strict = False, reverse = True)

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

3.　sequenceの個々のelm対し、インデックスiを使い順次読み込み昇順でないと判断した時点で6.、11.のbreakを適用しループを抜け対象から外れます。

5.　狭義単調増の場合、前の要素と等しい場合も選ばれないようにします。k_listを省略した場合、sequenceの文字コード順に昇順のものを抜き出すようにします。

10.　三項演算子（ternary operator）を使い、reverseがTrueの場合、現在より次の要素の方が大きい場合breakします。

12. k_listを指定した場合、indexメソッドで対象とする値のk_listでの順番の値が昇順かで抜き出す際の判断をします。

n=6、和因子数が3の分割は(3,2,1),(4,1,1),(2,2,2)の3つであることが分かりました。

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

不定方程式の結果をわかりやすく集計

k=3のケースを見てきましたが、n=6の場合、図の通りk=1からk=6までの分割が考えられます。

コンポジッションの生成

分割数に近い結果を得ることができましたが、まだ1+2+3、2+3+1など別の組み合わせとして数えています。そこで、増加写像の考え方を使い、ラベル無しの分割に変換します。和因子の個数は1から6まで考えられるので、それぞれの個数を計算するため、不定方程式の関数を使って全射の条件で1つ1つ組み合わせを生成します。このような分割をordered partitionといいます。いくつかの要素を集めて一つのものを作ることで、英語の教科の中で英作文も同じ名称で呼んでいました。その意味では、これまで作成してきたものはまさにcompositionに他なりません。

それでは、k=1からk=6までsolve_surjective_equation関数を順次適用し、kの値をインデックスとするリストを作成します。また、そのリストの1つ1つにつきfilter_increasing_map関数を適用し、やはりインデックスごとの分割に絞り込みます。最後に、両者の件数を比較します。

Code 4.2　不定方程式で要素数が1から6まで計算

composition_list = []
for i in range(1, n+1):
composition_list.append(solve_surjective_equation(i, n))
partition_list = []
for l in composition_list:
partition_list.append(filter_increasing_map(l ,strict=False, reverse=True))
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

 
[(7,),
 (4, 3),
 (5, 2),
 (6, 1),
 (3, 2, 2),
 (3, 3, 1),
 (4, 2, 1),
 (5, 1, 1),
 (2, 2, 2, 1),
 (3, 2, 1, 1),
 (4, 1, 1, 1),
 (2, 2, 1, 1, 1),
 (3, 1, 1, 1, 1),
 (2, 1, 1, 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 を指定しています。

コンポジッションの個数

n=6,k=3の場合、不定方程式の解の組み合わせは$\ _{n-1} C_{k-1}=\ _5 C_3=10$で計算しました。よって、k=1からk=6まで計算すると要素数ごとの個数と総合計は次の式から計算することができます。

$\sum\limits _{k=1}^{n} \ _{n-1} C_{k-1}=\sum\limits _{k^{\prime}=0}^{n^{\prime}} \ _{n^{\prime}} C_{k^{\prime}} = \ _{n^{\prime}} C _0 + \ _{n^{\prime}} C _1+ \ _{n^{\prime}} C _2+ \ _{n^{\prime}} C _3 + \cdots \ _{n^{\prime}} C _{n^{\prime}} = 2^{n^{\prime}}=2^{n-1}$

したがって

$\ _5 C_0+\ _5 C_1+\ _5 C_2+\ _5 C_3+\ _5 C_4+\ _5 C_5=1+5+10+10+5+1=32=2^5$

このことは次の図で見るとイメージできると思います。6個の区別の無い集合Nの要素に対し、0個から5個の「しきり」をつくります。例えば、①の1+2+3は2,4,5番目の「しきり」に＋を入れます。また②のように6の分割は＋をどこにも入れません。

このように5個の「しきり」に＋を入れる入かれないかを自由に選ぶことができるので$2^{n-1}=2^5$個になることがわかります。

図らずも、分割数を計算する過程で二項定理の関係を見出すことができます。

コンポジッションと分割数の関係

コンポジッションから分割数の計算の方法の一般化を試みます。スターリング数のときには、全射の重複順列からスターリング数に関わる集合分割を抽出するとき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つの分割に集約するときに場合分けをする必要があります。ここが分割の難しさですが、とんでもなく奥が深い世界が待っています。

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

PythonのSymPyライブラリには、分割数の計算や分割の生成をする関数が用意されています。これらを使い、これまでの計算結果を確認します。

分割数を計算する関数

SymPyライブラリのpartition関数

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

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

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


partition= 11

2.　partition関数の戻り値はsympy.core.numbers.Integerクラスという特別な形式の整数の型になります。このため、3．で出力する場合にはint関数を適用します。

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

分割を生成する関数

SymPyライブラリのpartitions関数

SymPyライブラリのsympy.utilities.iterablesモジュールで提供されるpartitions関数を使用することにより分割を生成することができます。

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

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


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

3.　partitions関数の戻り値はジェネレータ形式になります。

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

分割を生成することができましたが、出力結果のうち個々の分割は辞書形式となり少し見づらいので、リスト形式に変換します。辞書からリストへの変換は今後も使用することが想定されるので、dict_convert_to_listという関数にします。配列converted_listに辞書形式の分割をリストに変換して挿入します。

このプログラムは、Pythonの辞書（dict型）を受け取り、各キーを「その値の数だけ」リスト内に繰り返して展開した新しいリストを生成する関数です。たとえば、{"a": 2, "b": 3} という辞書を渡すと、["a", "a", "b", "b", "b"] というリストが返されます。この関数は、キーとその出現回数の関係を持つ辞書データを、単純なリスト構造に変換したい場合に有用です。

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

def dict_convert_to_list(dict):
converted_list = []
for key, value in dict.items():
converted_list.extend([key] * value)
return converted_list
sym_partitions_list = []
for partition_dict in sym_partitions_dict:
sym_partitions_list.append(dict_convert_to_list(partition_dict))
symp_partitions_list = convert_to_tuple(sym_partitions_list)
symp_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 はその数を表す整数です。

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

SymPyライブラリordered_partitions関数

SymPyライブラリにはpartitionsのほか、分割を生成する関数としてsympy.utilities.iterablesモジュールで提供されるordered_partitions関数があります。ordered_partitions関数ではリストで分割を生成されますが、個々の分割の並びが昇順になります。そこで、分割の定義から降順になるための工夫をします。

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

from sympy.utilities.iterables import ordered_partitions
sym_ordered_partitions_list = []
for p in ordered_partitions(n, sort = True):
sym_ordered_partitions_list.append(p[::-1])
sym_ordered_partitions_list = convert_to_tuple(sym_ordered_partitions_list)
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にすると分割が辞書のように降順で生成されます。Sort=Falseとしても結果は変わりませんが、プログラムの流れで生成された順番で出力されるといわれているので、Trueとしておいた方が無難です。

4.　ordered_partitions関数では、昇順で分割が生成されるので降順に変換します。リストに対して[::-1]とスライスすることにより並びを逆転させることができます。

順番が逆転するものの、ordered_partitions関数を使うことにより分割を生成することができました。

コンボジッションから生成した分割とSymPyライブラリの関数の結果を比較

Code 4.7　不定方程式から生成した分割とSymPyの2つの関数で生成した分割を比較

if (
sorted(from_composition_list)
== sorted(sym_partitions_list)
== sorted(sym_orderd_partitions_list)
):
print('SymPy == list from composition')

SymPy == list from composition

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

不定方程式を積み上げたコンポジッションを降順のものだけを抜き出すことによって生成した分割はSymPyライブラリのordered_partitions関数およびpartitions関数の結果が等しくなることがわかりました。ただし、ordered_partitions関数とpartitions関数は今後の展開において、少し異なる結果をもたらすようになります。

分割数 制約なし N,Kともラベルなし