分割数を写像から考える

ぴったりではなく、それ以下という補助関数

分割数がk以下である分割の数　p*(n,k)

これまで、nの分割で和因子数がkのp(n,k)についてみてきました。これに対して和因子数がk個以下とする関数をp*(n k)と定義します。

例えばp*(6,3)は次の3つに分類されます。

①p(6, 3)　 (4, 1, 1), (3, 2, 1), (2, 2, 2)

②p(6,2) (5,1),(4,2),(3,3)

③p(6,1) (6)

p*(6, 3)を求めるためには、①から③を合計すればよいわけですが、あまりにも芸がありません。そこで、p*(n,k) とp(n,k)との関係を見るために、p(9,3)との関係を考えます。p(9,3)の9はn+k=6+3を意味します。

P(9,3)を次のとおり分類します。

①和因子に1が含まれていない分割　 (5,2,2),(4,3,2),(3,3,3)

②和因子に1が1つ含まれている分割 (6,2,1),(5,3,1),(4,4,1)

③和因子に1が2つ含まれている分割 (7,1,1)

①の代表として(3,3,3)を取り上げます。各和因子を1つずつ差し引くとp(6,3)の(2,2,2)に対応します。(5,2,2),(4,3,2)についても同様です。

②の代表として(5,3,1) を取り上げます。各和因子を1つずつ差し引くと (4,2,0)になり、右側の0を削除するとp(6,2)の(4,2)になります。

③の要素(7,1,1) を取り上げます。各和因子を1つずつ差し引くと (7,0,0)になり、右側の0、2つを削除するとp(6,1)の(6)になります。

逆に、p*(6,3)の要素に対し、和因子数が1,2の場合は右側に0を補い、3つのの配列にし、それぞれ１ずつを加えるとl(9,3)になります。

結果的にp*(6, 3)とp(9, 3)はお互いに逆写像を持ち一対一対応となります。

p(n+k, k)=p*(n,k)

p(n,k)とp*(n,k)との全単射（一対一対応）
p(n,k)とp*(n,k)との全単射（一対一対応）

さっそく、pn_list_func関数を使いp*(6,3)とp(9,3)の関係を確かめます。P*(6,3)はp(6,1),p(6,2),p(6,3)を結合してリストpn_63に代入し、p(9,3)も同じ関数で生成してp_93に代入し、分割ごとに比較します。

p(n+k, k)とp*(n,k)の関数

  1. pn_93 = pn_list_func(9, 3)
  2. pn_aster_63 = pn_list_func(6, 1)+pn_list_func(6, 2)+pn_list_func(6, 3)
  3. for i,j in zip(pn_93, pn_aster_63):
  4. print(f'{str(i):<14}{str(j):<14}')
[7, 1, 1]     [6]           
[6, 2, 1]     [5, 1]        
[5, 3, 1]     [4, 2]        
[4, 4, 1]     [3, 3]        
[5, 2, 2]     [4, 1, 1]     
[4, 3, 2]     [3, 2, 1]     
[3, 3, 3]     [2, 2, 2]

3.　pn_93とpn_aster_63をzip関数で要素ごとに組み合わせて出力します。

4.　2つのリストを並べて見やすくするため、列幅を14文字分とします。str関数でリストを

文字列に変換すると列幅を指定することができます。

p(n)とp*(n)の関係が分かったところで、pnを生成するpn_list_func 関数を使い、p*(n)を生成する関数を作成します。pn_list_func関数の引数nをn+kにして呼び出すことにより、p*(n)のもとになるリストを生成することができます。ここから、k個の和因子から1を引き、０になったら削除するよう処理をします。

p*(n)のリストを生成する

  1. def pn_aster_list_func(n, k):
  2. array = []
  3. for elm in pn_list_func(n+k, k):
  4. new_elm = []
  5. for item in elm:
  6. if item > 1:
  7. new_elm.append(item-1)
  8. array.append(new_elm)
  9. return array
  11. for i,j in zip(pn_aster_list_func(6, 3), pn_aster_63):
  12. print(f'{str(i):<18}{str(j):<16}')
[6]           [6]           
[5, 1]        [5, 1]        
[4, 2]        [4, 2]        
[3, 3]        [3, 3]        
[4, 1, 1]     [4, 1, 1]     
[3, 2, 1]     [3, 2, 1]     
[2, 2, 2]     [2, 2, 2]

2.　全体の配列はarrayに、また4.にあるように個々の分割はnew_elmというリストにします。

3.　 pn_list_func(n+k,k)で生成したリストに対し、和因子が1であれば何もせず、1よりおおきければ1を引いてnew_elmに追加することで、p*(n, k)の分割を生成することができます。

最大の和因子がk以下の分割の個数　q*(n,k)

例えばp*(q,3)は次の3つに分類されます。

①q(6, 3)　 (3, 1, 1, 1) (3, 2, 1)(3, 3)

②q(6,2) (2, 1, 1, 1, 1)(2, 2, 1, 1)

③q(6,1) (1, 1, 1, 1, 1, 1)

q*(n,k) とq(n,k)との関係を見るために、q(9,3)との関係を考えます。q(9,3)の9はやはりn+k=6+3を意味します。

q(9,3)を次のとおり分類します。

①2番目に大きな和因子が3の分割　(3, 3, 1, 1, 1) (3, 3, 2, 1)(3, 3, 3)

②2番目に大きな和因子が2の分割 (3, 2, 1, 1, 1, 1)(3, 2, 2, 1, 1)

③2番目に大きな和因子が1の分割 (3, 1, 1, 1, 1, 1, 1)

①の代表として(3,3,3)を取り上げます。最大和因子（左端）の3を削除するとq(6,3)の(3,3)に対応します。(3, 1, 1, 1),( 3, 2, 1)についても同様です。

②の代表として(3, 2, 2, 1, 1) を取り上げます。最大和因子（左端）の3を削除すると 、q(3,2 ) の(2, 2, 1, 1)になります。

③の要素(3, 1, 1, 1, 1, 1, 1) を取り上げます。最大和因子（左端）の3を削除すると 、q(3,1 ) の(1, 1, 1, 1, 1, 1)になります。

逆に、q*(6,3)の要素に対し、最大和因子（左端）に3を追加するとq(9,3)になります。

結果的にq*(6, 3)とq(9, 3)はお互いに逆写像を持ち一対一対応となります。

p(n,k)とp*(n,k)
p(n,k)とp*(n,k)

さっそく、pn_list_func関数を使いq*(6,3)とq(9,3)の関係を確かめます。q*(6,3)はq(6,1),q(6,2),q(6,3)を結合してリストqn_63に代入し、q(9,3)も同じ関数で生成してp_q3に代入し、分割ごとに比較します。

q(9,3)とq*(6,3)の関係を確かめる

  1. qn_93 = qn_list_func(9, 3)
  2. qn_aster_63 = qn_list_func(6, 1)+qn_list_func(6, 2)+qn_list_func(6, 3)
  3. for i,j in zip(qn_93, qn_aster_63):
  4. print(f'{str(i):<26}{str(j):<26}')
[3, 1, 1, 1, 1, 1, 1]     [1, 1, 1, 1, 1, 1]        
[3, 2, 1, 1, 1, 1]        [2, 1, 1, 1, 1]           
[3, 2, 2, 1, 1]           [2, 2, 1, 1]              
[3, 2, 2, 2]              [2, 2, 2]                 
[3, 3, 1, 1, 1]           [3, 1, 1, 1]              
[3, 3, 2, 1]              [3, 2, 1]                 
[3, 3, 3]                 [3, 3]

比べます。

q*(n, k)=q(n+k,k)

p(n)とp*(n)の関係が分かったところで、pnを生成するpn_list_func 関数を使い、p*(n)を生成する関数を作成します。pn_list_func関数の引数nをn+kにして呼び出すことにより、p*(n)のもとになるリストを生成することができます。ここから、k個の和因子から1を引き、０になったら削除するよう処理をします。

qnとq*nの関係を確認する

  1. def qn_aster_list_func(n, k):
  2. array = []
  3. for elm in qn_list_func(n+k, k):
  4. array.append(elm[1:])
  5. return array
  7. for i,j in zip(qn_aster_list_func(6, 3), qn_aster_63):
  8. print(f'{str(i):<24}{str(j):<24}')
[1, 1, 1, 1, 1, 1]      [1, 1, 1, 1, 1, 1]      
[2, 1, 1, 1, 1]         [2, 1, 1, 1, 1]         
[2, 2, 1, 1]            [2, 2, 1, 1]            
[2, 2, 2]               [2, 2, 2]               
[3, 1, 1, 1]            [3, 1, 1, 1]            
[3, 2, 1]               [3, 2, 1]               
[3, 3]                  [3, 3]

3.　 qn_list_func(n+k,k)で生成したリストに対し、最大和因子（左端）を削除してarrayに追加します。

def qn_aster_list_funcの方が、分割の左端を削除するだけなので処理が簡単なのがわかります。

ictsr4 All Rights Reserved.