\[ \DeclareMathOperator{\im}{im} \DeclareMathOperator{\rank}{rank} \DeclareMathOperator{\GL}{GL} \DeclareMathOperator{\End}{End} \]
\(q\)-阶乘 和 \(q\)-Pochhammer
定义 \(q\)-整数
\[ (i)_q = \frac{1-q^i}{1-q} \]
定义 \(q\)-阶乘
\[ (n!)_q = \prod_{i=1}^n (i)_q \]
和 \(q\)-Pochhammer 记号
\[ (x;q)_m = \prod_{i=0}^{m-1} (1-q^ix), (x;q)_{-m} = \prod_{i=1}^m \frac1{1+q^{-i}x} \]
那么显然 \[ (n!)_q = \frac{(q;q)_n}{(1-q)^n} \]
\(q\)-二项式定理
定义 \(q\)-二项式系数
\[ \binom nm_q = \frac{(q;q)_n}{ (q;q)_m(q;q)_{n-m} } = \frac{(n!)_q}{(m!)_q((n-m)!)_q} \]
有 \(q\)-二项式定理
\[ \begin{aligned} \frac1{(x;q)_n} &= \sum_{m\ge 0} \binom{n+m-1}m_q x^m \\ (-x;q)_n &= \sum_{m\ge 0} q^{m(m-1)/2} \binom nm_q x^m \end{aligned} \]
证明略，非常经典。
一些计数的对象
I
对 \(\mathbb F_q^n\) 的基计数，即 \(|\GL_n(\mathbb F_q)|\)。
考虑第 \(j\) 个向量可以取的有 \(q^n-q^{j-1}\) 种，故答案
\[ \begin{aligned} &= (q^n-1)(q^n-q)\dots(q^n-q^{n-1}) \\ &= q^{n(n-1)/2} (q-1)^n (n!)_q \end{aligned} \]
II
对 \(\mathbb F_q^n\) 中的 \(m\) 维线性子空间计数。
考虑用 \(k\) 个线性无关向量的个数除以一个子空间的基的个数，即
\[ \begin{aligned} &= \frac{(q^n-1)(q^n-q)\dots(q^n-q^{m-1})}{(q^m-1)(q^m-q)\dots(q^m-q^{m-1})} \\ &= \frac{(q^n-1)(q^{n-1}-1)\dots(q^{n-m+1}-1)}{(q^m-1)(q^{m-1}-1)\dots(q-1)} \\ &= \binom nk_m \end{aligned} \]
III
对 \(\mathbb F_q^{n\times m}\) 中秩为 \(r\) 的矩阵计数。
考虑先选取一组 \(r\times m\) 的基，类似 I 可以得到方案数为
\[ q^{r(r-1)/2}(q-1)^r(r!)_q \binom mr_q \]
然后考虑插入一些不影响秩的向量，可以写出 GF
\[ [x^{n-r}] \prod_{i=0}^r \frac1{1-q^ix} \]
由 \(q\)-二项式定理得其为 \(\binom nr_q\)，故总答案为
\[ q^{r(r-1)/2}(q-1)^r(r!)_q\binom nr_q\binom mr_q \]
也可以从消元的角度来计算。
IV
给定 \(C \in \mathbb F_q^{n\times n}\)，计数矩阵对 \((A, B)\) 满足 \(A, B \in \mathbb F_q^{n\times n}\) 且 \(AB=C\)。
将 \(B, C\) 按列分块，记其第 \(i\) 列分别为 \(B_i, C_i\)，则即方程组
\[ AB_i = C_i \]
考虑先定 \(A\) 再计数 \(B_i\)，注意到若有解，则 \(B_i\) 的个数仅与 \(A\) 的秩相关。
因而我们只需要 \(C_i \in \im(B)\)，即 \(C\) 给出一个 \(\im(B)\) 的子空间。
记 \(r = \rank(C)\)，枚举 \(k = \rank(A) \ge r\)，则我们首先从 \(\im(C)\) 的正交补中选择 \(k-r\) 维，方案数为 \(\binom{n-r}{k-r}_q\)，然后我们只需要计数恰好张成这一子空间的矩阵个数，即等于 \(k\times n\) 且秩为 \(k\) 的矩阵个数。
然后乘上 \(q^{n(n-k)}\) 即可。总共的方案数就是
\[ \binom{n-r}{k-r}_q \binom nk_q (q-1)^k(k!)_q q^{k(k-1)/2+n(n-k)} \]
V
对矩阵对 \((A, B)\) 计数，满足 \(A \in \GL_n(\mathbb F_q), B \in \mathbb F_q^{n\times n}\) 且 \(AB = B\)。
记 \(X=\End(\mathbb F_q^n), G=\GL_n(\mathbb F_q)\)，\(G\) 通过左乘作用在 \(X\) 上，那么有 Burnside 引理
\[ |X/G| = \frac1{|G|} \sum_{g\in G} |X^g| \]
注意到 \(\sum_{g\in G} |X^g|\) 就给出了答案，因此我们只需要计数 \(|X/G|\) 和 \(|G|\)。
后者即 I，前者即本质不同子空间个数。
VI
对于 \(A \in \GL(\mathbb F_q^n)\)，记 \(f(A)\) 为矩阵 \(B\) 的数量，满足 \(B \in \mathbb F_q^{n\times n}\) 且 \(AB = B\)。求出每种不同的 \(f(A)\) 和对应的 \(A\) 的个数。
换一个角度。
将 \(B\) 对列分块，则各列独立，我们只考虑 \(Ab = b\) 的向量个数。
注意到 \(b\) 构成 \(A\) 的 \(1\)-特征子空间 \(\ker(A-I)\)，因此我们考虑枚举 \(\dim \ker(A-I)\) 计数对应的 \(A\) 的个数。
注意到我们容易钦定一些向量 \(b_1, \dots, b_k\) 满足 \(Ab_i=b_i\)，但难以确保 \(b_i\) 恰好张成 \(\ker(A-I)\)。
这启示我们考虑子空间反演。
设 \(f_{n-k}\) 表示给定一个 \(k\) 维子空间，\(\ker(A-I)\) 与之相等的 \(A\) 的个数；\(g_{n-k}\) 表示给定一个 \(k\) 维子空间，\(\ker(A-I)\) 包含之的 \(A\) 的个数。接下来我们会看到这样定义的方便性。
那么有
\[ g_{n-k} = \sum_{d=k}^n \binom{n-k}{d-k}_q f_{n-d} \]
即
\[ g_k = \sum_{d=0}^k \binom kd_q f_d \]
这恰好满足子空间反演的形式。
接下来考虑求 \(g_{n-k}\)。我们任取给定的子空间的一组基，然后从余下的补空间中任取 \(n-k\) 个向量满足它们总共构成一组 \(\mathbb F_q^n\) 的基，设这一矩阵为 \(B'\)。
记 \(C'=AB'\)，那么我们知道 \(C'\) 与 \(A\) 一一对应；又因为 \(B'\) 中有 \(k\) 列是钦定在 \(1\)-特征子空间内的，所以 \(C'\) 的这 \(k\) 列应当与其一致，剩下 \(n-k\) 列只需任取线性无关的向量。
因此，\(g_{n-k} = (q^n-q^k)(q^n-q^{k+1})\dots(q^n-q^{n-1})\)。
接下来就是推导 \(q\)-整式递推的工作了。