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

はじめに

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

qポッホハマー記号

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

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

べき乗和

\begin{eqnarray} \sum_{n=1}^{\infty} \frac{q^n z}{1-q^n z} = \sum_{n=1}^{\infty} \frac{q^n z^n}{1-q^n} \end{eqnarray}

基本対称式

\begin{eqnarray} (-qz)_{\infty} = \prod_{n=1}^{\infty}(1+q^n z) = \sum_{n=1}^{\infty} \frac{q^{n(n+1)/2}}{(q)_n}z^n \end{eqnarray}
nをm個の異なる自然数に分割する数を$q_m(n)$として
\begin{eqnarray} \frac{q^{m(m+1)/2}}{(q)_m} = \sum_{n=m(m+1)/2}q_m(n)q^n \end{eqnarray}
※和は$m(m+1)/2$以下なら$q_m(n)=0$となるのでどこからでもよい。

完全斉次式

\begin{eqnarray} (qz)_{-\infty} = \frac{1}{(qz)_{\infty}} = \frac{1}{\prod_{n=1}^{\infty}(1-q^n z)}= \sum_{n=1}^{\infty} \frac{q^n}{(q)_n}z^n \end{eqnarray}
nをm個の自然数に分割する数を$p_m(n)$として
\begin{eqnarray} \frac{q^m}{(q)_m} = \sum_{n=m}^{\infty}p_m(n)q^n \end{eqnarray}

z=1のとき

nを異なる自然数に分割する数を$q(n)$、nを自然数に分割する数を$p(n)$として
\begin{eqnarray} (-q)_{\infty} &=& 1 + \sum_{n=1}^{\infty} q(n) q^n \\ \frac{1}{(q)_{\infty}} &=& 1 + \sum_{n=1}^{\infty} p(n) q^n \end{eqnarray}

オイラーの分割恒等式

\begin{eqnarray} (-q)_{\infty} = \frac{1}{(-q;q^2)} \end{eqnarray}

有限積の場合

前回は以下のような無限積
$$ (-qz)_{\infty}=(1+q z)(1+q^2 z)(1+q^3z)~.. $$
を考えました。これは$q,q^2,q^3~..$の基本対称式の母関数であり、$z^m$の係数は
$$ \sum_{j=1}^{\infty}q_m(j)q^j=\frac{q^{m(m+1)/2}}{(q)_m} =\frac{q^{m(m+1)/2}}{(1-q)(1-q^2)(1-q^3)~..(1-q^m)} $$
これの$q^j$の係数は$j$を$m$個の異なる整数に分割する方法の数となります。これが有限積の場合どうなるでしょうか？
$$ (-qz)_n=(1+q z)(1+q^2 z)(1+q^3z)~..(1+q^{n}z) $$
この場合、使っていい整数が$1$から$n$までになります。例えば
$$ (1+qz)(1+q^2z)=1+(q+q^2)z+q^3z^2 $$
は$1,2$を重複なく使って表せる数を表します。$z$の係数はそのうち$1$個を使って表せる数で、$z^2$の係数はそのうち$2$個を使って表せる数に対応します。
\begin{array}{ll} q+q^2&1=1,~2=2\\ q^3&3=1+2 \end{array}
同様に$n=3$のとき
$$ (1+qz)(1+q^2z)(1+q^3z)=1+(q+q^2+q^3)z+(q^3+q^4+q^5)z^2+q^6z^3 $$
\begin{array}{ll} q+q^2+q^3&1=1,~2=2,~3=3\\ q^3+q^4+q^5&3=1+2,~4=1+3,~5=2+3\\ q^6&1+2+3 \end{array}
$n=4$のとき
\begin{array}{ll} (1+qz)(1+q^2z)(1+q^3z)(1+q^4z)=1+(q+q^2+q^3+q^3)z+\\(q^3+q^4+2q^5+q^6+q^7)z^2+(q^6+q^7+q^8+q^9)z^3+q^{10}z^4 \end{array}

\begin{array}{ll} q+q^2+q^3+q^4&1=1,~2=2,~3=3,~4=4\\ q^3+q^4+\textcolor{red}{2q^5}+q^6+q^7&3=1+2,~4=1+3,~\textcolor{red}{5=2+3=1+4},~6=2+4,~7=3+4\\ q^6+q^7+q^8+q^9&6=1+2+3,~7=1+2+4,~8=1+3+4,~9=2+3+4\\ q^{10}&10=1+2+3+4 \end{array}

表による理解

無限積バージョンもそうですが、この式はいわば"祖母"関数であり、$z$についての母関数としてみると、$q$についての母関数が生成する仕組みになっています。表を使って計算の過程を見てみます。
$(1+qz)(1+q^2z) = 1+qz + q^2z(1+qz)$
$$ \begin{array}{lll} 1&\\ q&q^2\\ &q^3\\ \end{array} ~~~\to~~~ \begin{array}{lll} 1&\\ q&q^2\\ q^3\\ \end{array} $$
$(1+qz)(1+q^2z)(1+q^3z) = (1+qz)(1+q^2z) + q^3z(1+qz)(1+q^2z)$
$$ \begin{array}{llll} 1&\\ q&q^2&q^3\\ q^3&&q^4&q^5\\ &&q^6 \end{array} ~~~\to~~~ \begin{array}{lll} 1&\\ q&q^2&q^3\\ q^3&q^4&q^5\\ q^6\\ \end{array} $$
$(1+qz)(1+q^2z)(1+q^3z)(1+q^4z) = (1+qz)(1+q^2z)(1+q^3z) + q^4z(1+qz)(1+q^2z)(1+q^3z)$
$$ \begin{array}{llll} 1&\\ q&q^2&q^3 & q^4\\ q^3&q^4&q^5 &q^5&q^6&q^7\\ q^6&&&q^7&q^8&q^9\\ &&&q^{10} \end{array} ~~~\to~~~ \begin{array}{llllll} 1&\\ q&q^2&q^3 & q^4\\ q^3&q^4&2q^5&q^6&q^7\\ q^6&q^7&q^8&q^9\\ q^{10} \end{array} $$
$q=1$のとき二項定理の表になります。
$$ (1+z)^2 $$
$$ \begin{array}{ll} 1&\\ 1&1\\ &1\\ \end{array} ~~~\to~~~ \begin{array}{ll} 1\\ 2\\ 1\\ \end{array} $$
$$ (1+z)^3 $$
$$ \begin{array}{llll} 1&\\ 2&1\\ 1&2\\ &1 \end{array} ~~~\to~~~ \begin{array}{lll} 1\\ 3\\ 3\\ 1\\ \end{array} $$
$$(1+z)^4$$
$$ \begin{array}{llll} 1&\\ 3&1\\ 3&3\\ 1&3\\ &1 \end{array} ~~~\to~~~ \begin{array}{llllll} 1\\ 4\\ 6\\ 4\\ 1 \end{array} $$

ヤング図形による理解

$(1+qz)(1+q^2z)(1+q^3z)(1+q^4z)$が表す整数の分割を図示すると
$(1+qz)(1+q^2z)(1+q^3z)(1+q^4z)$が示す分割
組合せ論と母関数２：自然数の分割 の公式３で述べたように、異なる自然数への分割の数は三角数を引くと、重複を許した分割の数に対応します。これについては後に説明します。
$(1+qz)(1+q^2z)(1+q^3z)(1+q^4z)$が示す分割 - 三角数
上図のグレーの部分を引くと
$(1+qz)(1+q^2z)(1+q^3z)(1+q^4z)$が示す分割- 三角数
グレーの点線の輪郭からわかるように、$z$の項に対応した長方形が $z : 3 \times 1,~z^2 : 2 \times 2,~z^3 : 1 \times 3$ のように定まり、この長方形に収まるヤング図形が並んでいることがわかります。$m \times n$の長方形に収まるヤング図形は大きさが$m$以下（０を含む）の自然数を用いた、個数が$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$個をとる組み合わせの数は$\dbinom{n}{k}$であり、重複して$k$個とる組み合わせは$\displaystyle\left(\!\!{n\choose k}\!\!\right)=\dbinom{n+k-1}{k}$となります。

q二項定数

ここで$m \times n$の長方形に含まれるヤング図形を生成する$q$の母関数を$q$二項定数とよび
\begin{eqnarray} \dbinom{m+n}{n}_q \end{eqnarray}
と書きます。$m+n$ は長方形の外周の長さです。そうすると
\begin{eqnarray} \dbinom{4}{1}_q &=& \dbinom{4}{3}_q = 1+q+q^2+q^3\\ \dbinom{4}{2}_q &=& 1+q+2q^2+q^3+q^4\\ \end{eqnarray}
これを用いると
\begin{eqnarray} (1+qz)(1+q^2z)(1+q^3z)(1+q^4z) = 1 + \dbinom{4}{1}_q q z + \dbinom{4}{2}_q q^3 z^2 + \dbinom{4}{3}_q q^6 z^3 + q^{10} z^4 \end{eqnarray}
同様にして一般に
\begin{eqnarray} (-qz)_n=\prod_{k=1}^n(1+q^k z) = \sum_{k=0}^n \dbinom{n}{k}_q q^{k(k+1)/2}z^k \end{eqnarray}

q数,q階乗

q数

以下のようなものを考え$q$数と呼びます
\begin{eqnarray} [1]_q &=& 1 \\ [2]_q &=& 1+q \\ [3]_q &=& 1+q+q^2 \\ .. \end{eqnarray}

q階乗

以下のようなものを考え$q$階乗と呼びます
\begin{eqnarray} [3]_q !&=& (1+q)(1+q+q^2) \\ [4]_q !&=& (1+q)(1+q+q^2)(1+q+q^2+q^3) \\ [5]_q !&=& (1+q)(1+q+q^2)(1+q+q^2+q^3)(1+q+q^2+q^3+q^4) \\ .. \end{eqnarray}

q二項定数の表現

この図で$\dbinom{5}{3}_q = \dfrac{[5]_q!}{[3]_q!~[2]_q!}$
が説明できるはず・・・
まず$0$を含む分割は図４の左図のようになり、わかりにくいので１を最小とする分割にします。この２つは対応づけることができます。右図を考えます。
$3 \times 2$の長方形はサイズ$5$の階段からサイズ$2,3$の階段を引いたものになります。実は数式としては
\begin{eqnarray} \dbinom{n}{k}_q = \dfrac{[n]_q!}{[k]_q!~[n-k]_q!} \end{eqnarray}
が成り立ちます。それをヤング図形で直感的に示せないかと思い、図４を思いついたのですが、少しつながりが分からない部分があり考え中です。