q-number: (下标qq可以省略)

[k]q=∑i=0k−1qi={1−qk1−q,q≠1k,q=1[k]_{q} = \sum_{i=0}^{k-1} q^{i}= \begin{cases} \frac{1-q^{k}}{1-q}, & q \neq 1 \\ k, & q = 1 \end{cases}

[n]q!=[1]q[2]q⋯[n]q[n]_{q}! = [1]_{q}[2]_{q}\cdots[n]_{q}

高斯二项式系数:

[mr]={[m]q![r]q![m−r]q!,r≤m0,r>m\begin{bmatrix} m \\ r \end{bmatrix}= \begin{cases} \frac{[m]_{q}!}{[r]_{q}![m-r]_{q}!}, & r\leq m \\ 0 , & r > m \end{cases}

也被称为q-二项式系数

基本性质:

[mr]=[mm−r]\begin{bmatrix} m \\ r \end{bmatrix} = \begin{bmatrix} m \\ m -r \end{bmatrix}

定理1:设qq是有限域Fqn\mathbb{F}_{q}^{n}的阶，则

[nj]=n维向量空间Fqn中j维子空间的个数\begin{bmatrix} n \\ j \end{bmatrix}= n \text{维向量空间} \mathbb{F}_{q}^{n} \text{中} j \text{维子空间的个数}

定理1的证明 设 V=FqnV = \mathbb{F}_q^n。当 j=0j=0 时，[n0]=1\begin{bmatrix} n \\ 0 \end{bmatrix} = 1，且 VV 中只有唯一的 0 维子空间，此情形得证。

当 j≥1j \ge 1 时，为得到一个 jj 维子空间，我们需要选取 jj 个线性无关的向量构成一组基。

  • 第一个基向量 v1v_1 可以是任意非零向量，有 qn−1q^n - 1 种选择；
  • 第二个基向量 v2v_2 不能在 v1v_1 张成的 1 维子空间中（该子空间有 qq 个元素），故有 qn−qq^n - q 种选择；
  • 第三个基向量 v3v_3 不能在 v1,v2v_1, v_2 张成的 2 维子空间中（该子空间有 q2q^2 个元素），故有 qn−q2q^n - q^2 种选择；
  • 一般地，在选好前 ii 个基向量后，第 (i+1)(i+1) 个基向量不能在前 ii 个基向量张成的 ii 维子空间中（该子空间有 qiq^i 个元素），故有 qn−qiq^n - q^i 种选择。

因此，在 Fqn\mathbb{F}_q^n 中选取 jj 个线性无关向量的方式共有

(qn−1)(qn−q)(qn−q2)…(qn−qj−1)(q^n - 1)(q^n - q)(q^n - q^2) \dots (q^n - q^{j-1})

种。

然而，许多这样的 jj 元组张成同一个子空间。我们需要用 上式 除以同一个 jj 维子空间的不同基的个数。而一个 jj 维子空间的基的个数，本质上就是将 上式 中的 nn 替换为 jj，即

(qj−1)(qj−q)(qj−q2)…(qj−qj−1)(q^j - 1)(q^j - q)(q^j - q^2) \dots (q^j - q^{j-1})

因此，不同 jj 维子空间的个数为

(qn−1)(qn−q)(qn−q2)…(qn−qj−1)(qj−1)(qj−q)(qj−q2)…(qj−qj−1)= q⋅q2…qj−1⋅(qn−1)(qn−1−1)…(qn−j+1−1)q⋅q2…qj−1⋅(qj−1)(qj−1−1)…(q−1)= [nj],\begin{aligned} & \frac{(q^n - 1)(q^n - q)(q^n - q^2) \dots (q^n - q^{j-1})}{(q^j - 1)(q^j - q)(q^j - q^2) \dots (q^j - q^{j-1})} \\ = \ & \frac{q \cdot q^2 \dots q^{j-1} \cdot (q^n - 1)(q^{n-1} - 1) \dots (q^{n-j+1} - 1)}{q \cdot q^2 \dots q^{j-1} \cdot (q^j - 1)(q^{j-1} - 1) \dots (q - 1)} \\ = \ & \begin{bmatrix} n \\ j \end{bmatrix}, \end{aligned}

这正是高斯二项式系数的定义。

命题 存在两条 q-帕斯卡公式：

[nj]=[n−1j−1]+qj[n−1j]\begin{bmatrix} n \\ j \end{bmatrix} = \begin{bmatrix} n-1 \\ j-1 \end{bmatrix} + q^j \begin{bmatrix} n-1 \\ j \end{bmatrix}

和

[nj]=qn−j[n−1j−1]+[n−1j],\begin{bmatrix} n \\ j \end{bmatrix} = q^{n-j} \begin{bmatrix} n-1 \\ j-1 \end{bmatrix} + \begin{bmatrix} n-1 \\ j \end{bmatrix},

其中 1≤j≤n−11 \le j \le n-1。

证明 对任意 1≤j≤n−11 \le j \le n-1，有

[n]=1+q+⋯+qn−1=(1+q+⋯+qj−1)+qj(1+q+⋯+qn−j−1)=[j]+qj[n−j],\begin{aligned} [n] &= 1 + q + \dots + q^{n-1} \\ &= (1 + q + \dots + q^{j-1}) + q^j (1 + q + \dots + q^{n-j-1}) \\ &= [j] + q^j [n-j], \end{aligned}

于是

[nj]=[n]![j]![n−j]!=[n−1]![n][j]![n−j]!=[n−1]!([j]+qj[n−j])[j]![n−j]!=[n−1]![j−1]![n−j]!+qj[n−1]![j]![n−j−1]!=[n−1j−1]+qj[n−1j],\begin{aligned} \begin{bmatrix} n \\ j \end{bmatrix} &= \frac{[n]!}{[j]![n-j]!} = \frac{[n-1]![n]}{[j]![n-j]!} \\ &= \frac{[n-1]!([j] + q^j[n-j])}{[j]![n-j]!} \\ &= \frac{[n-1]!}{[j-1]![n-j]!} + q^j \frac{[n-1]!}{[j]![n-j-1]!} \\ &= \begin{bmatrix} n-1 \\ j-1 \end{bmatrix} + q^j \begin{bmatrix} n-1 \\ j \end{bmatrix}, \end{aligned}

这就是第一条 q-帕斯卡公式。利用系数的对称性

[nj]=[nn−j]\begin{bmatrix} n \\ j \end{bmatrix} = \begin{bmatrix} n \\ n-j \end{bmatrix}

可得另一条恒等式：

[nj]=[nn−j]=[n−1n−j−1]+qn−j[n−1n−j]=[n−1j]+qn−j[n−1j−1].\begin{aligned} \begin{bmatrix} n \\ j \end{bmatrix} &= \begin{bmatrix} n \\ n-j \end{bmatrix} = \begin{bmatrix} n-1 \\ n-j-1 \end{bmatrix} + q^{n-j} \begin{bmatrix} n-1 \\ n-j \end{bmatrix} \\ &= \begin{bmatrix} n-1 \\ j \end{bmatrix} + q^{n-j} \begin{bmatrix} n-1 \\ j-1 \end{bmatrix}. \end{aligned}

定理2（q-二项式系数的组合解释）

设 Pj,n−j\mathcal{P}_{j, n-j} 是由 jj 个 0 和 n−jn-j 个 1 组成的所有长度为 nn 的排列集合。对于 π∈Pj,n−j\pi \in \mathcal{P}_{j, n-j}，定义 inv(π)\text{inv}(\pi) 为 π\pi 的逆序对数。则有：

[nj]q=∑π∈Pj,n−jqinv(π) \begin{bmatrix} n \\ j \end{bmatrix}_q = \sum_{\pi \in \mathcal{P}_{j, n-j}} q^{\text{inv}(\pi)}

证明

令 S(n,j)=∑π∈Pj,n−jqinv(π)S(n, j) = \sum_{\pi \in \mathcal{P}_{j, n-j}} q^{\text{inv}(\pi)}。我们要证明 S(n,j)S(n, j) 满足 q-二项式系数的递推关系和边界条件。

  • 当 j=0j=0 时（全为 1），只有一种排列，逆序数为 0。S(n,0)=1=[n0]S(n, 0) = 1 = \begin{bmatrix} n \\ 0 \end{bmatrix}。

  • 当 j=nj=n 时（全为 0），只有一种排列，逆序数为 0。S(n,n)=1=[nn]S(n, n) = 1 = \begin{bmatrix} n \\ n \end{bmatrix}。
    考虑 Pn,j\mathcal{P}_{n, j} 中的任意排列 π=x1x2…xn\pi = x_1 x_2 \dots x_n。根据最后一个元素 xnx_n 的值，我们将集合划分为两类情况：

  • 情况 A：最后一个元素是 1 (xn=1x_n = 1)

    • 去掉末尾的 1，剩下的前缀是长度为 n−1n-1、包含 jj 个 0 的排列（属于 Pn−1,j\mathcal{P}_{n-1, j}）。
    • 由于 1 是最大元素且在最后，它不与前面的任何元素构成逆序对（逆序对要求大数在小数前面）。
    • 因此，逆序数不变。此部分的生成函数为：

      1⋅S(n−1,j)=S(n−1,j)1 \cdot S(n-1, j) = S(n-1, j)

  • 情况 B：最后一个元素是 0 (xn=0x_n = 0)

    • 去掉末尾的 0，剩下的前缀是长度为 n−1n-1、包含 j−1j-1 个 0 的排列（属于 Pn−1,j−1\mathcal{P}_{n-1, j-1}）。
    • 由于 0 是最小元素且在最后，它与前面所有的 1 都构成逆序对。
    • 前面 1 的个数共有 n−jn - j 个。因此，增加末尾的 0 会增加 n−jn-j 个逆序对。
    • 此部分的生成函数为：

      qn−j⋅S(n−1,j−1)q^{n-j} \cdot S(n-1, j-1)

将两种情况相加，得到总的生成函数：

S(n,j)=S(n−1,j)+qn−jS(n−1,j−1)S(n, j) = S(n-1, j) + q^{n-j} S(n-1, j-1)

这正是第二条 q-帕斯卡公式：

[nj]=[n−1j]+qn−j[n−1j−1]\begin{bmatrix} n \\ j \end{bmatrix} = \begin{bmatrix} n-1 \\ j \end{bmatrix} + q^{n-j} \begin{bmatrix} n-1 \\ j-1 \end{bmatrix}

由于 S(n,j)S(n, j) 与 [nj]\begin{bmatrix} n \\ j \end{bmatrix} 满足相同的递推关系和边界条件，故定理得证。

参考：
高斯二项式系数小结 | Distant Yesterday
q高斯二项式 - 知乎