对着 zaky 抄写一下...这里用极限定义大概只是为了 \(q=1\) 时的特殊情况,就是二项式系数。后面都用 \(q\) 表示无限趋近于 \(q\) 了。
定义:
\[[n]_q = \sum\limits_{i=0}^{n-1} q^i = \lim_{x \rightarrow q} \frac{1-x^n}{1-x}, [ n ] !_q = \prod_{i=1}^n [i]_q, {n \brack m}_q = \frac {[n]!_q} {[m]!_q [n - m]!_q} \]对称,展开,吸收,帕斯卡恒等式。
\[{n\brack m}_q={n\brack n-m}_q \]\[{n\brack m}_q=\frac{\prod_{n-m+1}^n(1-x^i)}{\prod_1^m (1-x^i)} \]\[[m]_q{n\brack m}_q=[n]_q{n-1\brack m-1}_q \]\[{n\brack m}_q={n-1\brack m-1}_q+q^m{n-1\brack m}_q \](下面是需要额外记忆的)代入 \(m\gets n-m\) 有帕斯卡恒等式第二个形式(自己编的名字):
\[{n \brack m}_q = q^{n-m} {n-1 \brack m-1}_q + {n-1 \brack m}_q \]考虑 \(m\times (n-m)\) 这个平面,相当于每次可以往右走或者往上走,每次往右走还要乘上 \(q\) 的《当且列下方格子》次方。所以得到 \({n\brack m}_q\) 的一个组合意义就是 \((0,0)\) 走到 \((n-m,m)\) 每步只能向右向上,所有路径中,\(q^{\text{折线右下方格子数}}\) 之和。
二项式定理:
\[\prod_{i=0}^{n-1} (1+q^iz) = \sum\limits_{i=0}^n q^{\binom{i}{2}} {n \brack i}_q z^i \]证明直接对 \(n\) 归纳即可。这给出了生成函数的形式 \(q^{\binom{m}{2}}{n\brack m}_q=[x^m]\prod_{i=0}^{n-1}(1+q^iz)\),这给出了 \({n\brack m}_q\) 的另一个组合意义是,对于 \(1\sim n\) 的选出大小为 \(m\) 的集合 \(S\),\({n\brack m}_q=\sum\limits_{|S|=m}\prod\limits_{i\in S}q^{i\text{ 前面有多少个没被选}}\)。
上指标求和:\({n + m + 1 \brack n + 1}_q = \sum\limits_{i=0}^m q^i {n + i \brack n}_q\),不断运用帕斯卡恒等式第二个形式。
范德蒙德卷积:\({n + m \brack k}_q = \sum\limits_{i=0}^k q^{(n-i)(k-i)} {n \brack i}_q {m \brack k-i}_q\),考虑运用第二个组合意义,后半部分选出的 \((k-i)\) 每个都要补充乘上 \(q^{n-i}\)。
标签:frac,limits,sum,恒等式,brack,binomial,prod From: https://www.cnblogs.com/do-while-true/p/17970572