q-analog
qwaszx
·
·
个人记录
本篇文章中有标号的公式的标号对应于具体数学中原公式的标号
今天看见这样一个题:
定义 f(v) 为 \{1,2,\cdots,n\} 的大小为 m 的子集中和为 v 的子集个数，令 p=\max(v\mid f(v)\neq 0) ，求出
\sum_{i=0}^p19190506^{p-i}f(i)
对 p=998244353 取模的结果. n,m\leq 10^{12}，多组询问，T\leq 5\times 10^5.
首先显然有
f(v)=[x^vy^m]\prod_{i=1}^n(1+x^iy)
设 B=19190506，那么我们要求的就是
B^p\sum_v[x^vy^m]B^{-v}\prod_{i=1}^n(1+x^iy)=B^p[y^m]\prod_{i=1}^n(1+B^{-i}y)=B^{p-m}[y^m]\prod_{i=0}^{n-1}(1+B^{-i}y)
现在让我们来关注一下后面一部分的系数:
F_q(z)=\prod_{i=0}^{n-1}(1+q^iz)
做扰动，有
F_q(z)=\prod_{i=0}^{n-1}(1+q^iz)=\frac{1+z}{1+q^nz}\prod_{i=0}^{n-1}(1+q^i\cdot qz)=\frac{1+z}{1+q^nz}F_q(qz)
用 (1+q^nz) 乘两边并展开就得到
\sum_{i=0}^nf_iz^i+f_iq^nz^{i+1}=\sum_{i=0}^nf_iq^iz^i+f_iq^iz^{i+1}
比较系数得到
f_i+q^nf_{i-1}=f_iq^i+f_{i-1}q^{i-1}
也就是
f_i=\frac{q^{i-1}-q^n}{1-q^i}f_{i-1}
显然有 f_0=1，于是我们得到
f_i=\frac{(q^{i-1}-q^n)(q^{i-2}-q^n)\cdots(1-q^n)}{(1-q^i)(1-q^{i-1})\cdots(1-q)}=q^{i(i-1)/2}\frac{(1-q^n)(1-q^{n-1})\cdots(1-q^{n-i+1})}{(1-q^i)(1-q^{i-1})\cdots(1-q)}
我们把后面这个分式记作 \dbinom{n}{i}_q，其中 q 是任何非 1 复数，它被称为高斯二项式系数或 q-二项式系数. 那么我们现在可以得到
\prod_{i=0}^{n-1}(1+q^iz)=\sum_{i=0}^nq^{i(i-1)/2}\binom{n}{i}_qz^i\tag{5.13}
这被称为高斯二项式定理或 q-二项式定理. 这是极为重要的一个恒等式. 按照 EI 的说法，这被用于定义高斯二项式系数（因为前面那个分式定义在 q 为单位根时会出现分母为 0），不过我们还是使用分式定义，它和原形式比较接近.
那么现在清楚了，我们的问题就是如何计算
B^{p-m(m+1)/2}\binom{n}{m}_{B^{-1}}
由于 n,m 很大，我们试图给 q-二项式系数找一个类似 Lucas 定理的关系. 令 a=\mathrm{ord}(q) 为满足 q^{a}\equiv 1\pmod p 的最小整数，即 q 在模 p 下的阶，那么我们可以得到一些结论:
引理 1：当 0<m<a 时，\dbinom{a}{m}_q\equiv 0\pmod p
证明：直接按照分式展开二项式系数，显然分子为 0 而分母不为 0，于是得证.
推论 1：
\prod_{i=0}^{a-1}(1+q^iz)\equiv 1+q^{a(a-1)/2}z^a\pmod p
证明：按照 q-二项式定理展开后应用引理 1 即可
定理 1:
\binom{n}{m}_q\equiv \binom{\lfloor n/a\rfloor}{\lfloor m/a\rfloor}\binom{n\bmod a}{m\bmod a}_q
（请注意前面那个二项式系数不带有下标 q）
证明：仿照 Lucas 定理的证明，我们有
\begin{aligned}
q^{m(m-1)/2}\binom{n}{m}_q&=[z^m]\prod_{i=0}^{n-1}(1+q^iz)\\
&\equiv [z^m]\left(\prod_{i=0}^{a-1}(1+q^iz)\right)^{\lfloor n/a\rfloor}\left(\prod_{i=0}^{n\bmod a-1}(1+q^iz)\right)\\
&\equiv \left([z^{\lfloor m/a\rfloor}](1+q^{a(a-1)/2}z)^{\lfloor n/a\rfloor}\right)\left([z^{m\bmod a}]\prod_{i=0}^{n\bmod a-1}(1+q^iz)\right)\\
&=q^{\lfloor m/a\rfloor a(a-1)/2}\binom{\lfloor n/a\rfloor}{\lfloor m/a\rfloor}q^{C(m\bmod a,2)}\binom{n\bmod a}{m\bmod a}_q
\end{aligned}
该推导首先使用了 q^a\equiv 1\pmod p 来把乘积分成 \lfloor n/a\rfloor 个完整段和剩余 n\bmod a 项，然后使用推论 1 和 q-二项式定理来完成化简. 指数上不写二项式系数而是写组合数是因为写不开了.
接下来注意
\begin{aligned}
q^{\lfloor m/a\rfloor a(a-1)/2}= q^{C(\lfloor m/a\rfloor a,2)}q^{-a^2C(\lfloor m/a\rfloor,2)}\equiv q^{C(\lfloor m/a\rfloor a,2)}\pmod{p}
\end{aligned}
然后利用 \binom{a+b}{2}-\binom{a}{2}-\binom{b}{2}=ab, 我们就得到了想要的结果.
然后算一下发现 19190506 的阶为 10^6 级别，因此 \lfloor n/a\rfloor 和 n\bmod a 都不大，于是这道题就在 O(\mathrm{ord}(19190506)+T) 时间内完成了.
不过我们的探索还没有结束，我们需要考察 q-二项式系数的更多性质.
我们首先介绍 q-模拟(q-analog)，它引入一个参数 q，使得当取极限 q\to 1 时得到原定理、等式或表达式. 这个模拟通常表达为 q 的一个级数，它与原对象有许多相似的性质. 在这里我们只探讨最经典的部分，定义实数 r 的 q-模拟为
[r]_q=\frac{1-q^r}{1-q}
显然当 q\to 1 时 [r]_q\to r，根据洛必达法则.
当 n 为非负整数时，还可以得到
[n]_q=1+q+q^2\cdots q^{n-1},n\text{是非负整数}
接下来定义整数阶乘的 q-模拟为
[n]!_q=\prod_{i=1}^n[i]_q=\frac{(1-q^n)(1-q^{n-1})\cdots (1-q)}{(1-q)^n},n\text{是非负整数}
那么不难验证 q-二项式系数可以写为
\binom{n}{m}_q=\frac{[n]!_q}{[m]!_q[n-m]!_q},n,m\text{是整数},0\leq m\leq n\tag{5.3}
有一个问题是，\dbinom{n}{m}_q 一定是 q 的整系数多项式吗？我们知道当 q\to 1 时 \dbinom{n}{m} 是整数，这就是对这个命题的 q-模拟.
根据 q-二项式定理，答案是显然的，不过我们试图从一个数论的角度来说明. 当 q\to 1 时一个证明是这样的:
设 v_p(n) 为 n 的质因子分解中素数 p 的指数，那么我们有
v_p(n!)=\sum_{i=1}^n\sum_{k\geq 1}[p^k\mid n]=\sum_{k\geq 1}\left\lfloor\frac{n}{p^k}\right\rfloor
而 v_p\dbinom{n+m}{n}=v_p((n+m)!)-v_p(n!)-v_p(m!). 由于 \left\lfloor\dfrac{n+m}{d}\right\rfloor=\left\lfloor\dfrac{n}{d}\right\rfloor+\left\lfloor\dfrac{m}{d}\right\rfloor+[n\bmod d+m\bmod d\geq d]\geq \left\lfloor\dfrac{n}{d}\right\rfloor+\left\lfloor\dfrac{m}{d}\right\rfloor，这就给出 v_p((n+m)!)-v_p(n!)-v_p(m!)\geq 0，从而这个二项式系数一定是整数
现在我们要做的事情就是试图找出这个证明的一个 q-模拟，自然考虑分圆多项式:
q^n-1=\prod_{d\mid n}\Phi_d(q)
那么就有
[n]_q=\prod_{d\neq 1,d|n}\Phi_d(q)
于是
[n]!_q=\prod_{i=1}^n\prod_{d\neq 1,d|i}\Phi_d(q)=\prod_{d\geq 2}\Phi_d(q)^{\lfloor n/d\rfloor}
于是类似的分析对于 q-二项式系数依然成立，而我们知道分圆多项式是整系数多项式，这就完成了证明.
事实上与 q\to 1 时相同，q-二项式系数可以对任意的上下指标定义. 不过为了简便起见，我们先只允许上指标为复数. 我们来重新定义一下 q-二项式系数，首先定义 q-下降幂:
[r]_q^{\underline{n}}=\frac{(1-q^r)(1-q^{r-1})\cdots (1-q^{r-n+1})}{(1-q)^n},n\ \text{是非负整数}
对 n 为负整数的情况也是可以自然定义的，不过不是重点. 现在使用下降幂来定义 q-二项式系数
\binom{r}{n}_q=\begin{cases}\dfrac{(1-q^r)(1-q^{r-1})\cdots(1-q^{r-n+1})}{(1-q^n)(1-q^{n-1})\cdots(1-q)}=\dfrac{[r]_q^{\underline{n}}}{[n]!_q},&\text{整数}\ k\geq 0\\\\0,&\text{整数}\ k<0\end{cases}\tag{5.1}
接下来我们来列举一下常规的二项式系数恒等式扩展到 q-二项式系数时的结果，这些结果不难证明（不过需要多项式推理法证明的那些还比较阴间...q-模拟之后失去了多项式的性质）:
\binom{n}{k}_q=\binom{n}{n-k}_q,\quad \text{整数}n\geq 0,k\ \text{是整数}\tag{5.4}
\binom{r}{k}_q=\frac{[r]_q}{[k]_q}\binom{r-1}{k-1}_q,\quad \text{整数}\ k\neq 0\tag{5.5}
（由 (5.5) 可以变形出 (5.6) 和 (5.7)，这是吸收恒等式的 q-模拟）
\binom{r}{k}_q=q^k\binom{r-1}{k}_q+\binom{r-1}{k-1}_q,\quad k\ \text{是整数}\tag{5.8.1}
\binom{r}{k}_q=\binom{r-1}{k}_q+q^{r-k}\binom{r-1}{k-1}_q,\quad k\ \text{是整数}\tag{5.8.2}
（有两种加法公式，这和 q\to 1 时不同，不过由 (5.14) 的 q-模拟可知它们是等价的）
\sum_{k\leq n}q^k\binom{r+k}{k}_q=\binom{r+n+1}{n}_q,\quad n\ \text{是整数}\tag{5.9.1}
\sum_{k\leq n}q^{(r+1)(n-k)}\binom{r+k}{k}_q=\binom{r+n+1}{n}_q,\quad n\text{是整数}\tag{5.9.2}
\sum_{0\leq k\leq n}q^{(m+1)(n-k)}\binom{k}{m}_q=\binom{n+1}{m+1}_q,\quad \text{整数}\ m,n\geq 0\tag{5.10.1}
\sum_{0\leq k\leq n}q^{k-m}\binom{k}{m}_q=\binom{n+1}{m+1}_q,\quad \text{整数}m,n\geq 0\tag{5.10.2}
这四个式子都是对 (5.8.1) 或 (5.8.2) 展开得到的.
由 (5.9.1) 和 (5.10.1) 我们可以得到两个不平凡的生成函数恒等式:
\begin{aligned}
F_{m+1}(z)=&\sum_{n\geq 0}\binom{m+1+n}{n}_qz^n\\
=&\sum_{n\geq 0}z^n\sum_{k\leq n}q^k\binom{m+k}{k}_q\\
=&\sum_{k\geq 0}q^kz^k\binom{m+k}{k}_q\frac{1}{1-z}\\
=&\frac{1}{1-z}F_{m}(qz)
\end{aligned}
当 m 是非负整数时，一定会递归到 F_0(q^mz)=\dfrac{1}{1-q^mz}，于是我们就得到
\prod_{i=0}^{m-1}\frac{1}{1-q^iz}=\sum_{k\geq 0}\binom{m+k-1}{k}_qz^k
而对于 (5.10)，我们可以得到
\begin{aligned}
F_{m+1}(z)=&\sum_{n\geq 0}\binom{n}{m+1}_qz^{n}\\
=&\sum_{n\geq 0}z^n\sum_{0\leq k<n}\binom{k}{m}_qq^{(m+1)(n-1-k)}\\
=&\sum_{k\geq 0}\binom{k}{m}_qz^k\frac{z}{1-q^{m+1}z}\\
=&\frac{z}{1-q^{m+1}z}F_m(z)
\end{aligned}
我们忽略了 n=0 时的边界情况，不过没关系，因为当 m>0 时有 \dbinom{0}{m}_q=0. 那么我们可以和上面一样展开得到
z^{m}\prod_{i=0}^{m}\frac{1}{1-q^iz}=\sum_{k\geq 0}\binom{k}{m}_qz^k
我们将看到它们都可以认为是 q-二项式定理的负指数情况. 用 (5.9.2) 和 (5.10.2) 来推导会得到相同的结果，只不过是乘法的顺序颠倒一下.
\binom{r}{k}_q=(-1)^kq^{kr-\binom{k}{2}}\binom{k-r-1}{k}_q,\quad k\ \text{是整数}\tag{5.14}
这就是反转公式的 q-模拟.
我们来试图通过这个东西得到 q-二项式定理的负指数情况. 首先我们应该对于负指数来定义幂的 q-模拟. 把 (1+z)^m 的 q-模拟记为 (-z;q)_m wdnmd这玩意好丑啊，称为 q-Pochhammer：
(z;q)_m=\prod_{i=0}^{m-1}(1-q^iz),\quad \text{整数}\ m\geq 0
我们可以看到 (-z;q)_m=(1+q^{m-1}z)(-z;q)_{m-1}，我们可以以此来定义负指数的幂的 q-模拟:
(-z;q)_{-m}=\frac{1}{1+q^{-m}z}(-z;q)_{-(m-1)},\quad \text{整数}\ m\geq 0
也就是
(-z;q)_{-m}=\prod_{i=-m}^{-1}\frac{1}{1+q^iz},\quad \text{整数}\ m\geq 0
我猜对于任意实数甚至复数 r 都可以定义 (z,q)_r，但是我不会(
我们现在重写 q-二项式定理:
(-z;q)_n=\sum_{i\geq 0}q^{i(i-1)/2}\binom{n}{i}_qz^i,\quad n\text{是整数}
在 n<0 时使用 (5.14) 就得到
\begin{aligned}
(-z;q)_{-n}=&\sum_{i\geq 0}q^{i(i-1)/2}\binom{-n}{i}_qz^i\\
=&\sum_{i\geq 0}(-1)^iq^{-in}\binom{i+n-1}{i}_qz^i\\
=&\prod_{i=0}^{n-1}\frac{1}{1+q^{i-n}z}\\
=&\prod_{i=-n}^{-1}\frac{1}{1+q^iz}
\end{aligned}
接下来是 (5.21)，中间我们跳过了一些不太重要的恒等式.
\binom{r}{m}_q\binom{m}{k}_q=\binom{r}{k}_q\binom{r-k}{m-k}_q,\quad m,k\ \text{是整数}
最后一个写在这里的 q-模拟恒等式是 q-范德蒙德卷积:
\binom{r+s}{n}_q=\sum_k q^{(r-k)(n-k)}\binom{r}{k}_q\binom{s}{n-k}_q
还有一个与 q\to 1 不同的恒等式，我们来考虑把 q 换成 q^{-1} 会发生什么，不难发现有
\binom{n}{m}_{q^{-1}}=q^{-m(n-m)}\binom{n}{m}_q
由于本文已经太长，继续罗列恒等式已经没有意义，我们来考虑一些实际的问题.
记一个排列 \pi 的逆序对数为 \mathrm{inv}(\pi)，S(n) 为所有长度为 n 的排列组成的集合，那么有
\sum_{\pi\in S(n)}q^{\mathrm{inv}(\pi)}=[n]!_q
考虑每个位置 i，设 f_i 为 i 前面小于 \pi_i 的元素的数量，那么显然 0\leq f_i<i，并且每个不同的 f 序列和全排列一一对应，于是上式是显然的.
假设给定了 n,k（同数量级），我们需要快速计算出 [q^k][n]!_q，那么有若干不同做法. 首先第一步都是分开计算分子分母:
[n]!_z=\prod_{i=1}^{n}\frac{1-z^i}{1-z}
分母就是 (1-z)^{n}，使用组合数计算，主要考虑分子.
- Ln+Exp，这是因为 \ln(1-z^i) 具有简单的形式. O(k\log k)，需要多项式操作.
- 当 k\leq n 时，可以去掉 n 的上界，那么就是五边形数.
- 否则比较麻烦，考虑一个组合意义，相当于是在 1\cdots n 中选出若干个不同数字的带容斥系数的方案数的生成函数，显然只能选择 \Theta(\sqrt{k}) 个不同数字，所以设计 dp 为 f_{i,j} 表示选了 i 个不同数字和为 j 的答案，那么转移的时候可以给所有选择的数字加一，或者给所有选择的数字加一之后再放进来一个 1，即
f_{i,j}=f_{i,j-i}+f_{i-1,j-i}
不过这样可能会选择大小超过 n 的数字，由于这个数字只可能是 n+1，所以还要减去 f_{i-1,j-n-1}. 复杂度 \Theta(k\sqrt{k})
- （EItxdy）按照 q-二项式定理进行展开，有
\prod_{i=0}^{n-1}(1-z^i\cdot z)=\sum_{i=0}^n(-1)^iz^{i(i+1)/2}\binom{n}{i}_z
显然只有前 \Theta(\sqrt{k}) 项有贡献，并且我们很容易 O(K) 从 \dbinom{n}{i-1}_z 递推到 \dbinom{n}{i}_z，所以这样做的复杂度也是 O(k\sqrt{k})，并且常数显著优于上一个做法. code
然后有一个非常震撼的结论，定义一个降位为满足 \pi_i>\pi_{i+1} 的 i，定义一个排列的 major index 为 \mathrm{maj}(\pi)=\sum [\pi_i>\pi_{i+1}]i，即所有降位的下标和，那么我们有
\sum_{\pi\in S(n)}q^{\mathrm{maj}(\pi)}=\sum_{\pi \in S(n)}q^{\mathrm{inv}(\pi)}
证明完全不会，听说从提出到构造出双射用了几十年(
上面这个东西对多重排列也适用，对于有 a_1 个 1，a_2 个 2，\cdots，a_m 个 m 的排列组成的集合 S，我们有
\sum_{\pi\in S}q^{\mathrm{maj}(\pi)}=\sum_{\pi\in S}q^{\mathrm{inv}(\pi)}=\binom{a_1+\cdots+a_m}{a_1,\cdots,a_m}
我会证后面那个等号 前面那个就完全没想法(
可以用 major index 定义 q-Catalan 数 [C_n]_q 和 q-Fuss-Catalan 数 [C^{(m)}_n]_q，这需要我们回忆一下在研究 广义二项级数 时提到的 m-Raney 数列. 令 S^{(m)}_n 为所有长度为 mn+1 的 m-Raney 数列 \left<a_0,\cdots,a_{mn}\right> 组成的集合，那么有：
\sum_{\pi\in S_n^{(m)}}q^{\mathrm{maj}(\pi)}=\frac{1}{[mn+1]_q}\binom{mn+1}{n}_q
这个东西我就完全不懂了 所以只能列出来了(
猜测应该同样有广义二项级数和广义指数级数的 q-analog，但我的解析水平完全达不到，大概要先教教我 q-拉格朗日反演怎么做(
我们知道划分数的生成函数为
F(z)=\prod_{i\geq 1}\frac{1}{1-z^i}
这就注定了它会和我们这部分内容有关系. 按照刚才的记号，可以写成 (z;z)_\infty^{-1}. 直接展开就得到
F(z)=\sum_{i\geq 0}z^i\binom{\infty}{i}_z
后面这个上标为 \infty 的 q-二项式系数有些令人迷惑，不过我们也可以写得正常一点. 当 |z|<1 时，有
\lim_{n\to \infty}\binom{n}{i}_z=\lim_{n\to \infty}\frac{(1-z^n)(1-z^{n-1})\cdots (1-z^{n-i+1})}{(1-z^i)(1-z^{i-1})\cdots(1-z)}=(z;z)_i^{-1}=\frac{1}{[i]!_z(1-z)^i}
于是
F(z)=\sum_{i\geq 0}\frac{z^i}{(z;z)_i}
它的一个组合意义是枚举最大的元素.
还有一个结论是
F(z)=\sum_{i\geq 0}z^{i^2}(z;z)^{-2}_i
我现在大概只会个组合证明，即考虑 Ferrers diagram，从原点引一条直线 y=x，那么它离开这个图时会产生一个正方形，这被称为 Durfee square. 枚举这个正方形的大小，剩余的部分就是 (z;z)^{-2}_i，于是就得到了上面那个结论. 这个结论也可以用于 O(n\sqrt{n}) 计算划分数，代码可以看 EI's blog.
然后的一个结论是 [q^r]\dbinom{n+m}{n}_q 是把 r 划分成不超过 n 个部分，每部分不超过 m 的方案数. 这个的证明比较简单，我们只要考虑一个 BGF
[t^n]\frac{1}{1-t}\prod_{i=1}^m\frac{1}{1-z^it}=[t^n]\sum_{i\geq 0}t^i\binom{n+m}{n}_q
还有一个结论是相异无序拆分等于奇无序拆分，也就是说
\prod_{i\geq 1}(1+z^i)=\prod_{i\geq 1}\frac{1}{1-z^{2i-1}}
只需要注意到
\prod_{i\geq 1}(1+z^i)=\frac{(1-z^{2})(1-z^4)\cdots}{(1-z)(1-z^2)\cdots}=\prod_{i\geq 1}\frac{1}{1-z^{2i-1}}
即可证明
还有一些有限制的划分数的计算，也一并说了
从 (0,0) 走到 (n,m)，只允许向上向右走. 设一条路径 p 与直线 y=0 和直线 x=n 围成的面积为 \mathrm{area}(p)，所有路径的集合为 S，那么有
\sum_{p\in S}q^{\mathrm{area}(p)}=\binom{n+m}{n}_q
这个还比较简单，我们按列分割坐标系，考虑所有向右走的步，那么面积就是所有向右走的步的高度之和. 显然这个高度序列与长度不超过 n，值域为 [0,m] 的不降序列一一对应，所以答案就是
[t^n]\frac{1}{1-t}\prod_{i=1}^m\frac{1}{1-q^it}=\binom{n+m}{n}_q
还有更多的结果成立，但我的数理基础限制了我的想象力/kk 所以就只能到这里了.