免费行情软件网站下载大全爱,学校vi设计案例,微信开发什么时候好,西安网站建设风尚组合数 (nm)\dbinom{n}{m}(mn)#xff1a;从 nnn 个物品中选出 mmm 个的方案数。 (nm)n!m!(n−m)!nm‾m!\dbinom{n}{m}\dfrac{n!}{m!(n-m)!}\dfrac{n^{\underline{m}}}{m!}(mn)m!(n−m)!n!m!nm #xff08;这个式子只依靠经典的组合意义#xff0c;所以只在 0≤m≤…组合数
(nm)\dbinom{n}{m}(mn)从 nnn 个物品中选出 mmm 个的方案数。 (nm)n!m!(n−m)!nm‾m!\dbinom{n}{m}\dfrac{n!}{m!(n-m)!}\dfrac{n^{\underline{m}}}{m!}(mn)m!(n−m)!n!m!nm 这个式子只依靠经典的组合意义所以只在 0≤m≤n0\leq m\leq n0≤m≤n 时确保成立。 推论 对称性(nm)(nn−m)\dbinom{n}{m}\dbinom{n}{n-m}(mn)(n−mn) 吸收/释放(nm)nm(n−1m−1)\dbinom{n}{m}\dfrac{n}{m}\dbinom{n-1}{m-1}(mn)mn(m−1n−1) 递推公式(nm)(n−1m)(n−1m−1)\dbinom{n}{m}\dbinom{n-1}{m}\dbinom{n-1}{m-1}(mn)(mn−1)(m−1n−1) 推论 平行求和∑i0n(rii)(rn1n)\sum\limits_{i0}^{n}\dbinom{ri}{i}\dbinom{rn1}{n}i0∑n(iri)(nrn1) 证明∑i0n(rii)(r0)(r11)(r22)...(rnn)(r10)(r11)(r22)...(rnn)(r21)(r22)...(rnn)(r32)...(rnn)(rn1n)\sum\limits_{i0}^{n}\binom{ri}{i}\\\binom{r}{0}\binom{r1}{1}\binom{r2}{2}...\binom{rn}{n}\\\binom{r1}{0}\binom{r1}{1}\binom{r2}{2}...\binom{rn}{n}\\\binom{r2}{1}\binom{r2}{2}...\binom{rn}{n}\\\binom{r3}{2}...\binom{rn}{n}\\\binom{rn1}{n}i0∑n(iri)(0r)(1r1)(2r2)...(nrn)(0r1)(1r1)(2r2)...(nrn)(1r2)(2r2)...(nrn)(2r3)...(nrn)(nrn1) 上指标求和∑i0n(im)(n1m1)\sum\limits_{i0}^{n}\dbinom{i}{m}\dbinom{n1}{m1}i0∑n(mi)(m1n1) 证明∑i0n(im)(mm)(m1m)(m2m)...(nm)(m1m1)(m1m)(m2m)...(nm)(m2m1)(m2m)...(nm)(m3m1)...(nm)(n1m1)\sum\limits_{i0}^{n}\binom{i}{m}\\\binom{m}{m}\binom{m1}{m}\binom{m2}{m}...\binom{n}{m}\\\binom{m1}{m1}\binom{m1}{m}\binom{m2}{m}...\binom{n}{m}\\\binom{m2}{m1}\binom{m2}{m}...\binom{n}{m}\\\binom{m3}{m1}...\binom{n}{m}\\\binom{n1}{m1}i0∑n(mi)(mm)(mm1)(mm2)...(mn)(m1m1)(mm1)(mm2)...(mn)(m1m2)(mm2)...(mn)(m1m3)...(mn)(m1n1) 经典二项式定理(xy)k∑i0k(ki)xiyk−i(xy)^k\sum\limits_{i0}^{k}\dbinom{k}{i}x^iy^{k-i}(xy)ki0∑k(ik)xiyk−i 范德蒙德卷积 结论(nmk)∑i0k(ni)(mk−i)\dbinom{nm}{k}\sum\limits_{i0}^{k}\dbinom{n}{i}\dbinom{m}{k-i}(knm)i0∑k(in)(k−im) 证明首先显然有 (1x)nm(1x)n(1x)m(1x)^{nm}(1x)^n(1x)^m(1x)nm(1x)n(1x)m 那么∑k0nm(nmk)xk∑i0n(ni)xi∑j0m(mj)xj\sum\limits_{k0}^{nm}\binom{nm}{k}x^k\sum\limits_{i0}^{n}\binom{n}{i}x^i\sum\limits_{j0}^{m}\binom{m}{j}x^jk0∑nm(knm)xki0∑n(in)xij0∑m(jm)xj ∑k0nm(nmk)xk∑i0n∑j0m(ni)(mj)xij\sum\limits_{k0}^{nm}\binom{nm}{k}x^k\sum\limits_{i0}^{n}\sum\limits_{j0}^{m}\binom{n}{i}\binom{m}{j}x^{ij}k0∑nm(knm)xki0∑nj0∑m(in)(jm)xij ∑k0nm(nmk)xk∑k0nm∑i0k(ni)(mk−i)xk\sum\limits_{k0}^{nm}\binom{nm}{k}x^k\sum\limits_{k0}^{nm}\sum\limits_{i0}^{k}\binom{n}{i}\binom{m}{k-i}x^{k}k0∑nm(knm)xkk0∑nmi0∑k(in)(k−im)xk [xk]∑k0nm(nmk)xk[xk]∑k0nm∑i0k(ni)(mk−i)xk[x^k]\sum\limits_{k0}^{nm}\binom{nm}{k}x^k[x^k]\sum\limits_{k0}^{nm}\sum\limits_{i0}^{k}\binom{n}{i}\binom{m}{k-i}x^{k}[xk]k0∑nm(knm)xk[xk]k0∑nmi0∑k(in)(k−im)xk (nmk)∑i0k(ni)(mk−i)\binom{nm}{k}\sum\limits_{i0}^{k}\binom{n}{i}\binom{m}{k-i}(knm)i0∑k(in)(k−im) 推论 ∑i1n(ni)(ni−1)(2nn−1)\sum\limits_{i1}^n\dbinom ni\dbinom {n}{i-1}\dbinom {2n}{n-1}i1∑n(in)(i−1n)(n−12n) 证明(2nn−1)∑i0n−1(ni)(nn−1−i)∑i0n−1(ni)(ni1)∑i1n(ni)(ni−1)\binom {2n}{n-1} \sum\limits_{i0}^{n-1}\binom ni\binom n{n-1-i}\sum\limits_{i0}^{n-1}\binom ni\binom n{i1}\sum\limits_{i1}^{n}\binom ni\binom n{i-1}(n−12n)i0∑n−1(in)(n−1−in)i0∑n−1(in)(i1n)i1∑n(in)(i−1n) ∑i0m(ni)(mi)(nmm)\sum\limits_{i0}^m\dbinom ni\dbinom mi\dbinom {nm}mi0∑m(in)(im)(mnm) 证明∑i0m(ni)(mi)∑i0m(ni)(mm−i)(nmm)\sum\limits_{i0}^m\binom ni\binom mi\sum\limits_{i0}^m\binom ni\binom m{m-i}\binom {nm}mi0∑m(in)(im)i0∑m(in)(m−im)(mnm)
广义二项式系数
广义二项式系数 : (αi)αi‾i!\dbinom{\alpha}{i}\dfrac{\alpha^{\underline {i}}}{i!}(iα)i!αi α\alphaα可以是实数(或者更多?)
广义二项式定理 (xy)α∑i0∞(αi)xiyk−i(xy)^{\alpha}\sum\limits_{i0}^{\infty}\dbinom{\alpha}{i}x^iy^{k-i}(xy)αi0∑∞(iα)xiyk−i 普通二项式定理求和到α\alphaα就停下是因为之后的组合数都是000可弃掉上指标反转 认识和处理上指标为负(整)数的组合数。 (rk)(−1)k(k−r−1k)\dbinom{r}{k}(-1)^k\dbinom{k-r-1}{k}(kr)(−1)k(kk−r−1) 证明rk‾k!(−1)k(−r)k‾k!(−1)k(−r)(−r1)...(−rk−1)k!(−1)k(k−r−1)k‾k!\frac{r^{\underline{k}}}{k!}\frac{(-1)^k(-r)^{\overline{k}}}{k!}\frac{(-1)^k(-r)(-r1)...(-rk-1)}{k!}\frac{(-1)^k(k-r-1)^{\underline{k}}}{k!}k!rkk!(−1)k(−r)kk!(−1)k(−r)(−r1)...(−rk−1)k!(−1)k(k−r−1)k取一半处理 (2nn)\dbinom{2n}{n}(n2n) 形组合数。 由 xk‾(x−12)k‾(2x)2k‾22kx^{\underline{k}}(x-\frac{1}{2})^{\underline{k}}\frac{(2x)^{\underline{2k}}}{2^{2k}}xk(x−21)k22k(2x)2k 知 nn‾(n−12)n‾(2n)2n‾22nn^{\underline{n}}(n-\frac{1}{2})^{\underline{n}}\frac{(2n)^{\underline{2n}}}{2^{2n}}nn(n−21)n22n(2n)2n nn‾(n−12)n‾(2n)n‾nn‾22nn^{\underline{n}}(n-\frac{1}{2})^{\underline{n}}\frac{(2n)^{\underline{n}}n^{\underline{n}}}{2^{2n}}nn(n−21)n22n(2n)nnn 等式两边同时除以(n!)2(n!)^2(n!)2得到 (nn)(n−12n)122n(2nn)(nn)\binom{n}{n}\binom{n-\frac{1}{2}}{n}\frac{1}{2^{2n}}\binom{2n}{n}\binom{n}{n}(nn)(nn−21)22n1(n2n)(nn) (n−12n)14n(2nn)\binom{n-\frac{1}{2}}{n}\frac{1}{4^n}\binom{2n}{n}(nn−21)4n1(n2n) 反转上指标 (−1)n(12−1n)14n(2nn)(-1)^n\binom{\frac{1}{2}-1}{n}\frac{1}{4^n}\binom{2n}{n}(−1)n(n21−1)4n1(n2n) (2nn)(−4)n(−12n){\color{Goldenrod}\dbinom{2n}{n}(-4)^n\dbinom{-\frac{1}{2}}{n} }(n2n)(−4)n(n−21) ∑i0∞(2ii)xi∑i0∞(−12i)(−4x)i×1(−12−i)(1−4x)−12{\color{Goldenrod}\sum\limits_{i0}^{\infty}\dbinom{2i}{i}x^i\sum\limits_{i0}^{\infty}\dbinom{-\frac{1}{2}}{i}(-4x)^i\times 1^{(-\frac{1}{2}-i)}(1-4x)^{-\frac{1}{2}}}i0∑∞(i2i)xii0∑∞(i−21)(−4x)i×1(−21−i)(1−4x)−21阶乘幂的二项式定理 当 nnn 是自然数时有 (xy)n‾∑i0n(ni)xi‾yn−i‾(xy)^{\underline{n}}\sum\limits_{i0}^n\dbinom{n}{i}x^{\underline i}y^{\underline{n-i}}(xy)ni0∑n(in)xiyn−i (xy)n‾∑i0n(ni)xi‾yn−i‾(xy)^{\overline{n}}\sum\limits_{i0}^n\dbinom{n}{i}x^{\overline i}y^{\overline{n-i}}(xy)ni0∑n(in)xiyn−i
二项式反演
各种反演总结
差分与前缀和
nnn 阶差分是 : Δnf(x)∑i0n(ni)(−1)n−if(xi)\Delta^{n} f(x)\sum\limits_{i0}^n\dbinom{n}{i}(-1)^{n-i}f(xi)Δnf(x)i0∑n(in)(−1)n−if(xi) nnn 阶前缀和是 : Σnf(x)∑i0(ni−1i)f(x−i)\Sigma^{n} f(x)\sum\limits_{i0}\dbinom{ni-1}{i}f(x-i)Σnf(x)i0∑(ini−1)f(x−i)注意,没有指明上界
牛顿级数
若 Ri(x)R_i(x)Ri(x) 是关于 xxx 的 iii 次多项式我们总能在系数合适的时候用 ∑i0mciRi(x)\sum\limits_{i0}^mc_iR_i(x)i0∑mciRi(x) 来描述任意多项式。
现在我们令 Ri(x)(xi)xi‾i!R_i(x)\dbinom{x}{i}\dfrac{x^{\underline i}}{i!}Ri(x)(ix)i!xi这是符合要求的。
我们就能得到牛顿级数F(x)∑i0mF[i](xi)F(x)\sum\limits_{i0}^mF[i]\dbinom{x}{i}F(x)i0∑mF[i](ix)
根据递推公式能得到结论Δx(xk)(xk−1)\Delta_x\dbinom{x}{k}\dbinom{x}{k-1}Δx(kx)(k−1x)
所以ΔnF(x)∑inmF[i](xi−n){\color{GoldenRod}\Delta^nF(x)\sum\limits_{in}^mF[i]\dbinom{x}{i-n}}ΔnF(x)in∑mF[i](i−nx)
对 F(x)∑i0(xi)F[i]F(x)\sum\limits_{i0}\dbinom{x}{i}F[i]F(x)i0∑(ix)F[i] 使用二项式反演可得F[x]∑i0(xi)(−1)m−iF(i){\color{GoldenRod}F[x]\sum\limits_{i0}\dbinom{x}{i}(-1)^{m-i}F(i)}F[x]i0∑(ix)(−1)m−iF(i) 二项式反演是可以NTTNTTNTT卷积加速的所以我们能在 O(nlogn)O(n\log n)O(nlogn) 内做到 0⋯m点值⟺牛顿级数0\cdots m点值\Longleftrightarrow牛顿级数0⋯m点值⟺牛顿级数 。
生成函数与杨辉三角 将杨辉三角可以看作二维数组写成二元生成函数的形式 数组写成二元生成函数的形式 G[n,m](nm)G(x,y)∑i0∑j0(ij)xiyj∑i0xi(y1)i11−x−xy\begin{aligned} G[n,m]\dbinom{n}{m}\\ G(x,y)\sum\limits_{i0}\sum\limits_{j0}\dbinom{i}{j}x^iy^j\\ \sum\limits_{i0}x^i(y1)^i\\ \dfrac{1}{1-x-xy} \end{aligned}G[n,m]G(x,y)(mn)i0∑j0∑(ji)xiyji0∑xi(y1)i1−x−xy1 这个简洁的封闭形式将整个杨辉三角蕴含其中。 如果将 yyy 替换为关于 xxx 的式子或将 xxx 替换为关于 yyy 的式子从二元变成一元 xaybx^ay^bxayb 的系数会根据某些条件合并。 例如 令 yxkyx^kyxk则 [xn]G(x,xk)[xn]∑i0∑j0(ij)xixjk∑ij×kn(ij)[x^n]G(x,x^k)[x^n]\sum\limits_{i0}\sum\limits_{j0}\dbinom{i}{j}x^ix^{jk}\sum\limits_{ij\times kn}\dbinom{i}{j}[xn]G(x,xk)[xn]i0∑j0∑(ji)xixjkij×kn∑(ji) 令 xykxy^kxyk则 [xn]G(yk,y)[xn]∑i0∑j0(ij)xikxj∑i×kjn(ij)[x^n]G(y^k,y)[x^n]\sum\limits_{i0}\sum\limits_{j0}\dbinom{i}{j}x^{ik}x^j\sum\limits_{i\times kjn}\dbinom{i}{j}[xn]G(yk,y)[xn]i0∑j0∑(ji)xikxji×kjn∑(ji) 这是杨辉三角上某个奇怪方向的求和。同时考察封闭形式即可得到系数。 更多的求和 ∑i0m(mi)\sum\limits_{i0}^m\dbinom{m}{i}i0∑m(im) 即为 ∑ij×0m(ij)\sum\limits_{ij\times 0m}\dbinom{i}{j}ij×0m∑(ji)所以令 yx0yx^0yx0 得到 G(x,1)11−2xG(x,1)\dfrac{1}{1-2x}G(x,1)1−2x1。提取系数得 ∑i0m(mi)[xm]11−2x2m\sum\limits_{i0}^m\dbinom{m}{i}[x^m]\dfrac{1}{1-2x}2^mi0∑m(im)[xm]1−2x12m ∑i0m(im2i)\sum\limits_{i0}^m\dbinom{im}{2i}i0∑m(2iim) 注意到 im−(2i)/2mim−(2i)/2mim-(2i)/2mim−(2i)/2mim−(2i)/2mim−(2i)/2m 故上式即为 ∑i−j/2m(ij)\sum\limits_{i-j/2m}\dbinom{i}{j}i−j/2m∑(ji) 。令 yx−1/2yx^{-1/2}yx−1/2 得 G(x,x−1/2)11−x−xG(x,x^{-1/2})\dfrac{1}{1-\sqrt{x}-x}G(x,x−1/2)1−x−x1则 ∑i0m(im2i)[xm]11−x−x[z2m]11−z−z2F2m1\sum\limits_{i0}^m\dbinom{im}{2i}[x^m]\dfrac{1}{1-\sqrt{x}-x}[z^{2m}]\dfrac{1}{1-z-z^2}F_{2m1}i0∑m(2iim)[xm]1−x−x1[z2m]1−z−z21F2m1。其中 11−z−z2\frac{1}{1-z-z^2}1−z−z21 正是斐波那契数列的生成函数除去一个 zzz。
