分割数　制約なし　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のように、写像を使って整理します。

Figure 4.1　分割数を不定方程式と比較する
分割数を不定方程式と比較する

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

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

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

  1. def solve_surjective_equation(k, n):
  2. solution_list = [()]
  3. for kth in range(k):
  4. temp = solution_list
  5. solution_list = []
  6. for elm in temp:
  7. if kth < k - 1:
  8. for nth in range(1, n - k + 2):
  9. if sum(new_elm:=elm + (nth,)) < n:
  10. solution_list.append(new_elm)
  11. else:
  12. break
  13. else:
  14. solution_list.append(elm + (n - sum(elm),))
  15. return solution_list
  17. n = 6
  18. k = 3
  19. equation_surjective_list = solve_surjective_equation(k, n)
  20. 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関数を使うとリストから昇順のものを抜き出すことができますが、狭義単調増加（strictly increasing)にしか対応できていません。一方、

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

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

  1. def filter_increasing_map(sequence, k_list = None, strict=True, reverse=False):
  2. array = []
  3. for elm in sequence:
  4. for i in range(len(elm) - 1):
  5. if strict == True and elm[i] == elm[i + 1] :
  6. break
  7. if k_list is None:
  8. elm_cur = elm[i]
  9. elm_next = elm[i + 1]
  10. if elm_cur < elm_next if reverse else elm_cur > elm_next:
  11. break
  12. else:
  13. idx_cur = k_list.index(elm[i])
  14. idx_next = k_list.index(elm[i + 1])
  15. if (idx_cur < idx_next) if reverse else (idx_cur > idx_next):
  16. break
  17. else:
  18. array.append(elm)
  19. return array
  21. 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までを結合してコンポジッションを生成する

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

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

Figure 4.3　集合Nも集合Kも区別なしとなる写像
集合Nも集合Kも区別なしとなる写像

コンポジッションの生成

composition分割数に近い結果を得ることができましたが、まだ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.　不定方程式で要素数が1から6まで計算

  1. composition_list = []
  2. for i in range(1, n+1):
  3. composition_list.append(solve_surjective_equation(i, n))
  4. partition_list = []
  5. for l in composition_list:
  6. partition_list.append(filter_increasing_map(l ,strict=False, reverse=True))
  7. sigma_composition = 0
  8. sigma_partition = 0
  9. print(f' i |composition| partition |')
  10. print(f'-----+-----------+-----------|')
  11. for num, (cnt_composition, cnt_partition) in enumerate(
  12. zip(composition_list, partition_list), start=1
  13. ):
  14. print(f'{num:^5}|{len(cnt_composition):>11}|{len(cnt_partition):>11}|')
  15. sigma_composition += len(cnt_composition)
  16. sigma_partition += len(cnt_partition)
  17. print(f'-----+-----------+-----------|')
  18. print(f'sigma|{sigma_composition:>11}|{sigma_partition:>11}|')
  19. from_composition_list = sum(partition_list,[])
  20. from_composition_list
 compositionとpartitionの比較
[(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の分割は＋をどこにも入れません。

Figure 4.4　不定方程式の解と二項分布
不定方程式の解と二項分布

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

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

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

コンポジッションから分割数の計算の方法の一般化を試みます。スターリング数のときには、全射の重複順列からスターリング数に関わる集合分割を抽出するときk!個が1つに集約されました。

Figure 4.5　ラベル無しの分割に変換する際のスターリング数との違い
ラベル無しの分割に変換する際のスターリング数との違い

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

Figure 4.6　和因子数ごとのラベル無しの分割への変換
和因子数ごとのラベル無しの分割への変換

例えば(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.　SymPyライブラリで分割数の計算をする

  1. from sympy import partition
  2. print(type(sym_partition_cnt))
  3. 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関数による分割の生成

  1. from sympy.utilities.iterables import partitions
  2. sym_partitions_dict = partitions(n)
  3. print(type(sym_partitions_dict))
  4. 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ライブラリで分割数を計算する

  1. def dict_convert_to_list(dict):
  2. converted_list = []
  3. for key, value in dict.items():
  4. converted_list.extend([key] * value)
  5. return converted_list
  7. sym_partitions_list = []
  8. for partition_dict in sym_partitions_dict:
  9. sym_partitions_list.append(dict_convert_to_list(partition_dict))
  10. symp_partitions_list = convert_to_tuple(sym_partitions_list)
  11. 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.　ordered_partitions関数で分割を生成する

  1. from sympy.utilities.iterables import ordered_partitions
  2. sym_ordered_partitions_list = []
  3. for p in ordered_partitions(n, sort = True):
  4. sym_ordered_partitions_list.append(p[::-1])
  5. sym_ordered_partitions_list = convert_to_tuple(sym_ordered_partitions_list)
  6. 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.　不定方程式から生成した分割とSymPyの2つの関数で生成した分割を比較

  1. if (
  2. sorted(from_composition_list)
  3. == sorted(sym_partitions_list)
  4. == sorted(sym_orderd_partitions_list)
  5. ):
  6. print('SymPy == list from composition')
SymPy == list from composition

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

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

ictsr4 All Rights Reserved.