分割数を写像から考える

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

分割数の考え方

分割数の考え方

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

問題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程度の整数でも、思いつくままに書き出していたのでは正確に数え上げるのは容易ではありません。そこで図表1のように、写像を使って整理します。例えばk=3の(3,2,1)の分割は、図表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は別の組み合わせとして計算しているところです。そこで、分割を求めるためには不定方程式の組み合わせを求め、集合Kの区別なしの分割に変換すればよいことになります。

不定方程式によるリストの作成

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

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

  1. def indefinite_surjective_func(k, n):
  2. array = [[]]
  3. for kth in range(k):
  4. temp = array
  5. array = []
  6. for elm in temp:
  7. if kth < k-1:
  8. for nth in range(1, n-k+2): # range(n+1)
  9. new_elm = elm + [nth]
  10. if sum(new_elm) < n: #<=
  11. array.append(new_elm)
  12. else:
  13. break
  14. else:
  15. array.append(tuple(elm + [n-sum(elm)]))
  16. return array
  18. n = 6
  19. k = 3
  20. indefinite_surjective_func(k, n)
[(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)]

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

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

不定方程式の解の組み合わせを生成することができました。次に増加関数の考え方を使い集合Kを区別なしに変換しますが、分割は要素を大きな順番に並べるのでinccreasing_map_funcを少し変更し、2番目の引数をreverse=Trueとすることで、降順の要素を抜き出すことができるようにします。もちろん、この関数は昇順で使うことの方が多いので、reverseを指定しなければFalseとなり昇順の要素を抜き出すようにします。

不定方程式から降順の分割だけを抜き出す

  1. def increasing_map_func(inversed_list, reverse=False):
  2. array=[]
  3. for elm in inversed_list:
  4. for i in range(len(elm)-1):
  5. if (elm[i] < elm[i+1]) if reverse else (elm[i] > elm[i+1]):
  6. break
  7. else:
  8. array.append(elm)
  9. return array
  11. print(increasing_map_func(indefinite_list,reverse=True ))
[(2, 2, 2), (3, 2, 1), (4, 1, 1)]

5.　Pythonでは次のような三項演算子を使うことにより、状況に応じてifを使った条件式を切り分けることができます。

条件式が真のときに返す値 if 条件式 else 条件式が偽のときに返す値

このことにより、if reverseでrverse==Trueかを聞き、条件を変更することができます。

当初抜き出したように3つの分割を作成することができました。

分割数の難しさ

分割数を作成したり個数を求めたりする方法を一般化します。

不定方程式で求めた組み合わせの個数から分割数を求める計算方法を一般化します。スターリング数と同じようにk!で割ればよいような気がします。

例えば、n=6,k=3の場合、(3,2,1),(4,1,1),(2,2,2)の3種類の分割があります。これらのうち前2つについて集合Kについてラベル無しに変換すると図の通りになります。

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

ますが、分割数の場合は同じになるので、同じ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の分割が２つあるので、3!/2!個を1つに集約します。さらに図にはありませんが、(2,2,2)に至っては3!通りを1つの分割にするように場合分けをする必要があります。ここが分割数の難しさですが、とんでもなく奥が深い世界が待っています。

K=3以外の場合も計算

はじめに計算した分割にはk=3だけでなく、k=1からk=6までの分割が考えられます。

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

図表1を眺めていると、を使い、のようにn=6、k=6の制約なしのパターンとなり、k=1からk=6までに分類します。図1を眺めていると、不定方程式を使いkの個数ごとに組み合わせを生成し、$x_k$について増加写像の考え方を使いラベル無しの分割に変換します。

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

分割数に近い結果を得ることができましたが、まだ1+2+3、2+3+1など別の組み合わせとして数えています。そこで、増加写像の考え方を使い、ラベル無しの分割に変換します。和因子の個数は1から6まで考えられるので、それぞれの個数を計算するため、不定方程式の関数を使って全射の条件で1つ1つ組み合わせを生成します。このためk=1からk=6までindefinite_surjective_func関数を適用し、結果はリストindefinite_listに追加します。

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

  1. indefinite_list = []
  2. for i in range(1, n+1):
  3. indefinite_list.append(indefinite_surjective_func(i, n))
  4. cnt = 0
  6. for categorized_elm in indefinite_list:
  7. print(categorized_elm, len(categorized_elm))
  8. cnt += len(categorized_elm)
  9. print('合計',cnt,'個')
[(6,)] 1
[(1, 5), (2, 4), (3, 3), (4, 2), (5, 1)] 5
[(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)] 10
[(1, 1, 1, 3), (1, 1, 2, 2), (1, 1, 3, 1), (1, 2, 1, 2), (1, 2, 2, 1), (1, 3, 1, 1), (2, 1, 1, 2), (2, 1, 2, 1), (2, 2, 1, 1), (3, 1, 1, 1)] 10
[(1, 1, 1, 1, 2), (1, 1, 1, 2, 1), (1, 1, 2, 1, 1), (1, 2, 1, 1, 1), (2, 1, 1, 1, 1)] 5
[(1, 1, 1, 1, 1, 1)] 1
合計 32 個

2～3.　nに対して1からnまでのkについてindefinite_list.append関数を適用し、その結果をリストindefinite_listに追加します。

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+2+3、2+3+1など不定方程式では別のものとして数えていたものを増加関数の考え方を使って集約します。ただし、今回は分割は大きなものから並べるので、降順にするため、increasing_map_funcを降順のものを抜き出すようにして適用します。

それぞれの組を降順にして集計しやすくする

  1. cnt = 0
  2. for elm in indefinite_list:
  3. partition = increasing_map_func(elm, reverse=True)
  4. print(len(partition),'個', partition)
  5. cnt += len(partition)
  6. print('合計',cnt,'個')
  7. print('合計',cnt,'個') 
1 個 [(6,)]
3 個 [(3, 3), (4, 2), (5, 1)]
3 個 [(2, 2, 2), (3, 2, 1), (4, 1, 1)]
2 個 [(2, 2, 1, 1), (3, 1, 1, 1)]
1 個 [(2, 1, 1, 1, 1)]
1 個 [(1, 1, 1, 1, 1, 1)]
合計 11 個

5.　elmのiよりi+1番目の値が大きくなると降順にならないのでbreakしてarrayに追加しないようにします。これ以外はincreasing_map_funcと同じです。

1つ１つの組み合わせにincreasing関数をreverse=Trueとして適用して、降順になっていないものは削除します。この結果、区別なしの分割の要素の個数ごとに出力します。最初に求めた組み合わせと同じように11個になり、はじめに数え上げた個数と一致します。

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

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

PythonではSymPyライブラリを使い、分割数の一覧を作成したり個数を計算したりすることができます。これまでの計算結果を確認します。

分割数を計算する関数

分割数だけであれば、SymPyライブラリのpartition関数を使って計算することができます。

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

  1. from sympy import partition
  2. sym_partition_cnt = partition(n)
  3. print(sym_partition_cnt)
11

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

1. partition関数に正の整数を適用すると、分割数を計算することができます。

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

分割を生成する関数

分割はsympyライブラリのpartitions関数を使い生成することができます。

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

  1. from sympy.utilities.iterables import partitions
  2. sym_partition_dict = list(partitions(n))
  3. print(sym_partition_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}] 11

1.　 partitions関数はSymPyライブラリのsympy.utilities.iterablesモジュールからインポートします。

2.　 partitions関数の返り値はジェネレータという特殊な形式なので、list関数で出力結果をリストに変換します。

ただし、出力結果のうち個々の分割は辞書形式となり少し見づらいので、リスト形式に変換します。配列result_listに辞書形式の分割をリストに変換して挿入します。

辞書形式で求めた分割数をリストに変換する

  1. for elm in sym_partition_dict:
  2. result_list=[]
  3. for key, value in elm.items():
  4. result_list.extend([key] * value)
  5. print(result_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. result_listにはkeyの要素をvalue個だけ追加します。

このようにリストに変換することができました。合計11件でこれまでの計算結果と一致していることがわかります。

n=1から決められた数までの分割数を連続して生成する関数

分割を生成する関数の考え方

前節で不定方程式から分割を生成しましたが、ここでは直接に生成するプログラムを作成します。このとき、分割数の左端の最大の和因子に注目する全単射を見出すことにより、面白いプログラムを作ることができます。

和因子の最大値から分割数を作成
和因子の最大値から分割数を作成

6の分割数11個を集合Xとします。これに対し、集合Xの分割の最も大きな数字（左端）を削除した分割を集合Yとします。例えば、集合Xの分割(2, 2, 1, 1)は、集合Yの(2, 1, 1)に対応します。(2, 1, 1)は4の分割になるので集合Yは6-2=4の分割数となります。このため、4の分割は全て集合Yの部分集合になるような気もしますが、実はそうではありません。例えば、(3,1)は4の分割数の1つですが、左端に2を追加すると降順であるという前提が崩れてしまいます。

少し面倒ですが、集合Ｙを別の視点から見ると、6以下のiに対して6-iの分割でなおかつ最大の和因子がiであるものと定義することができます。ここで、集合Yから集合Xへの対応を考えます。(2, 1, 1)は4の分割なので6との差2を左に追加しても降順であるとの分割を満たすので集合Xの(2, 2, 1, 1)に対応付けられ写像であるといえます。

このことから集合Xと集合Yは全単射（一対一対応）といえます。

分割数を生成するプログラム

この考え方から分割数を生成するプログラムを作成します。最終的な6の分割数は[(6),(5,1)・・・]のようにリストのなかに分割数がタプルとして埋め込まれるようにしますが、全単射の考え方を取り入れるため、1から５までの分割数を順次計算し、その結果を積み上げていくので3次元の配列になります。

関数名はpartition_func(n)とし、引数は求めたい分割のnとします。今計算している分割をcurrent_n、参照している分割をiとして定義するので、削除、追加をするk= current_n - iとなります。

和因子の最大値を順次挿入することにより分割数を計算

  1. def partition_func(n):
  2. array = [[()]]
  3. for current_n in range(1, n+1):
  4. new_array = []
  5. for i in range (current_n):
  6. for elm in array[i]:
  7. if elm == () or elm[0] <= current_n - i:
  8. new_array.append((current_n - i,) + elm)
  9. array.append(new_array)
  10. return array
  12. partition_func(6)
[[()],
 [(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)]]

2.　n=0の場合は空集合として定義します。

3.　以下で、nまで順次、分割数を求めます。

4.　作成中の分割数はnew_array に積み上げていきます。

5.　作成中の分割より小さい分割をelmに代入し、順次チェックします。

6.　iの分割の中で集合Ｙに当てはまるものについて、k= current_n - iをnew_arrayに追加します。

7.　elm == ()という条件は、n=1を作成するときelmがブランクであるためです。or条件の左側がTrueになるとorの右側は評価されません。このためelm[0]はエラーになりません。

この処理を、全て行って終了となります。

例えば、partition_func(6)を呼び出すと、数字6をさまざまな整数の和に分割したパターンがリストとして返されます。

分割をこんな簡単なプログラムで生成することができるのは驚きです。しかし、処理の中身を見るとnの分割数を求めるのに、毎回1からn-1までの分割数を1つ１つ見に行くのでかなりの無駄が生じるので、分割の個数p(n)だけを計算するのであればもっと簡単な方法を模索していきます。

ictsr4 All Rights Reserved.