q-analog 和 q-binomial

· · 个人记录

模拟赛四道题三道是计数，不得不来看一看这个。

当一个表达式 f(q) 满足 \lim_{q\to1}f(q)=c 时，称它是 c 的 q-analog。
例如 [n]_q=\frac{1-q^n}{1-q}=(1+q+q^2+\cdots+q^{n-1}) 是 n 的 q-analog，因为它满足上述定义。

一个自然数 n 的 q-factorial 为 \underset{i=1}{\overset{n}{\prod}}[i]_q，记作 [n]_q!。
记 (q)_k 为 [k]_q!(1-q)^k。

再定义 \left(\begin{matrix}n\\m\end{matrix}\right)_q=\frac{[n]_q!}{[m]_q![n-m]_q!}，称作 q-binomial coefficient，或 Gaussian polynomial coefficient。
定义当 n<m 时，上述值为 0。
直接展开可得：

\left(\begin{matrix}n\\m\end{matrix}\right)_q=\frac{\prod_{i=n-m+1}^n\left(1-q^i\right)}{\prod_{i=1}^m\left(1-q^i\right)}

当 n\to\infin 时，上述值是确定的：

\left(\begin{matrix}\infin\\m\end{matrix}\right)_q=\lim_{n\to\infin}\left(\begin{matrix}n\\m\end{matrix}\right)_q=\frac{1}{[m]_q!(1-q)^m}

即便 q-binomial coefficient 有分数的形式，我们依然可以证明它是整系数多项式。

对于 n\in\mathbb N 和 a_1,a_2,\dots a_k\in\mathbb N,a_1+a_2+\cdots+a_k=n，其中 k\ge 2，定义其 q-multinomial coefficient 为：

\left(\begin{matrix}n\\a_1,a_2,\dots a_k\end{matrix}\right)_q=\frac{[n]_q!}{[a_1]_q![a_2]_q!\cdots[a_k]_q!} $$e_q(z)=\sum_{n=0}^{\infin}z^n\frac{(1-q)^n}{(1-q^n)(1-q^{n-1})\cdots(1-q)}$$ 长度为 $n$ 的排列的逆序对的生成函数，即 $\sum_{\pi\in S_n}q^{\operatorname{inv}(\pi)}$，为 $[n]_q!$。 证明：考虑每个数开头的逆序对个数，列成表，记作 $a$。例如 $\pi=6\ 4\ 2\ 3\ 1\ 5$ 的逆序对表为 $a=(5,3,1,1,0,0)$。可以证明 $\pi$ 与 $a$ 之间构成双射（从前往后确定）。 所以有： $$\begin{aligned}\sum_{\pi\in S_n}q^{\operatorname{inv}(\pi)}&=\sum_{a_1=0}^{n-1}\sum_{a_2=0}^{n-2}\cdots\sum_{a_n=0}^{0}q^{a_1+a_2+\cdots a_n}\\&=\left(\sum_{a_1=0}^{n-1}q^{a_1}\right)\left(\sum_{a_2=0}^{n-2}q^{a_2}\right)\cdots\left(\sum_{a_n=0}^{0}q^{a_n}\right)\\&=[n]_q[n-1]_q\cdots[1]_q\\&=[n]_q!\end{aligned}$$ 有结论：将 $\operatorname{inv(\pi)}$ 换成 $\operatorname{maj(\pi)}=\sum_{i=1}^{n-1}i[\pi_i>\pi_{i+1}]$（降位和），结果是一致的。 突发奇想：设 $\operatorname{inc}(\pi)=\sum_{i=1}^{n}i[\pi_i>\max_{j=1}^{i-1}\pi_j]$，$\sum_{\pi\in S_n}q^{\operatorname{inc}(\pi)}$ 应如何计算？ 组合意义：以 $q$ 为底，$a_1$ 个 $1$，$a_2$ 个 $2$，一直到 $a_k$ 个 $k$ 的逆序对数量为指数的和为 $\left(\begin{matrix}n\\a_1,a_2,\dots a_k\end{matrix}\right)_q$。 令 $B(n,m,r)$ 是将 $r$ 个相同小球放入 $m$ 个相同试管中，每个试管最多可以容纳 $n$ 个小球的方案数。则 $B(n,m,r)=[q^r]\left(\begin{matrix}n+m\\m\end{matrix}\right)_q$。 $q-$binomial coefficient 有很多性质： $$\left(\begin{matrix}n\\m\end{matrix}\right)_q=\left(\begin{matrix}n\\n-m\end{matrix}\right)_q$$ 瞪眼可得。 $$\left(\begin{matrix}n\\m\end{matrix}\right)_q=\left(\begin{matrix}n-1\\m-1\end{matrix}\right)_q+q^m\left(\begin{matrix}n-1\\m\end{matrix}\right)_q$$ 这是帕斯卡性质，可以通过把两边拆开约分证明。 有一个很类似的东西： $$\left(\begin{matrix}n\\m\end{matrix}\right)_q=\left(\begin{matrix}n-1\\m\end{matrix}\right)_q+q^{n-m}\left(\begin{matrix}n-1\\m-1\end{matrix}\right)_q$$ 令 $m\gets n-m$ 可得。 由此可以推出它的组合意义：考虑网格上一条 $(0,0)$ 到 $(n,m)$ 的只能向右或向上的路径 $P\in\mathcal P$，令 $\operatorname{area}(P)$ 为它下方的格子数量，则有： $$\sum_{P\in\mathcal P}q^{\operatorname{area}(P)}=\left(\begin{matrix}n+m\\n\end{matrix}\right)_q$$ 还可以在 $\operatorname{area}(P)$ 和 Ferrers diagram 之间建立联系。 还有推论，可反复由帕斯卡性质拆解得到： $$\left(\begin{matrix}n+m+1\\n+1\end{matrix}\right)_q=\sum_{i=0}^{m}q^i\left(\begin{matrix}n+i\\n\end{matrix}\right)_q$$ $q-$Catalan 指的是 $\frac{\left(\begin{matrix}2n\\n\end{matrix}\right)_q}{[n+1]_q}$，它的组合意义是以 $q$ 为底，以长为 $2n$ 的括号序列的逆序对个数为指数的和。 $q-$binomial theorem： $$\prod_{i=0}^{n-1}(q^ix+1)=\sum_{i=0}^nq^{\binom{i}{2}}\left(\begin{matrix}n\\i\end{matrix}\right)_qx^i$$ 证明：把等式左侧记作 $f(x)$，观察到： $$f(qx)(x+1)=f(x)(q^nx+1)$$ 如果将展开 $f(x)$，记作 $f(x)=\sum_{i=0}^nQ_ix^i$，上式可写作： $$(x+1)\sum_{i=0}^nQ_iq^ix^i=(q^nx+1)\sum_{i=0}^nQ_ix^i$$ 对比其系数，可知当 $i\ge1$ 时，有： $$Q_i=Q_{i-1}\frac{q^{n-i+1}-1}{q^i-1}q^{i-1}$$ 由于 $Q_0=1$，可以递推出： $$Q_i=q^{\binom{i}{2}}\binom{n}{i}_q$$ 原命题得证。 由它就可以证明 $q-$binomial coefficient 是整系数多项式了。 $$\prod_{i=0}^{n}\frac{1}{1-q^ix}=\sum_{i=0}^\infin\binom{n+i}{i}_qx^i$$ 这是 $q-$binomial theorem 的负指数形式。 欧拉给出了另一个性质： $$\prod_{i=0}^\infin\frac{1}{q^ix+1}=\sum_{i=0}^\infin(-1)^i\frac{x^i}{(q)_i}$$ 接下来看 $q-$Lucas theorem。先回顾一下 Lucas theorem： $$\binom{n}{m}\equiv\left(\begin{matrix}\left\lfloor\frac{n}{p}\right\rfloor\\\left\lfloor\frac{m}{p}\right\rfloor\end{matrix}\right)\binom{n\bmod p}{m\bmod p}\pmod{p}$$ 有性质： $$\binom{p}{m}\equiv [m=0\lor m=p]\pmod p$$ 其中 $0\le m\le p$，$p$ 是质数。 接下来观察二项式： $$\begin{aligned}[x^m](1+x)^n&\equiv[x^m](1+x)^{p\times\left\lfloor\frac{n}{p}\right\rfloor}(1+x)^{n\bmod p}\pmod p\\&\equiv[x^m](1+x^p)^{\left\lfloor\frac{n}{p}\right\rfloor}(1+x)^{n\bmod p}\pmod p\\&\equiv\left[x^{\left\lfloor\frac{m}{p}\right\rfloor}\right](1+x)^{\left\lfloor\frac{n}{p}\right\rfloor}[x^{m\bmod p}](1+x)^{n\bmod p}\pmod p\end{aligned}$$ 其中第一步利用性质，第二步观察贡献。 接下来我们希望如法炮制，推出 $q-$Lucas theorem。可以确定的是要用到 $q-$binomial theorem。 可以找到 $d=\operatorname{ord}_p(q)$，使得相似的性质成立： $$\binom{d}{m}_q\equiv[m=0\lor m=d]$$ 其中 $0\le m\le d$。 接下来二项式中有贡献的就只有两项： $$\prod_{i=0}^{d-1}(q^ix+1)\equiv 1+q^{\binom{d}{2}}x^d\equiv1+(-1)^{[2\mid d]}x^d\pmod p$$ 接下来通过推导 $q-$binomial theorem，就可以得到 $q-$Lucas theorem： $$\binom{n}{m}_q\equiv \left(\begin{matrix}\left\lfloor\frac{n}{d}\right\rfloor\\\left\lfloor\frac{m}{d}\right\rfloor\end{matrix}\right)\left(\begin{matrix}n\bmod d\\m\bmod d\end{matrix}\right)_q\pmod p$$ $n$ 阶分圆多项式，记作 $\Phi_n(x)$，是 $x^n-1$ 的一个不可约因式，且不是 $x^k-1(k<n)$ 的因式。 如 $\Phi_6(x)=x^2-x+1$，$\Phi_{11}(x)=\sum_{i=0}^{10}x^i$，$\Phi_{16}(x)=x^8+1$。 它的名称的由来是这样的： $$\Phi_n(x)=\prod_{\begin{subarray}{c}1\le k\le n\\\gcd(k,n)=1\end{subarray}}\left(x-e^{2i\pi\frac{k}{n}}\right)$$ 这其实与 $x^n-1$ 本身也有关系。 有性质： $$x^n-1=\prod_{d|n}\Phi_d(x)$$ 由莫比乌斯反演可得 $$\Phi_n(x)=\prod_{d|n}\left(x^d-1\right)^{\mu\left(\frac{n}{d}\right)}$$ 例题：[因式分解](https://www.luogu.com.cn/problem/P1520) 其实对于 $q$-Lucas theorem，不仅是阶，单位根也可以，只要开始的那个性质就行了。 所以有： $$\binom{n}{m}_q\equiv \left(\begin{matrix}\left\lfloor\frac{n}{d}\right\rfloor\\\left\lfloor\frac{m}{d}\right\rfloor\end{matrix}\right)\left(\begin{matrix}n\bmod d\\m\bmod d\end{matrix}\right)_q\pmod {\Phi_d(q)}$$ 其中 $d$ 为任意正整数。这里模分圆多项式相当于引入了它的所有根。 最后有一个形式类似的式子： $$\sum_{w\in P_n}x^{\operatorname{cyc}(w)}=\sum_{i=0}^{n-1}(x+i)$$ 例题：[October 18, 2017](https://codeforces.com/contest/1603/problem/F)