首页 > 其他分享 >q-binomial

q-binomial

时间:2024-01-17 17:33:20浏览次数:26  
标签:frac limits sum 恒等式 brack binomial prod

对着 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

相关文章

  • Binomial Sum 学习笔记
    这是EI写的一个神秘科技。我只能把它最简单的东西讲述出来。用于\(O(k+\logn)\)复杂度解决一类求和问题。使用条件:\(f(x)\)微分有限,话句话说,存在\(f\)的微分方程。如果我容易知道\(\displaystyle\sum_{i=0}^{n}a_i[x^i]G(x)^k,k\in[0,]\),那么我就可以\(O(n)\)求\(\displaystyl......
  • P6667 [清华集训2016] 如何优雅地求和 -Binomial Sum
    题面有一个多项式函数\(f(x)\),最高次幂为\(x^m\),定义变换\(Q\):\[Q(f,n,x)=\sum_{k=0}^{n}f(k)\binom{n}{k}x^k(1-x)^{n-k}\]现在给定函数\(f\)和\(n,x\),求\(Q(f,n,x)\bmod998244353\)。出于某种原因,函数\(f\)由点值形式给出,即给定\(a_0,a_1,⋯,a_m\)共\(m+1\)个......
  • 二项式系数 BINOMIAL COEFFICIENTS
    基本恒等式BASICIDENTITIES符号\({\dbinom{n}{k}}\)就是二次项系数,将此符号读作“\(n\)选取\(k\)”。这种常用说法来源于它的组合解释——从一个有\(n\)个元素的集合选取\(k\)个元素做成子集的方法数。嗯,显然有\({\dbinom{n}{k}}=\dfrac{n(n-1)...(n-k+1)}{k(k-1)......
  • Arrangement排列•Combination组合•Counting计数•Binomial Theorem二项式定理
    符号C-Combination组合数[1]A-Arrangement(旧教材为P-Permutation)N-Number元素的总个数(自然数集合).M-参与选择的元素个数(M不大于N,两者都是自然数集合).!-Factorial阶乘.Arrangement排列与Combination组合:注意:n,m都是自然数,且m<=n,下同.排列的定义:从n......
  • binomial sum
    前情提要:模拟赛就要出三个大模拟,字面意思上的模拟赛。所以发动了魔法卡献祭了模拟赛来写这个东西。我刚改邪归正准备好好敲暴力你就给我来这个?建议出题人自己写。感觉写博逐渐倾向于告诉自己“我学了这个东西但是以后可能会忘所以记下来”这种心态。算了反正模拟赛狗都不打。一......
  • 【XSY4186】Binomial(结论,数位DP)
    题面Binomial题解设\(\operatorname{ord}(n)\)表示\(n\)分解质因数后\(p\)的幂次,那么我们就是对于每一个\(k\)要求有多少\(0\leqm\leqn\)使得\(\operatorn......
  • Note / Solution Set -「Binomial Sum」两道例题
      删本地文件的时候瞟了一眼内容...这篇好像忘记发布了?  给定\(n,k\),求出\[\textit{ans}=\sum_{i=0}^n\binom{n}{i}i^k\bmod(10^9+7).\]  \(k\le5\times10......
  • q-binomial 学习笔记
    主要可以解决一些生成函数问题,网上资料不是很多,orzzaky的博客。part1q-Binomial考虑一个很经典的模型,就是从\((0,0)\)出发,每次向上或者向右走一格,走到\((n,m)\)的......