q二項係数

同義語:q-binomial coefficientGauss多項式Gaussian polynomial

概要

q二項係数(q-binomial coefficient)とは、二項係数の分子・分母の整数 $m$ を $q$ 整数 $1+q+\dots+q^{m-1}$ に置き換えた $\binom{n}{k}_q=\prod_{i=0}^{k-1}\frac{1-q^{n-i}}{1-q^{i+1}}$ である。$0$ 以上の整数を係数とする次数 $k(n-k)$ の多項式で、$q=1$ で二項係数に戻る。$0$ と $1$ の並びの転倒数の母関数、$k$ 行 $n-k$ 列の箱に入る Young 図形の母関数であり、$q$ が素数冪のときは有限体 $\mathbb{F}_q$ 上の $n$ 次元空間の $k$ 次元部分空間の個数に等しい。$q$-Pascal の漸化式、$q$ 二項定理、$yx=qxy$ をみたす変数の二項定理が成り立つ。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 二項係数, 有限体, 形式的冪級数, Young図形

q二項係数(q-binomial coefficient)とは、二項係数 $\binom{n}{k}$ の分子と分母の整数 $m$ を $q$ 整数 $1+q+\dots+q^{m-1}$ に置き換えた $q$ の多項式
$$ \binom{n}{k}_q=\frac{(1-q^n)(1-q^{n-1})\cdots(1-q^{n-k+1})}{(1-q)(1-q^2)\cdots(1-q^k)} $$
である。Gauss 多項式(Gaussian polynomial)ともいう。$q=1$ とおくと二項係数に戻り、係数はすべて $0$ 以上の整数になる。
この多項式には 3 つの読み方がある。第一に、$0$ と $1$ の並びを「$1$ が $0$ より前にある組の個数」で重みを付けて数えた母関数である。第二に、$k$ 行 $n-k$ 列の箱に入る Young図形 を大きさで数えた母関数である。第三に、$q$ が素数冪のとき、有限体 $\mathbb{F}_q$ 上の $n$ 次元空間の $k$ 次元部分空間の個数である。二項係数が「$n$ 元集合の $k$ 元部分集合の個数」であるのに対し、$q$ 二項係数は「$\mathbb{F}_q^n$ の $k$ 次元部分空間の個数」であり、集合の数え上げを有限体上の線形代数に移す $q$ 類似の代表例である。
この記事では、$q$ 二項係数を定義し、$q$-Pascal の漸化式、上の 3 つの解釈、$q$ 二項定理とその逆数の形、$q$-Vandermonde の恒等式、$yx=qxy$ をみたす非可換な変数の二項定理を証明する。

定義

$q$ を不定元とし、整数 $m\ge0$ について
$$ [m]_q:=1+q+\dots+q^{m-1}=\frac{1-q^m}{1-q},\qquad [m]_q!:=[1]_q[2]_q\cdots[m]_q $$
とおく($[0]_q=0$、$[0]_q!=1$)。$[m]_q$ を $q$ 整数、$[m]_q!$ を $q$ 階乗 という。

q二項係数

整数 $n\ge0$ と $k$ について、$0\le k\le n$ のとき
$$ \binom{n}{k}_q:=\frac{[n]_q!}{[k]_q!\,[n-k]_q!}=\prod_{i=0}^{k-1}\frac{1-q^{n-i}}{1-q^{i+1}} $$
と定め、$k<0$ または $k>n$ のとき $\binom{n}{k}_q:=0$ と定める。これを $q$ 二項係数 という。

2 つの式が等しいのは、$[n]_q!/[n-k]_q!=[n]_q[n-1]_q\cdots[n-k+1]_q$ の各因子と $[k]_q!$ の各因子の分母 $1-q$ が約分されるからである。定義の段階では $\binom{n}{k}_q$ は $q$ の有理式であり、多項式であることは次の節で示す。定義から $\binom{n}{k}_q=\binom{n}{n-k}_q$、$\binom{n}{0}_q=\binom{n}{n}_q=1$ である。

小さい値

$\binom{2}{1}_q=1+q$、$\binom{3}{1}_q=1+q+q^2$、
$$ \binom{4}{2}_q=\frac{(1-q^4)(1-q^3)}{(1-q)(1-q^2)}=(1+q^2)(1+q+q^2)=1+q+2q^2+q^3+q^4 . $$
係数の和は $6=\binom{4}{2}$ で、$q=2$ を代入すると $35$ になる。

$q$-Pascal の漸化式と多項式であること

q-Pascal の漸化式

$n\ge1$ と全ての整数 $k$ について
$$ \binom{n}{k}_q=\binom{n-1}{k}_q+q^{\,n-k}\binom{n-1}{k-1}_q=q^{k}\binom{n-1}{k}_q+\binom{n-1}{k-1}_q . $$

$q$ 整数の分解

$k\le0$ または $k\ge n$ のときは、どの辺も $\binom{n}{k}_q$ と同じ値($0$ か $1$)になることを直接確かめられる。$1\le k\le n-1$ とする。共通因子 $C:=[n-1]_q!/([k]_q!\,[n-k]_q!)$ をくくり出すと
$$ \binom{n-1}{k}_q=C\,[n-k]_q,\qquad \binom{n-1}{k-1}_q=C\,[k]_q $$
である。$q$ 整数の定義から
$$ [n-k]_q+q^{n-k}[k]_q=(1+\dots+q^{n-k-1})+(q^{n-k}+\dots+q^{n-1})=[n]_q $$
であり、同様に $q^k[n-k]_q+[k]_q=[n]_q$ である。$C[n]_q=\binom{n}{k}_q$ なので 2 つの等式が従う。$\square$

多項式としての性質

$0\le k\le n$ のとき、$\binom{n}{k}_q$ は $0$ 以上の整数を係数とする $q$ の多項式で、次数はちょうど $k(n-k)$、定数項と最高次の係数は $1$ であり、$q=1$ での値は二項係数 $\binom{n}{k}$ である。さらに係数は左右対称で、$q^{k(n-k)}\binom{n}{k}_{q^{-1}}=\binom{n}{k}_q$ をみたす。

$n$ についての帰納法

$n=0$ では $\binom{0}{0}_q=1$ で成り立つ。$n-1$ まで正しいとすると、prop-qbin-pascal の第 1 式の右辺は係数が $0$ 以上の整数の多項式の和である。$1\le k\le n-1$ のとき、第 1 項の次数は $k(n-1-k)$、第 2 項の次数は $(n-k)+(k-1)(n-k)=k(n-k)$ で、後者が大きく、その最高次の係数は $1$ である。定数項は第 1 項から来て $1$ である。$q=1$ を代入すると二項係数の Pascal の関係式(二項係数 の命題「Pascal の関係式」)と同じ漸化式になるので、値は $\binom{n}{k}$ である。
対称性:定義の積の式で $q$ を $q^{-1}$ に替えると、各因子は $\frac{1-q^{-(n-i)}}{1-q^{-(i+1)}}=q^{\,i+1-(n-i)}\frac{1-q^{n-i}}{1-q^{i+1}}$ となる。指数の和は $\sum_{i=0}^{k-1}(2i+1-n)=k^2-nk=-k(n-k)$ なので、$\binom{n}{k}_{q^{-1}}=q^{-k(n-k)}\binom{n}{k}_q$ である。$\square$

0-1 の並びと箱の中の Young 図形

$0$ と $1$ からなる長さ $n$ の列 $w=w_1\cdots w_n$ で $1$ をちょうど $k$ 個含むものの全体を $W(n,k)$ とする。$i< j$ かつ $w_i=1,\ w_j=0$ となる組 $(i,j)$ を $w$ の 転倒 といい、その個数を $\operatorname{inv}(w)$ と書く。

転倒数による解釈

$0\le k\le n$ について
$$ \binom{n}{k}_q=\sum_{w\in W(n,k)}q^{\operatorname{inv}(w)} . $$

最後の文字で分ける

右辺を $Q(n,k)$ とおく。$Q(n,0)=Q(n,n)=1$(並びは 1 つで転倒はない)。$1\le k\le n-1$ とし、$w\in W(n,k)$ を最後の文字で分ける。$w=u0$ なら $u\in W(n-1,k)$ で、最後の $0$ は $u$ の $k$ 個の $1$ の全てと転倒をなすので $\operatorname{inv}(w)=\operatorname{inv}(u)+k$。$w=u1$ なら $u\in W(n-1,k-1)$ で $\operatorname{inv}(w)=\operatorname{inv}(u)$。よって
$$ Q(n,k)=q^kQ(n-1,k)+Q(n-1,k-1) $$
であり、これは prop-qbin-pascal の第 2 式と同じ漸化式・同じ初期値である。$n$ についての帰納法で $Q(n,k)=\binom{n}{k}_q$ を得る。$\square$

Sta11 は重複集合の置換の転倒数について同じ形の式(Proposition 1.7.1)を証明している。上の定理はその $2$ 種類の文字の場合である。

箱の中の Young 図形

$0\le k\le n$ について、部分の個数が $k$ 以下で各部分が $n-k$ 以下の分割 $\lambda$($k$ 行 $n-k$ 列の箱に入る Young 図形)の全体を $B(k,n-k)$ とすると
$$ \binom{n}{k}_q=\sum_{\lambda\in B(k,n-k)}q^{|\lambda|}. $$

各 $1$ の右にある $0$ を数える

$w\in W(n,k)$ の $1$ を左から $1$ 番目、…、$k$ 番目とし、$i$ 番目の $1$ より右にある $0$ の個数を $\lambda_i$ とする。$0\le\lambda_k\le\dots\le\lambda_1\le n-k$ であり、$\sum_i\lambda_i=\operatorname{inv}(w)$ である。逆に $n-k\ge\lambda_1\ge\dots\ge\lambda_k\ge0$ が与えられると、$i$ 番目の $1$ の右に $\lambda_i$ 個の $0$ が来るように $1$ を置く並びがただ 1 つある($i$ 番目の $1$ の前にある $0$ は $n-k-\lambda_i$ 個)。この対応は全単射なので、thm-qbin-inversions から従う。$\square$

有限体上の部分空間の個数

部分空間の個数

$q$ を素数冪、$0\le k\le n$ とする。$\mathbb{F}_q^n$ の $k$ 次元部分空間の個数は、多項式 $\binom{n}{k}_q$ に数 $q$ を代入した値に等しい。

一次独立な $k$ 個の組を 2 通りに数える

$\mathbb{F}_q^n$ の一次独立なベクトルの組 $(v_1,\dots,v_k)$ の個数を $N$ とする。$v_1$ は $0$ でない $q^n-1$ 通り、$v_i$ は $v_1,\dots,v_{i-1}$ の張る $q^{i-1}$ 元の部分空間の外の $q^n-q^{i-1}$ 通りなので、
$$ N=(q^n-1)(q^n-q)\cdots(q^n-q^{k-1}). $$
一方、組は張る部分空間 $V$($k$ 次元)を決め、$V$ を固定すると同じ議論で $V$ の基底の組は $(q^k-1)(q^k-q)\cdots(q^k-q^{k-1})$ 個ある。$k$ 次元部分空間の個数を $G$ とすると
$$ G=\prod_{i=0}^{k-1}\frac{q^n-q^i}{q^k-q^i}=\prod_{i=0}^{k-1}\frac{q^{n-i}-1}{q^{k-i}-1} =\prod_{i=0}^{k-1}\frac{1-q^{n-i}}{1-q^{i+1}}, $$
最後の等号は分母の因子の並べ替え($i\mapsto k-1-i$)と符号の打ち消しである。これは def-qbin-main の積の式に数 $q$ を代入した値である。$\square$

Sta11 の Proposition 1.7.2 が同じ証明である。同じ数は Grassmann多様体 $\operatorname{Gr}(k,\mathbb{F}_q^n)$ の点の個数でもある。

行簡約階段形との対応

$k$ 次元部分空間は、行簡約階段形の $k\times n$ 行列をただ 1 つもつ。先頭の $1$ の列の位置を固定したとき自由に選べる成分の個数を各行で数えると、箱 $B(k,n-k)$ の中の分割 $\lambda$ が現れ、そのような行列は $q^{|\lambda|}$ 個ある。こうして cor-qbin-box と thm-qbin-subspaces は 1 つの数え上げとして結びつく(Sta11 Proposition 1.7.3 の証明)。

小さい空間

$\mathbb{F}_2^4$ の $2$ 次元部分空間は $\binom{4}{2}_2=1+2+2\cdot4+8+16=35$ 個ある。$\mathbb{F}_q^n$ の $1$ 次元部分空間(射影空間 $\mathbb{P}^{n-1}(\mathbb{F}_q)$ の点)は $\binom{n}{1}_q=1+q+\dots+q^{n-1}$ 個ある。$q=2,3$ の小さい $n$ では、全ての部分空間を書き出して数えた値と一致することを計算機で確かめた。

$q$ 二項定理

q二項定理

$n\ge0$ について、$x,q$ の多項式として
$$ \prod_{i=0}^{n-1}(1+xq^i)=\sum_{k=0}^{n}q^{k(k-1)/2}\binom{n}{k}_q x^k . $$

因子を 1 つずつ掛ける

$n$ についての帰納法。$n=0$ は両辺 $1$。左辺を $P_n(x)$ とすると $P_n(x)=P_{n-1}(x)(1+xq^{n-1})$ なので、帰納法の仮定から $x^k$ の係数は
$$ q^{k(k-1)/2}\binom{n-1}{k}_q+q^{n-1}q^{(k-1)(k-2)/2}\binom{n-1}{k-1}_q . $$
$(k-1)(k-2)/2+n-1=k(k-1)/2+n-k$ なので、これは $q^{k(k-1)/2}\bigl(\binom{n-1}{k}_q+q^{n-k}\binom{n-1}{k-1}_q\bigr)=q^{k(k-1)/2}\binom{n}{k}_q$ である(prop-qbin-pascal の第 1 式)。$\square$

$q=1$ で二項定理 $(1+x)^n=\sum\binom{n}{k}x^k$ に戻る。因子 $q^{k(k-1)/2}$ が要ることは $n=2$ の $(1+x)(1+qx)=1+(1+q)x+qx^2$ で見える(Sta11 (1.87)、pp. 74–75)。

逆数の公式

$j\ge0$ について、$x$ の形式的冪級数(係数は $q$ の多項式)として
$$ \frac{1}{\prod_{i=0}^{j}(1-xq^i)}=\sum_{k\ge0}\binom{j+k}{k}_q x^k . $$

等比級数を展開して分割を数える

各因子を $\frac{1}{1-xq^i}=\sum_{m_i\ge0}x^{m_i}q^{im_i}$ と展開して掛けると、$x^k$ の係数は $m_0+\dots+m_j=k$ をみたす $(m_0,\dots,m_j)$ にわたる $q^{\sum_i im_i}$ の和である。この組は「$i$ を $m_i$ 個含む、$\{0,1,\dots,j\}$ からの $k$ 個の重複組合せ」と 1 対 1 に対応し、それを大きい順に並べたものは部分が $k$ 個以下で各部分が $j$ 以下の分割($0$ の部分を除く)で、大きさは $\sum_i im_i$ である。よって係数は $\sum_{\lambda\in B(k,j)}q^{|\lambda|}$ であり、cor-qbin-box($n=j+k$)から $\binom{j+k}{k}_q$ に等しい。$\square$

Sta11 p. 74 はこの式を $p(j,k,n)$ の母関数として述べている。$j\to\infty$ とすると係数は箱の制限のない分割の母関数 $1/\prod_{i=1}^{k}(1-q^i)$ に近づき、分割の母関数 に現れる積につながる。

さらに 2 つの恒等式

q-Vandermonde の恒等式

$m,n\ge0$ と $0\le k\le m+n$ について
$$ \binom{m+n}{k}_q=\sum_{j}q^{\,j(n-k+j)}\binom{m}{j}_q\binom{n}{k-j}_q . $$
ここで和は $0\le j\le m$ かつ $0\le k-j\le n$ をみたす $j$ にわたる。

並びを前後に切る

$w\in W(m+n,k)$ を最初の $m$ 文字 $u$ と残りの $n$ 文字 $v$ に分け、$u$ の $1$ の個数を $j$ とする。$u\in W(m,j)$、$v\in W(n,k-j)$ で、$w$ の転倒は $u$ の中、$v$ の中、$u$ の $1$ と $v$ の $0$ の組のどれかである。最後の種類は $j\cdot(n-(k-j))$ 個ある。よって $\operatorname{inv}(w)=\operatorname{inv}(u)+\operatorname{inv}(v)+j(n-k+j)$ で、$(u,v)$ を動かして thm-qbin-inversions を両辺に使えばよい。$\square$

$q=1$ で 二項係数 の Vandermonde の公式に戻る。

非可換な二項定理

$R$ を環、$q\in R$ を $R$ の全ての元と可換な元、$x,y\in R$ を $yx=q\,xy$ をみたす元とする。このとき $n\ge0$ について
$$ (x+y)^n=\sum_{k=0}^{n}\binom{n}{k}_q x^ky^{n-k} $$
である。ここで $\binom{n}{k}_q$ は整数係数の多項式に $q$ を代入した $R$ の元である。

隣り合う $yx$ を入れ替える

$(x+y)^n$ を展開すると、$x$ を $k$ 個、$y$ を $n-k$ 個並べた長さ $n$ の語 $u$ 全ての和になる。$u$ の中で $y$ が $x$ より前にある組の個数を $c(u)$ とすると、$u=q^{c(u)}x^ky^{n-k}$ である。実際、$c(u)>0$ なら隣り合う $yx$ があり、それを $q\,xy$ に替えると $c$ がちょうど $1$ 減り、$q$ は中心にあるので前に出せる。$c$ についての帰納法でよい。$y$ を $1$、$x$ を $0$ と読めば $c(u)$ は転倒数であり、$y$ が $n-k$ 個の並びについての和は thm-qbin-inversions から $\binom{n}{n-k}_q=\binom{n}{k}_q$ である。$\square$

例えば $q\in\mathbb{C}^\times$ と、多項式に作用する作用素 $x=$(変数 $t$ を掛ける)、$y=$($t\mapsto qt$ の代入)は $yx=q\,xy$ をみたす。

反例:仮定を外すと成り立たないこと

反例の表
主張外す仮定例何が成り立たなくなるか
thm-qbin-subspaces係数が体である4 元環 $\mathbb{Z}/4\mathbb{Z}$ の $(\mathbb{Z}/4\mathbb{Z})^2$ で、少なくとも一方の成分が奇数のベクトルが生成する部分加群そのような部分加群は $6$ 個あり、$\binom{2}{1}_4=5$ と一致しない
thm-qbin-subspaces部分空間が原点を通る$\mathbb{F}_q^n$ の $k$ 次元アフィン部分空間各部分空間の平行移動が $q^{n-k}$ 個ずつあるので、個数は $q^{n-k}\binom{n}{k}_q$ で、$k< n$ なら $\binom{n}{k}_q$ より大きい
thm-qbin-noncommutative$yx=q\,xy$可換な $x=y=1$、$q=2$(整数の環)$(x+y)^2=4$ だが $\sum_k\binom{2}{k}_2=1+3+1=5$

1 行目:少なくとも一方の成分が奇数のベクトルは $16-4=12$ 個ある。そのようなベクトル $v$ の生成する部分加群 $\{0,v,2v,3v\}$ の中で同じ性質をもつのは $v$ と $3v=-v$ だけなので、部分加群は $12/2=6$ 個である。$q$ 二項係数が部分空間を数えるのは、prf-qbin-subspaces で「部分空間の外の元を選べば一次独立が保たれる」という体の性質を使うからである。3 行目は、$c(u)$ による並べ替えの議論で $q$ の冪が出てこないことによる。

位置づけ

$q$ 二項係数は「$q\to1$ の極限で集合の数え上げに戻る、有限体上の線形代数の数え上げ」という $q$ 類似の見方の入口である(Sta11 §1.3 の終わり、§1.7)。分割の理論では、分割の母関数 や Eulerの分割恒等式 の有限版として現れ、thm-qbin-inverse と thm-qbin-binomial はその代表である。有限体上の幾何では、Grassmann多様体 の点の個数であり、rem-qbin-echelon の先頭の $1$ の位置による分類は、その点を $q^{|\lambda|}$ 個ずつの組に分ける。非可換な二項定理は、$yx=qxy$ で定まる量子平面の環の基本的な計算である。

関連項目

参考文献

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する