組み合わせ論による q-二項係数の定義

帰納的に証明する。

$n=1$ のときは明らかである。

$n=k$ で成立することを仮定する。

$1 , 2 , \cdots , k$ の順列 $a_1 a_2 \cdots a_{k}$ に $k+1$ を挿入する方法は $k+1$ 通りあり，各操作で増える転置数をまとめると次のようになる。

• $a_1$ の手前に挿入：転置数が $k$ 増える。
• $a_2$ の手前に挿入：転置数が $k-1$ 増える。
• ……
• $a_k$ の手前に挿入：転置数が $1$ 増える。
• $a_k$ の後ろに挿入：転置数が $0$ 増える。

よって $k+1$ を挿入することで

$$\sum_{i=1}^{k+1} A_{k+1} (i) = [k]_q! (1+q+q^2+ \cdots + q^k)$$ となる。

$1+q+\cdots + q^k$ は $[k+1]_q$ そのものである。こうして $$\sum_{i=1}^{k+1} A_{k+1} (i) = [k+1]_q!$$ であるため，命題が従う。

$1,2,\cdots , n$ の順列の転倒数を数える。前の定理からこの転倒数の母関数は $[n]_q!$ である。

$1,2, \cdots , k$ が配置されている箇所を $0$ に，$k+1,k+2,\cdots ,n$ が配置されている箇所を $1$ に取り換える。この $0$ と $1$ からなる数字の列の転倒数は $\binom{n}{k}_q$ であった。

こうしてできた順列の転倒数は次の3つの和である。

1. $0$ と $1$ に置き換えた数列の転倒数
2. 元の順列から $1$ から $k$ だけを取り出した際の転倒数
3. 元の順列から $n+1$ から $n$ だけを取り出した際の転倒数

よって $$A_n (i) = \sum_{i_1+i_2+i_3=i} B_{n,k} (i_1) A_{k} (i_2) A_{n-k} (i_3)$$ と表すことができる。

母関数の考え方から $$\binom{n}{k}_q [k]_q! [n-k]_q! = [n]_q !$$ が従う。つまり $$\binom{n}{k}_q = \dfrac{[n]_q!}{[k]_q! [n-k]_q!}$$ が示された。

$k$ の係数を求める。

$1,q,q^2 , \cdots , q^{n-1}$ のうちから $k$ 個を選んだものを $q^{a_1} , q^{a_2} , \cdots , q^{a_k}$ とおく。このとき $a_1 < \cdots < a_k$ である。

ここで $b_i = a_i - i$ とおく。このとき $0 \leqq b_i \leqq n-k$ で，$b_1 \leqq \cdots \leqq b_k$ である。

$b_1,b_2,\cdots , b_k$ と $k \times (n-k)$ マスの格子を左下から右上まで進む経路を次のように対応付ける。

• $1$ 列目で $b_1$ マス目まで上がる。
• $2$ 列目で $b_2$ マス目まで上がる。
• $\cdots$
• $k$ 列目で $b_k$ マス目まで上がる。

このとき，経路の下側のマスの個数は $b_1 + b_2 + \cdots + b_k$ である。

ゆえに $$\sum_{b_1 + \cdots + b_k = i} q^{b_1} q^{b_2} \cdots q^{b_k} = B'_{n,k} (i) q^i$$ となるため， $$\sum_{0 \leqq b_1 \leqq \cdots \leqq b_k \leqq n-k} q^{b_1} q^{b_2} \cdots q^{b_k} = \sum_{i=0}^{n} B'_{n,k} (i) q^i$$ を得る。

$$\begin{aligned} q^{a_1} \cdots q^{a_k} &= q^{b_1} \cdots q^{b_k} \cdot q^{1+2+ \cdots + k}\\ &= q^{b_1} \cdots q^{b_k} \cdot q^{\frac{k(k+1)}{2}} \end{aligned}$$ であるため，$x^k$ の係数は $$q^{\frac{k(k+1)}{2}}\sum_{i=0}^{n} B'_{n,k} (i) q^i = \binom{n}{k}_q q^{\frac{k(k+1)}{2}}$$ である。