0

組み合わせ論と母関数:q二項定理

50
0

はじめに

ここではガウスのq二項定理とそれを用いたヤコビの三重積の導出を紹介します。
前回の記事 組合せ論と母関数2:自然数の分割 の続きにもなっています。前回のものもそうですが、母関数を用いた組合せ論の考察は、組合せ論的な情報を多項式にエンコードして、組合せ論的推論を多項式に関する操作として”自動化”するという画期的手法です。

qポッホハマー記号

前回の分割数の式のようなタイプの式にはqを使うしきたりがあり、qポッホハマー記号という略記法があります。

qポッホハマー記号

(z;q)n=(1z)(1zq)(1zq2) ..(1zqn1)(z;q)=(1z)(1zq)(1zq2) ..
第2スロットがqのとき、さらに省略して
(z)n=(z;q)n(z)=(z;q)
複数のポッホハマー記号が連続するとき
(a,b,c)n=(a)n(b)n(c)n
添字がマイナスのとき逆数にします。
(z)n=1/(z)n(z)=1/(z)

前回までのあらすじ 略記ver

べき乗和

n=1qnz1qnz=n=1qnzn1qn

基本対称式

(qz)=n=1(1+qnz)=n=1qn(n+1)/2(q)nzn
nをm個の異なる自然数に分割する数をqm(n)として
qm(m+1)/2(q)m=n=m(m+1)/2qm(n)qn
※和はm(m+1)/2以下ならqm(n)=0となるのでどこからでもよい。

完全斉次式

(qz)=1(qz)=1n=1(1qnz)=n=1qn(q)nzn
nをm個の自然数に分割する数をpm(n)として
qm(q)m=n=mpm(n)qn

z=1のとき

nを異なる自然数に分割する数をq(n)、nを自然数に分割する数をp(n)として
(q)=1+n=1q(n)qn1(q)=1+n=1p(n)qn

オイラーの分割恒等式

(q)=1(q;q2)

有限積の場合

前回は以下のような無限積
(qz)=(1+qz)(1+q2z)(1+q3z) ..
を考えました。これはq,q2,q3 ..の基本対称式の母関数であり、zmの係数は
j=1qm(j)qj=qm(m+1)/2(q)m=qm(m+1)/2(1q)(1q2)(1q3) ..(1qm)
これのqjの係数はjm個の異なる整数に分割する方法の数となります。これが有限積の場合どうなるでしょうか?
(qz)n=(1+qz)(1+q2z)(1+q3z) ..(1+qnz)
この場合、使っていい整数が1からnまでになります。例えば
(1+qz)(1+q2z)=1+(q+q2)z+q3z2
1,2を重複なく使って表せる数を表します。zの係数はそのうち1個を使って表せる数で、z2の係数はそのうち2個を使って表せる数に対応します。
q+q21=1, 2=2q33=1+2
同様にn=3のとき
(1+qz)(1+q2z)(1+q3z)=1+(q+q2+q3)z+(q3+q4+q5)z2+q6z3
q+q2+q31=1, 2=2, 3=3q3+q4+q53=1+2, 4=1+3, 5=2+3q61+2+3
n=4のとき
(1+qz)(1+q2z)(1+q3z)(1+q4z)=1+(q+q2+q3+q3)z+(q3+q4+2q5+q6+q7)z2+(q6+q7+q8+q9)z3+q10z4

q+q2+q3+q41=1, 2=2, 3=3, 4=4q3+q4+2q5+q6+q73=1+2, 4=1+3, 5=2+3=1+4, 6=2+4, 7=3+4q6+q7+q8+q96=1+2+3, 7=1+2+4, 8=1+3+4, 9=2+3+4q1010=1+2+3+4

表による理解

無限積バージョンもそうですが、この式はいわば"祖母"関数であり、zについての母関数としてみると、qについての母関数が生成する仕組みになっています。表を使って計算の過程を見てみます。
(1+qz)(1+q2z)=1+qz+q2z(1+qz)
1qq2q3      1qq2q3
(1+qz)(1+q2z)(1+q3z)=(1+qz)(1+q2z)+q3z(1+qz)(1+q2z)
1qq2q3q3q4q5q6      1qq2q3q3q4q5q6
(1+qz)(1+q2z)(1+q3z)(1+q4z)=(1+qz)(1+q2z)(1+q3z)+q4z(1+qz)(1+q2z)(1+q3z)
1qq2q3q4q3q4q5q5q6q7q6q7q8q9q10      1qq2q3q4q3q42q5q6q7q6q7q8q9q10
q=1のとき二項定理の表になります。
(1+z)2
1111      121
(1+z)3
121121      1331
(1+z)4
13133131      14641

ヤング図形による理解

(1+qz)(1+q2z)(1+q3z)(1+q4z)が表す整数の分割を図示すると
!FORMULA[56][-169372375][0]が示す分割 (1+qz)(1+q2z)(1+q3z)(1+q4z)が示す分割
組合せ論と母関数2:自然数の分割 の公式3で述べたように、異なる自然数への分割の数は三角数を引くと、重複を許した分割の数に対応します。これについては後に説明します。
!FORMULA[57][-169372375][0]が示す分割 - 三角数 (1+qz)(1+q2z)(1+q3z)(1+q4z)が示す分割 - 三角数
上図のグレーの部分を引くと
!FORMULA[58][-169372375][0]が示す分割- 三角数 (1+qz)(1+q2z)(1+q3z)(1+q4z)が示す分割- 三角数
グレーの点線の輪郭からわかるように、zの項に対応した長方形が z:3×1, z2:2×2, z3:1×3 のように定まり、この長方形に収まるヤング図形が並んでいることがわかります。m×nの長方形に収まるヤング図形は大きさがm以下(0を含む)の自然数を用いた、個数がn以下の分割を表します。

多重集合の性質

異なる要素をとる方法の数と、重複を許してとる方法の数は対応させることができます。例えば(1,2,3)から2つ重複を許してとる組み合わせは
((1,1),(1,2),(1,3),(2,2),(2,3),(3,3))
これは(1,2,3,4)から異なる2つを選ぶ方法に以下のような処理をすることで得られます。
((1,2),(1,3),(1,4),(2,3),(2,4),(3,4))((0,1),(0,1),(0,1),(0,1),(0,1),(0,1))
(1,2,..n)から異なるk個をとる組み合わせの数は(nk)であり、重複してk個とる組み合わせは((nk))=(n+k1k)となります。

q二項定数

ここでm×nの長方形に含まれるヤング図形を生成するqの母関数をq二項定数とよび
(m+nn)q
と書きます。m+n は長方形の外周の長さです。そうすると
(41)q=(43)q=1+q+q2+q3(42)q=1+q+2q2+q3+q4
これを用いると
(1+qz)(1+q2z)(1+q3z)(1+q4z)=1+(41)qqz+(42)qq3z2+(43)qq6z3+q10z4
同様にして一般に
(qz)n=k=1n(1+qkz)=k=0n(nk)qqk(k+1)/2zk

q数,q階乗

q数

以下のようなものを考えq数と呼びます
[1]q=1[2]q=1+q[3]q=1+q+q2..

q階乗

以下のようなものを考えq階乗と呼びます
[3]q!=(1+q)(1+q+q2)[4]q!=(1+q)(1+q+q2)(1+q+q2+q3)[5]q!=(1+q)(1+q+q2)(1+q+q2+q3)(1+q+q2+q3+q4)..

q二項定数の表現

この図で!FORMULA[87][1620926347][0] 
が説明できるはず・・・ この図で(53)q=[5]q![3]q! [2]q!
が説明できるはず・・・

まず0を含む分割は図4の左図のようになり、わかりにくいので1を最小とする分割にします。この2つは対応づけることができます。右図を考えます。
3×2の長方形はサイズ5の階段からサイズ2,3の階段を引いたものになります。実は数式としては
(nk)q=[n]q![k]q! [nk]q!
が成り立ちます。それをヤング図形で直感的に示せないかと思い、図4を思いついたのですが、少しつながりが分からない部分があり考え中です。

投稿日:331
更新日:331
OptHub AI Competition

この記事を高評価した人

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

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

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

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

投稿者

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

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中
  1. はじめに
  2. qポッホハマー記号
  3. 前回までのあらすじ 略記ver
  4. 有限積の場合
  5. 表による理解
  6. ヤング図形による理解
  7. 多重集合の性質
  8. q二項定数
  9. q数,q階乗
  10. q二項定数の表現