联考题考这个♿不会就来学了
首先给出对其的定义。
对于一个对象 \(u\)，构造关于 \(q\) 的某表达式 \(f(q)\)，使得：
\[\lim_{q\to 1}f(q)=u
\]
然而这个可能没有很大用。真正 OI 有用的还是要实际一点。
定义
\[[n]_q=\frac{1-q_n}{1-q},[n]_q!=\prod_{i=1}^n[i]_q\\ \binom{n}{m}_q=\frac{[n]_q!}{[m]_q![n-m]_q!}
\]
把 \(f(x)f(qx)f(q^2x)\dots f(q^{n-1}x)\) 记为 \(f^{(n;q)}(x)\)，比如
\[(x+y)^{(n;q)}=(x+y)(x+qy)\dots(x+q^{n-1}y)
\]
从定义不难看出若干性质。
\[[a+b]_q=[a]_q+q^a[b_q],[ab]_q=[a]_q[b]_{q^a}\\
[-n]_q=-q^{-n}[n_q],[n]_{1/q}=q^{1-n}[n]_q,[n]_{1/q}!=q^{-\binom{n}{2}}[n]_q\\
\binom{n}{k}_{1/q}=q^{-k(n-k)}\binom{n}{k}_q,\binom{n}{k}_q=\binom{n}{n-k}_q\\
\binom{n}{k}_q=\binom{n-1}{k-1}_q+q^k\binom{n-1}{k}_q=q^{n-k}\binom{n-1}{k-1}_q+\binom{n-1}{k}_q
\]
由于
\[\Delta \binom{x}{k}_q=q^{x-k+1}\binom{x}{k-1}_q
\]
有
\[\sum q^{x}\binom{x}{k}\delta x=q^k\binom{x}{k+1}_q\\
\sum_{i\le n} q^{x}\binom{x}{k}=q^k\binom{n}{k+1}_q,\sum_{x=0}^mq^x\binom{x+k}{k}=\binom{k+m+1}{k+1}\\
\]
q-二项式系数的若干恒等式性质
q-二项式定理。
\[(x+y)^{(n;q)}=\sum_{k}\binom{n}{k}_qq^{\binom{k}{2}}x^{n-k}y^k
\]
证明：
显然只需考虑 \(x=1\)。
考察
\[(1+z)^{(n;y)}=F_y(z)=\prod_{i=0}^{n-1}(1+y^iz)\\
F_y(z)=\frac{1+z}{1+y^nz}\prod_{i=0}^{n-1}(1+y^{i+1}z)=\frac{1+z}{1+y^nz}F_y(yz)\\
(1+y^nz)F_y(z)=(1+z)F_y(yz)\\
\sum_{i=0}^nf_iz^i+f_iy^nz^{i+1}=\sum_{i=0}^n f_iy^iz^i+f_iy^iz^{i+1}\\
(1-y^i)f_i=f_{i-1}(y^{i-1}-y^n)\\
f_i=\frac{y^{i-1}-y^n}{1-y^i}f_{i-1}
\]
展开，上面每项提取 \(y^{i-1}\) 即证。
q-Lucas 定理
令 \(a=\delta_q(p)\) ，即 \(\min(\{a|q^a\equiv 1\pmod p\})\)。
Lemma：
\[\forall k\in(0,a),\binom{a}{k}_q\equiv0\pmod p
\]
证明：注意到 \([a]_q!=0\)。
推论：
\[(1+z)^{(a;q)}\equiv 1+z^a\pmod p
\]
证明：
\[(1+z)^{(a;q)}=\sum_k\binom{a}{k}_qq^{\binom{k}{2}}z^k
\]
唯一有贡献的是 \(k=0\) 和 \(k=a\)，为 \(1\)，即证。
q-Lucas Theorem：
\[q^{\binom{m}{2}}\binom{n}{m}_q\equiv\binom{\lfloor n/a\rfloor}{\lfloor m/a\rfloor}q^{\binom{m\bmod a}{2}}\binom{n\bmod a}{m\bmod a}_q\pmod p
\]
证明：
\[q^{\binom{m}{2}}\binom{n}{m}_q=[z^m](1+z)^{(n;q)}\\
\equiv [z^m]\left((1+z)^{(a;q)}\right)^{\lfloor n/a\rfloor}(1+z)^{(n\bmod a;q)}\pmod p\\
\equiv [z^m](1+z^a)^{\lfloor n/a\rfloor}(1+z)^{(n\bmod a;q)}\pmod p\\
\equiv \left([z^{\lfloor m/a\rfloor}](1+z)^{\lfloor n/a\rfloor}\right)\left([z^{m\bmod a}](1+z)^{(n\bmod a;q)}\right)\pmod p\\
\binom{\lfloor n/a\rfloor}{\lfloor m/a\rfloor}q^{\binom{m\bmod a}{2}}\binom{n\bmod a}{m\bmod a}_q
\]
代数地证明 q-二项式系数为整数
这里先给个分圆多项式定义：
\[\zeta_d=\cos \frac{2\pi d}{n}+i\sin\frac{2\pi d}{n},\gcd(d,n)=1(\iff ord(\zeta_d)=n)\\
\Phi_n(x)=\prod_{(d,n)=1,d\le n}(x-\zeta_d)\\
\]
为了刻画整数 q-模拟，有：
\[\prod_{d|n} \Phi_d(x)=x^n-1\\
\]
证明：
\[RHS=(x-\zeta_1)(x-\zeta_1^2)\dots(x-\zeta_1^n)\\
\because\forall k\in[1,n],ord(\zeta_1^k)\mid n\\
\therefore (x-\zeta_1^k)\mid\prod_{d|n}\Phi_d(x)\\
\therefore (x^n-1)\mid\prod_{d|n}\Phi_d(x)\\
\because \gcd(\Phi_{d_1}(x),\Phi_{d_2}(x))=1,\forall d\mid n,\Phi_d(x)\mid (x^n-1)\\
\therefore \prod_{d|n}\Phi_d(x)\mid(x^n-1)
\]
两者均为首一多项式，即证。
Gause Lemma:两个本原多项式的乘积仍然是本原多项式。本原多项式的定义是系数最大公约数为一的多项式。
有：（即分圆多项式系数是整数）
\[\forall n\in\mathbb{N}^+,\Phi_n(x)\in\mathbb{Z}[x]
\]
证明：
\(n=1\) 时为 \(x-1\)，成立。
归纳，
\[x^n-1=\Phi_n(x)\prod_{d|n,d<n} \Phi_d(x)\\
\]
根据归纳假设， \(\Phi_d(x)\) 为本原多项式，故
\[\prod_{d|n,d<n} \Phi_d(x)
\]
为本原多项式。
这个和左项都是首一本原多项式，即证。
那么我们可以证明了！
\[[n]_q=\prod_{d|n,d>1}\Phi_d(q)\\
[n]_q!=\prod_{d\ge 2}\Phi_d(q)^{\lfloor n/d\rfloor}
\]
然后我们发现 \(\lfloor n/d\rfloor\ge \lfloor m/d\rfloor+\lfloor(n-m)/d\rfloor\)，这样就（类似 \(q\to 1\) 勒让德定理）地完成了证明。