HYPQ 是一个用 Mathematica 编写的软件包，用于操作和识别 q-二项式和基本超几何级数和恒等式。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
\] 证明：分两种情况：
-
满足条件的 Ferrers 图小于 \(n-m\) 行，这种情况的贡献为 \(\displaystyle{n-1\choose m}_q\)。
-
满足条件的 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}\)。
| 
