q-二項係数 - 数学の命題示しました

この記事では $q$ -二項係数を組合せ的に定義し，その値を求めます．

非負整数 $m,n$ が与えられているとします．
長さ1の水平な線分と垂直な線分を使って作れる，点 $(0,n)$ から点 $(m,0)$ への最短路の個数は，二項係数を使って
$\binom{m+n}{n}$
と表されます．図1はそのような最短路の例です．

定義と例

$q$ -二項係数は二項係数の拡張です．まず一つ必要な定義をします．
点 $(0,n)$ から点 $(m,0)$ への最短路 $P$ に対してその面積 ${\rm area}(P)$ を，路 $P$ と， $x$ 軸， $y$ 軸で囲まれた部分の面積だと定義します．
例えば図1の路を $P$ とすると，その面積は ${\rm area}(P)=14$ です．例えば ${\rm area}(P)$ は図2における緑色の部分の面積に対応しています．

面積を使って $q$ -二項係数を次のように定義します．
定義( $q$ -二項係数)
非負整数 $m,n$ に対し，
$\binom{m+n}{n}_q\triangleq\sum_{P:(0,m){\rm to}(n,0)} q^{{\rm area}(P)}$
を， $m+n, n$ に対する $q$ -二項係数という．
ただし和の添字は， $(0,m)$ から $(n,0)$ への最短路全てについての和をとることを意味する．

$q$ -二項係数は， $q=1$ のとき通常の二項係数に一致し，その意味で通常の二項係数の一般化となっています．
例として $m=2, n=2$ の場合について定義を確認してみます．
点 $(0,2)$ と点 $(2,0)$ を結ぶ最短路は六つあり，面積0, 1, 3, 4のものがそれぞれ一つづつ，面積2のものが二つあります．詳しくは表1を見てください．
よって定義から $4,2$ に対する $q$ -二項係数は，
$\binom{4}{2}_q=1+q+2q^2+q^3+q^4$ です．

表1: 点 $(0,2)$ と点 $(2,0)$ を結ぶ最短路の一覧と，その面積．

$P$	${\rm area}(P)$
	0
	1
	2
	2
	3
	4

$q$ -二項係数を求める

与えられた非負整数 $k\leq n$ に対し， $\binom{n}{k}_q$ の値を求めます．

命題1
非負整数 $n,k$ は $1\leq k\leq n$ を満たすとする．そのとき，
$\binom{n+1}{k}_q = q^k\binom{n}{k}_q + \binom{n}{k-1}_q$ .

証明
左辺は点 $(0,k)$ と点 $(n-k+1,0)$ をむすぶ最短路 $P$ について $q^{{\rm area}(P)}$ の和をとったものです．
そのような最短路を，

点 $(0,k)$ から下へ行くもの
点 $(0,k)$ から右へ行くもの

の二つに分けます．
前者の場合，点 $(0,k)$ から下へ伸びている最短路は全て，「点 $(0,k-1)$ と点 $(n-k+1,0)$ をむすぶ最短路」に「点 $(0,k-1)$ から点 $(0,k)$ への線分」をつけたものになっています．図3は前者の場合の路の模式図です．

「点 $(0,k-1)$ から点 $(0,k)$ への線分」をつける前と後で面積は変化しないので，前者に含まれる最短路 $P_1$ について $q^{{\rm area}(P_1)}$ の和をとると，それは $\binom{n}{k-1}_q$ に一致します．

後者の場合，点 $(0,k)$ から右へ伸びている最短路は全て，「点 $(0,k)$ と点 $(n-k,0)$ をむすぶ最短路」を右方向に１だけ平行移動したものになっています．
図4は後者の場合の模式図で，赤い路は点 $(0,k)$ から点 $(n-k+1,0)$ への最短路を表していて，黄色い路は赤い路に対応する，点 $(0,k)$ から点 $(n-k,0)$ への最短路を表しています．

図4: 路が点 $(0,k)$ から右にのびている場合．赤い路は，黄色い路を右に1ずらすことで作られる．

図4: 路が点 $(0,k)$ から右にのびている場合．赤い路は，黄色い路を右に1ずらすことで作られる．

平行移動の前と後で，面積はちょうど $k$ 増加します．よって後者に含まれる最短路 $P_2$ について $q^{{\rm area}(P_2)}$ の和をとると，それは $q^k\binom{n}{k}_q$ に一致します．

以上から，左辺と右辺が等しいことが言えます．（証明終）

命題2
非負整数 $n,k$ は $1\leq k\leq n$ を満たすとする．そのとき，
$\binom{n+1}{k}_q = \binom{n}{k}_q + q^{n-k+1}\binom{n}{k-1}_q$ .

証明
命題1と同様なので省略．

命題3 ( $q$ -二項係数の値)
非負整数 $k\leq n$ に対し，
$\binom{n}{k}_q = \frac{(1-q^{n-k+1})\cdots (1-q^{n})}{(1-q^{k})\cdots (1-q)}$ .

証明
$q\neq 1$ として命題1と命題2を組み合わせると，以下の漸化式を得る．
$\binom{n}{k}_q = \frac{1-q^{n-k+1}}{1-q^k}\binom{n}{k-1}_q$ .
定義より $\binom{n}{0}_q=1$ なので，命題3の主張を得る．（証明終）

この式を見ると，ふつうの二項係数の式
$\binom{n}{k} = \frac{n!}{k!(n-k!)}$ の一般化になっていることがわかります．
実際， $q\to 1$ の極限が，ロピタルの定理などを使うとたぶん計算できて，右辺は $\frac{n!}{k!(n-k!)}$ に一致します．

参考文献：
G. E. Andrews, R. Askey, R. Roy. (1999) "Special Functions." Cambridge university press.