メモ: q-二項係数 - noshi91のメモ

q-二項係数や Gaussian binomial coefficient などと呼ばれる概念がある。

詳細は上記のページなどを参照すると良い

基本事項

非負整数 $m, n$ に対し以下の記号を定義する。

\begin{align} \lbrack n \rbrack _ q &:= 1 + q + q ^ 2 + \cdots + q ^ {n - 1} = \frac{1 - q ^ n}{1 - q} \cr\cr \lbrack n \rbrack _ q ! &:= \lbrack 1 \rbrack _ q \lbrack 2 \rbrack _ q \cdots \lbrack n \rbrack _ q \cr\cr \binom{m}{n} _ q &:= \frac{\lbrack m \rbrack _ q !}{\lbrack n \rbrack _ q ! \lbrack m - n \rbrack _ q !} = \frac{(1 - q ^ m)(1 - q ^ {m - 1}) \cdots (1 - q ^ {m - n + 1})}{(1 - q)(1 - q ^ 2) \cdots (1 - q ^ n)} \end{align}

$\binom{m}{n} _ q$ は $q$ の多項式となる (分数が割り切れる)
有限体 $\mathbb{F} _ q$ 上の $n$ 次元ベクトル空間の $k$ 次元部分空間の個数は $\binom{n}{k} _ q$
$0$ を $a$ 個、 $1$ を $b$ 個並べた数列であって転倒数が $k$ のものの個数は $\lbrack q ^ k \rbrack \binom{a + b}{a} _ q$
各要素が $0$ 以上 $m$ 以下で、長さが $n$ 、合計が $k$ の広義単調増加列の個数は $\lbrack q ^ k \rbrack \binom{n + m}{n} _ q$
各要素が $0$ 以上 $m$ 未満で、長さが $n$ 、合計が $k$ の狭義単調増加列の個数は $\lbrack q ^ {k - n (n - 1) / 2} \rbrack \binom{m}{n} _ q$

\begin{align} \prod _ {i = 0} ^ {n - 1} (1 + q ^ i t) = \sum _ {k = 0} ^ {n} q ^ {k (k - 1) / 2} \binom{n}{k} _ q t ^ k \end{align}

$n _ 0, k _ 0 \lt d$ とする。

\begin{align} \binom{n _ 1 d + n _ 0}{k _ 1 d + k _ 0} _ q \equiv \binom{n _1}{k _ 1} \binom{n _ 0}{k _ 0} _ q \pmod {\Phi _ d(q)} \end{align}

$\binom{n _ 1}{k _ 1}$ の部分は通常の二項係数であることに注意。 $\Phi _ d$ は $d$ 番目の円分多項式。

　q-二項係数は、通常の二項係数で数えられる対象を更に何らかのパラメータで分類して、それを母関数として表したものと考えることも出来る。言い換えると、 $q = 1$ を代入すると通常の二項係数と一致する。例えば転倒数の例では、全ての転倒数について数列の個数を足し合わせれば当然 $\binom{a + b}{a}$ 個になるから $\lbrack q ^ k \rbrack \binom{a + b}{a} _ q$ が正解だろうと推測できて、 $\lbrack q ^ k \rbrack \binom{a}{b} _ q$ のようなものが答えになることはあり得ない。

計算について

$q$ が定数なら、通常の二項係数のように階乗とその逆元のテーブルを作れば高速に二項係数が計算できる。ただし、 $n$ が $q$ の $\mathbb{F} _ p$ における位数より大きい場合、q-Lucas の定理を使う必要がある。
$q$ が不定元として、 $\binom{n}{r} _ q$ を $k$ 次まで計算することは FPS の exp と log を用いれば $\mathrm{O}(k \log(k) )$ で行える。

証明

$0$ を $a$ 個、 $1$ を $b$ 個並べてできる全ての数列を考える。これらの転倒数の分布を母関数として表す。すなわち

\begin{align} I (q) := \sum _ {k = 0} ^ {\infty} \left \lvert \left \lbrace 0 \text{ を } a \text{ 個、} 1 \text{ を } b \text{ 個並べてできる、転倒数が } k \text{ の数列} \right \rbrace \right \rvert q ^ k \end{align}

と定義する。

$\lbrace 1, 2, \dots, a + b \rbrace$ の順列の全てについて同様に、その転倒数の分布を母関数として表す。

\begin{align} P (q) := \sum _ {k = 0} ^ {\infty} \left \lvert \left \lbrace \lbrace 1, 2, \dots, a + b \rbrace \text{ の順列のうち、転倒数が } k \text{ であるもの} \right \rbrace \right \rvert q ^ k \end{align}

$P(q)$ を $2$ 通りの方法で計算する。

計算方法 $1$

挿入 DP のように考える。 $\lbrace 1, 2, \dots, t - 1 \rbrace$ までの並びを決めたとき、次に $t$ をどこに差し込むか考えると、 $t$ 通りの選択肢がありそれぞれで転倒数が $0, 1, \dots, t - 1$ 増加する。これは母関数に $1 + q + \dots + q ^ {t - 1} = \lbrack t \rbrack _ q$ を掛けることと同義だから、 $P(q) = \lbrack a + b \rbrack _ q !$ である。

計算方法 $2$

まずは $1, 2, \dots, a$ が順列のどこにあるかを決める。 $1, 2, \dots, a$ 内の並び順はまだ固定しないでおく。選択肢は $\binom{a + b}{a}$ 通りあるが、それぞれについて既に確定した転倒の数を数えるとその母関数は定義より $I(q)$ と一致する。次に $1, 2, \dots, a$ の並びと、 $a + 1, a + 2, \dots, a + b$ の並びをそれぞれ決定する。その結果新たに確定する転倒の数の母関数は計算方法 $1$ と同様に考えればそれぞれ $\lbrack a \rbrack _ q !, \lbrack b \rbrack _ q !$ である。よって $P(q) = I(q) \lbrack a \rbrack _ q ! \lbrack b \rbrack _ q !$ 。

　以上の結果を合わせると $\lbrack a + b \rbrack _ q ! = I(q) \lbrack a \rbrack _ q ! \lbrack b \rbrack _ q !$ となり、 $I(q) = \binom{a + b}{a} _ q$ が従う。

例題

cp-unspoiler