模拟赛四道题三道是计数，不得不来看一看这个。
当一个表达式 \(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\)。
直接展开可得：
当 \(n\to\infty\) 时，上述值是确定的：
\[\left(\begin{matrix}\infty\\m\end{matrix}\right)_q=\lim_{n\to\infty}\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!} \]\(q-\)exponential 是指数函数的 \(q-\)analog，定义式为：
\[e_q(z)=\sum_{n=0}^{\infty}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\) 之间构成双射（从前往后确定）。
所以有：
有结论：将 \(\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 \]这是帕斯卡性质，可以通过把两边拆开约分证明。
有一个很类似的东西：
令 \(m\gets n-m\) 可得。
由此可以推出它的组合意义：考虑网格上一条 \((0,0)\) 到 \((n,m)\) 的只能向右或向上的路径 \(P\in\mathcal P\)，令 \(\operatorname{area}(P)\) 为它下方的格子数量，则有：
还可以在 \(\operatorname{area}(P)\) 和 Ferrers diagram 之间建立联系。
还有推论，可反复由帕斯卡性质拆解得到：
\(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}^\infty\binom{n+i}{i}_qx^i \]这是 \(q-\)binomial theorem 的负指数形式。
欧拉给出了另一个性质：
接下来看 \(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\) 是质数。
接下来观察二项式：
其中第一步利用性质，第二步观察贡献。
接下来我们希望如法炮制，推出 \(q-\)Lucas theorem。可以确定的是要用到 \(q-\)binomial theorem。
可以找到 \(d=\operatorname{ord}_p(q)\)，使得相似的性质成立：
其中 \(0\le m\le d\)。
接下来二项式中有贡献的就只有两项：
接下来通过推导 \(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\)。
它的名称的由来是这样的：
这其实与 \(x^n-1\) 本身也有关系。
有性质：
由莫比乌斯反演可得
\[\Phi_n(x)=\prod_{d|n}\left(x^d-1\right)^{\mu\left(\frac{n}{d}\right)} \]例题：因式分解
其实对于 \(q\)-Lucas theorem，不仅是阶，单位根也可以，只要开始的那个性质就行了。
所以有：
其中 \(d\) 为任意正整数。这里模分圆多项式相当于引入了它的所有根。
最后有一个形式类似的式子：
\[\sum_{w\in P_n}x^{\operatorname{cyc}(w)}=\sum_{i=0}^{n-1}(x+i) \] 标签：begin,right,end,matrix,sum,binomial,analog,left From： https://www.cnblogs.com/yzy4090/p/18281889