1
高校数学解説
文献あり

組合せ論と母関数2:自然数の分割

287
0

はじめに

prevの結果を使います。

自然数の分割

a,b,c,..の代わりにq,q2,q3,..を使います。すると積は指数の和になり、自然数の分割に関係した式になります。

べき乗和

べき乗和は以下のようになります。
p1=q+q2+q3+ ..=q1qp2=q2+q4+q6+ ..=q21q2p3=q3+q6+q9+ ..=q31q3 ..
べき乗和の母関数より
P=qz1qz+q2z1q2z+q3z1q3z+ ..=qz1q+q2z21q2+q3z31q3+

基本対称式

k次の基本対称式は異なるk個の文字からなる項の和です。
s1=q+q2+q3+q4+q5+q6+q7+ ..s2=q3+q4+2q5+2q6+3q7+3q8+4q9+4q10+ ..s3=q6+q7+2q8+3q9+4q10+5q11+7q12+8q13 .. ..
skq,q2,q3..のうちk個の異なる文字からなる項の総和ですが、qの指数は異なる自然数の和になり、この和がjになる組み合わせの数がqjの係数となります。jk個の異なる自然数に分割する方法の数をqk(j)とすると、以下のように表せます。
sk=j=1qk(j)qj
ちなみにk個の異なる自然数に分割できる最小の自然数はk(k+1)/2なので、j<k(k+1)/2のとき、qk(j)=0です。つまり級数はqk(k+1)/2から始まります。ニュートンの恒等式より
s1=q1q2s2=qs11qq21q23s3=qs21qq2s11q2+q31q3..
これより
s1=q1qs2=q3(1q)(1q2)s3=q6(1q)(1q2)(1q3) ..
これから以下のような予想ができます。
s1=p1s2=p1p2s3=p1p2p3 ..
別の方法でもこの結果を得ることができます。
R(z)=(1+qz)(1+q2z)(1+q3z) ..=1+s1z+s2z2+ ..=(1+qz)R(qz)
これから係数比較により
1   z   z2   z3   z4..1s1s2s3s4..= 1qs1q2s2q3s3q4s4..qq2s1q3s2q4s3..
よって
s1=q(s1+1)s2=q2(s2+s1)s3=q3(s3+s2)..
これより
s1=q1qs2=q3(1q)(1q2)s3=q6(1q)(1q2)(1q3) ..
一般に
sm=qm(m+1)/2(1q)(1q2) ..(1qm) =j=1qm(j)qj
となります。よって
R=(1+qz)(1+q2z)(1+q3z) ..=1+qz1q+q3z2(1q)(1q2)+q6z3(1q)(1q2)(1q3)+ ..

自然数の分割

nm個の異なる自然数に分割する方法の数をqm(n)とします。いまの結果から
sm=qm(m+1)/2(1q)(1q2)..(1qm)=k=1qm(k)qk
両辺にqmをかけると
qm(m1)/2(1q)(1q2)..(1qm)=k=1qm(k)qkm
k<m(m+1)/2のときqm(k)=0なのでqの指数がマイナスの項などは生じません。後者から前者を引くと
qm(m1)/2qm(m+1)/2(1q)(1q2)..(1qm)=qm(m1)/2(1q)(1q2)..(1qm1)=k=1qm1(k)qk
これからqkの係数を比較して以下の関係式を得ます。

制限付き分割数の再帰式

qm(n)=qm(nm)+qm1(nm)
nをm個の異なる自然数に分割する方法の数は、n-mをm個の異なる自然数に分割する数と、n-mをm-1個の異なる自然数に分割する数の和に等しい。

ヤング図形による図解

左:1を含まない分割,  右:1を含む分割 左:1を含まない分割,  右:1を含む分割
自然数の分割はヤング図形により表すことができます。例えば図1はそれぞれ2+3+5 ,1+4+5という分割を表します。qm(n)個のヤング図形はすべて、1を含む分割か、1を含まない分割のいずれかに分類できます。まず1を含まない場合(左図)、色のついたブロックを消すと、縦の段数はmのまま、ブロック数はnmになります。このとき残ったヤング図形はqm(nm)に対応します。1を含む場合、同様に色のついたブロックを消すと、ブロック数は同じくnmになりますが、縦の段数が一つ減るのでqm1(nm)に対応するヤング図形になります。よってqm(n)=qm(nm)+qm1(nm)が成り立ちます。

異なるルールの分割数との関係

jm個の異なる自然数に分割する数をpm(j)として
qm(m+1)/2(1q)(1q2) ..(1qm) =j=1qm(j)qj
ですが
1(1q)(1q2) ..(1qm)
は完全斉次式の母関数の形をしています。これは重複を許した組み合わせの項からなるので、重複を許した自然数の分割に関係します。用語の使用に関してですが、重複を許すルールをデフォルトにし、許さない場合は「異なる」をつけることにします。j1,2, ..,mによって分割する数をpm(j)(独自の記法)とすると
1(1q)(1q2) ..(1qm)=j=1pm(j)qj
よって

分割数の関係式

qm(n)=pm(nm(m+1)/2)
nをm個の異なる自然数に分割する数は、nm(m+1)/2を1からmまでの自然数で分割する方法に等しい。

ヤング図形による図解

左:!FORMULA[59][-1652904740][0], 右:!FORMULA[60][-651449794][0] 左:qm(n), 右:pm(nm(m+1)/2)
m個の異なる自然数からなる分割において、分割を(a1,a2,..,am)のように表し、昇順にすると隣合う数字は必ず1以上の差があります。このためbk0となる(b1,b2,..bm)を使って(a1,a2,..,am)=(1,2,..,m)+(b1,b2,..,bm)と表せます。図2の左図のグレーの部分が(1,2,..,m)という分割に対応します。グレーの部分のブロック数はm(m+1)/2なのでこれを引いた(b1,b2,..,bm)nm(m+1)/2の分割に対応します。(b1,b2,..,bm)は図2の右図のように並べることができ、これはnm(m+1)/2を1からmまでの自然数で分割する方法に等しくなります。

完全斉次式

h1=q+q2+q3+q4+q5+q6+q7+ ..h2=q2+q3+2q4+2q5+3q6+3q7+4q8+4q9+ ..h3=q3+q4+2q5+3q6+4q7+5q8+7q9+8q10 .. ..
jk個の自然数に分割する方法の数をpk(j)とすると、以下のように表せます。
hk=j=1pk(j)qj

V(z)=1(1qz)(1q2z)(1q3z) ..=1+h1z+h2z2+ ..=(1qz)V(qz)
から係数比較より
h1=q(h1+1)h2=q(h2q+h1)h3=q(h3q2+h2)..
よって
h1=q1qh2=q2(1q)(1q2)h3=q3(1q)(1q2)(1q3)..
一般に
hm=qm(1q)(1q2) ..(1qm)=j=1pm(j)qj
となります。よって
V=1(1qz)(1q2z)(1q3z) ..=1+qz1q+q2z2(1q)(1q2)+q3z3(1q)(1q2)(1q3)+ ..

異なるルールの分割数との関係

基本対称式の結果と比較すると
s1=h1s2=qh2s3=q3h3s4=q6h4..
一般に
sm=qm(m1)/2hm
これから以下の関係を得ます。

分割数の関係式

qm(n)=pm(nm(m1)/2)
nをm個の異なる自然数に分割する数は、nm(m1)/2をm個の自然数で分割する方法に等しい。

ヤング図形による図解

左:!FORMULA[86][-1652904740][0], 右:!FORMULA[87][-1847248768][0] 左:qm(n), 右:pm(nm(m1)/2)
(a1,a2,..,am)=(0,1,..,m1)+(b1,b2,..,bm)のように分割すると(b1,b2,..bm)bk1となり、ブロック数はnm(m1)/2となります。(b1,b2,..bm)の数はnm(m1)/2をm個の自然数で分割する方法に等しくなります。

分割数の再帰式

いまの式を公式1
qm(n+m)=qm(n)+qm1(n)
に代入すると
pm(nm(m3)/2)=pm(nm(m1)/2)+pm1(n(m1)(m2)/2)
変数を置き換えると以下の式を得ます。

分割数の再帰式

pm(n)=pm(nm)+pm1(n1)
nをm個の異なる自然数に分割する数は、nmm個の自然数で分割する方法とn1m1個の自然数に分割する方法の和に等しい。

ヤング図形による図解

左:1を含まない分割,  右:1を含む分割 左:1を含まない分割,  右:1を含む分割
nをm個に分割する方法は、1を含む分割とそうでない分割に分けれます。1を含まない分割から、グレーの部分を引くと、n-mをm個に分割するヤング図形になるので、pm(nm)に対応します。1を含む分割は右図のヤング図形になります。これからグレー部分を引くとpm(n1)に対応するヤング図形になります。このため
pm(n)=pm(nm)+pm1(n1)
となります。

問題によってヤング図形の操作が違う理由

同じ議論がqm(n)にも使えるじゃないかと思われるかもしれませんが、qm(n)では、1が一回しか使えないので、その1を引くと、2以上の異なる自然数からなる分割となり、分割のルールが変わってしまいます。逆にpm(n)の1を含む場合からnを引くと、1の個数によって異なる個数への分割になってしまいます。同じルールの分割数どうしの関係を得たいので、問題によってヤング図形の操作が違うのです。

z=1のとき

z=1とするとm個に分割するという制限がなくなります。nを異なる自然数に分割する数をq(n),nを自然数に分割する数をp(n)とすると
R=(1+q)(1+q2)(1+q3) ..=1+n=1q(n)qnV=1(1q)(1q2)(1q3) ..=1+n=1p(n)qn
となります。

オイラーの分割恒等式

(1+q)(1+q2)(1+q3) ..=(1q2)(1q4)(1q6)(1q8)..(1q)(1q2)(1q3)(1q4)..=1(1q)(1q3)(1q5)..
なのでnを異なる自然数に分割する方法の数をq(n)、nを奇数によって分割する数をpodd(n)とすると

オイラーの分割恒等式

q(n)=podd(n)
nを異なる自然数に分割する方法の数は、nを奇数による分割する方法の数に等しい。

組み合わせ論的考察

全ての自然数は(2n1)2mという形で表せます。これを表にすると
1,2,4,..3,6,12,..5,10,20,..7,14,28,..
二進数表記を考えれば、全ての自然数は先頭の奇数2n-1と末尾の連続する0の数mを用いた、(n,m)という組に一意に対応することが分かると思います。
1(1,10,100,1000,..)11(1,10,100,1000,..)101(1,10,100,1000,..)..
全ての自然数はこの表のどれかに対応するので、異なる自然数への分解はこの表のいくつかを埋めたものに対応します。各行の埋まりかたは自然数a,b,c,..の二進数表示と対応させることができ、
1a11b101c..
というように表せます。これは奇数を用いた分割を表します。例えば13=3+4+6
1(0,0,1)11(1,1)
なので1100+1111=14+33=1+1+1+1+3+3+3に対応します。

二進数表記の一意性

a,b,c ..としてq,q2,q4,q8..を考えます。
R(q)=(1+q)(1+q2)(1+q4)(1+q8) ..=1+Aq+Bq2+Cq3+ ..=(1+q)R(q2)
係数比較すると
1   q   q2   q3   q4   q5..1ABCDE..= 1AB..1AB..
よって
A=1B=A,C=AD=B,E=B..
結局全て1になります。よって
R(q)=(1+q)(1+q2)(1+q4)(1+q8) ..=1+q+q2+q3+ ..=11q
qkの係数はkを異なる1,2,4,8,..で分割する方法の数なので、これが一通りしかないことをこの式は示しています。これは二進数表示が一意であるという証明になっています。

天秤ばかりの問題

さきほどの問題は、天秤ばかりでどんな分銅を持っていれば全ての自然数に対応できるかという問いの答えになります。すなわち1,2,4,8,..という分銅をもっていれば、それの組み合わせで全ての自然数の重さが測れます。しかしこれは天秤の一方だけに分銅をのせる場合の話で、分銅を測りたいものと一緒に乗せてもいいなら、もっと少ない種類の分銅でよくなります。それは1,3,9,27,..という分銅です。これらを引き算と足し算を使って組み合わせることで全ての自然数が表現できます。これをみるため以下のような式を考えます。
R(q)=(q1+1+q)(q3+1+q3)(q9+1+q9) ..=(q1+1+q)P(q3)
R(q)= ..+cq3+bq2+aq1+1+Aq+Bq2+Cq3+ ..
として係数比較すると
q4   q3   q2   q1   1   q   q2   q3   q4..dcba1ABCD..=a1A..a1A..a1A..
よって
a=1,A=1a=b=c=d,A=B=C=Db=e=f=g,B=E=F=G..
よって
R(q)=(q1+1+q)(q3+1+q3)(q9+1+q9) ..=1+q+q1+q2+q2+q3+q3+ ..
qkの係数はkを異なる1,3,9,27,..を足し算と引き算で組み合わせて分割する方法の数です。この方法ですべての整数を一意に表すことができます。

参考文献

投稿日:2024428
更新日:202451
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

17世紀の数学を学び始めました。 https://www.17centurymaths.com/ このサイト素晴らしい。

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中
  1. はじめに
  2. 自然数の分割
  3. べき乗和
  4. 基本対称式
  5. 自然数の分割
  6. 異なるルールの分割数との関係
  7. 完全斉次式
  8. 異なるルールの分割数との関係
  9. 分割数の再帰式
  10. z=1のとき
  11. オイラーの分割恒等式
  12. 二進数表記の一意性
  13. 天秤ばかりの問題
  14. 参考文献