Gauss's blog

Gauss's blog

I’d go back to December turn around and make it alright.

「学习笔记」q-二项式系数

posted on 2022-02-11 21:29:14 | under 学习笔记 |

Background

这一切都要从一场模拟赛说起...... 怨念

q-analog

定义 q-模拟 $[n]_q$ 为

$$[n]_q=1+q+q^2+\cdots+q^{n-1}=\frac{1-q^n}{1-q}$$

我们可以看到当 $q\rightarrow 1$ 时,$[n]_q=n$。

q-factorial

定义 q-阶乘 $n!_q$ 为

$$n!_q=[1]_q[2]_q\cdots[n]_q$$

我们可以看到 $q\rightarrow 1$ 时,$n!_q=n!$。

q-binomial coefficient

定义 q-二项式系数 $\displaystyle{n\choose m}_q$ 为

$${n\choose m}_q=\frac{n!_q}{m!_q(n-m)!_q}$$

实际上,我们可以将其看成关于 $q$ 的生成函数,相应的组合对象是所有整数拆分,满足不超过 $n-m$ 部分,每部分不超过 $m$,$q^i$ 刻画的是满足条件的正整数 $i$ 的拆分数。

不仅 q-二项式系数的定义与通常的二项式系数形式相近,它们也有相似的性质。

我们考虑用于研究整数拆分的 Ferrers 图,满足条件的拆分即对应的 Ferrers 图不超过 $n-m$ 行 $m$ 列的拆分,我们对这样的的 Ferrers 图进行转置,得到一个不超过 $m$ 行 $n-m$ 列的图,反过来,我们也可以将不超过 $m$ 行 $n-m$ 列的 Ferrers 图转置得到不超过 $n$ 行 $n-m$ 列的图,这告诉我们

$${n\choose m}_q={n\choose n-m}_q$$

q-二项式系数满足 q-Pascal 递推关系

$${n\choose m}_q={n-1\choose m}_q+q^{n-m}{n-1\choose m-1}_q$$

证明:分两种情况:

  1. 满足条件的 Ferrers 图小于 $n-m$ 行,这种情况的贡献为 $\displaystyle{n-1\choose m}_q$。

  2. 满足条件的 Ferrers 图恰好 $n-m$ 行,所以我们可以移除第一列,得到一个不超过 $n-m$ 行 $m-1$ 列的 Ferrers 图,故这部分贡献为 $\displaystyle q^{n-m}{n-1\choose m-1}_q$。

有了这条递推关系,我们便可通过数学归纳法证明由生成函数定义的 q-二项式系数与本节开头给出的定义是等价的了。

q-binominal theorem

q-二项式定理说的是

$$\prod_{i=1}^n(1+q^ix)=\sum_{m=1}^n q^{{m+1\choose 2}}{n\choose m}_qx^m$$

当 $q\rightarrow 1$ 时,我们得到通常的二项式定理。

证明:

左边的式子可以看成不超过 $n$ 部分,且每部分不超过 $n$ 的拆分的二元 GF,其中 $q^i$ 刻画的是满足条件的正整数 $i$ 的拆分数,而 $x$ 刻画的则是拆分的部分数。

令 $a_m(q)$ 表示恰好有 $m$ 部分的合法拆分的 GF,于是我们仅需证

$$a_m(q)=q^{{m+1\choose 2}}{n\choose m}_q$$

证明也很容易,我们考虑将恰好有 $m$ 部分的合法拆分的第一行移除前 $m$ 列,第二行移除前 $m-1$ 列,......,第 $m$ 行移除第一列,这样我们就得到了一个不超过 $m$ 部分且每部分不超过 $n-m$ 的拆分,反过来做也是一样的,所以我们可以在这两类拆分之间建立双射,而后者的 GF 恰好为 $\displaystyle{n\choose m}_q$,乘上删去的列的贡献的贡献即知证毕。

那么,如何快速处理一行的 q-二项式系数呢?(取模意义下)

我们发现 q-模拟和 q-阶乘的线性处理都是 trivial 的,而瓶颈在于在于 q-二项式系数的处理时可能会出现分母为 0(在取模意义下)的情况。

设 $\alpha$ 为最小的 $i$ 使得 $q^i\equiv 1$,那么对于任意的 $i$,都有 $q^{i}\equiv q^{i\bmod \alpha}$。

我们将 q-二项式系数写成

$${n\choose m}_q=\prod_{i=1}^m\frac{1-q^{n-m+1}}{1-q^i}$$

不难发现分子分母均出现了长度为 $\alpha$ 的循环节,将每个循环节中不为 0(取模意义下)的部分提出来单独算。

那么分子分母中剩下的部分无非是形如 $(1-q^{i\alpha})$ 的连乘积,我们将 $(1-q^{i\alpha})$ 写成

$$1-q^{i\alpha}=(1-q^{\alpha})(1+q^{\alpha}+\cdots+q^{(i-1)\alpha})$$

而注意到剩下的部分分母有 $\displaystyle\left\lfloor\frac{m}{\alpha}\right\rfloor$ 项,分子有 $\displaystyle\left\lfloor\frac{n}{\alpha}\right\rfloor-\left\lfloor\frac{n-m}{\alpha}\right\rfloor$ 项,所以要么分子比分母多一项,要么分子分母项数相同

当分子比分母多一项的时候,有 $\displaystyle(1-q^\alpha)|{n\choose m}_q$,故 $\displaystyle {n\choose m}_q\equiv 0$;

当分子分母项数相等时 $(1-q^{i\alpha })$ 这些项相互抵消,记 $\displaystyle x=\left\lfloor\frac{n}{\alpha}\right\rfloor,y=\left\lfloor\frac{m}{\alpha}\right\rfloor$,剩下部分对 $\displaystyle {n\choose m}_q$ 的贡献即为 $\displaystyle {x\choose y}$。