二项式反演口胡

由于 wtcl ,所以讲得很基础

反演是什么

假设我们已经知道了 (g(n)=sum_{i=0}^n a_{ni}f(j)) 中的 (a) 这个系数数组

我们想要推求的是某一个 (b) 数组,满足 (f(n)=sum_{i=0}^nb_{ni}g(i))

我们考虑 (a,b) 两个数组有什么关系,假装我们现在已经的确找到了这样一个 (b)

那么:

[begin{align} f(n)&=sum_{i=0}^n b_{ni}sum_{j=0}^ia_{ij}f(j)\ &=sum_{i=0}^n f(i)sum_{j=i}^nb_{nj}a_{ji} end{align} ]

所以我们只要求 (sum_{j=i}^nb_{nj}a_{ji}=[i=n]) 即可,这里可以把 (n,i) 看成是一个常量

也就是说,只要我们找到了这种 (b) ,就完成了我们的二项式反演,可以从更直观的角度理解上面那个式子的变化

(上图是白嫖的老师课件里老师白嫖的不知道哪位大佬的图)

二项式反演

基础式

[g(n)=sum_{i=0}^n(-1)^ibinom nif(i) Leftrightarrow f(n)=sum_{i=0}^n(-1)^ibinom ni g(i) ]

我们现在的任务是证明 (sum_{i=j}^n(-1)^{i+j}binom nibinom ij=[j=n])

首先得知道这个东西:

[binom nibinom ij =binom njbinom{n-j}{i-j} ]

一种方式是直接按照组合数定义展开证明,

另一种是组合数的意义:左式是 (n)(i)(i)(j) ,那我不妨直接 (n)(j) ,然后从剩下的 (n-j) 个数中不足没有选的 (i-j)

那么:

[begin{align} &sum_{i=j}^n(-1)^{i+j}binom nibinom ij\ =&sum_{i=j}^n(-1)^{i+j}binom njbinom {n-j}{i-j}\ =&(-1)^jbinom njsum_{i=j}^n (-1)^i binom{n-j}{i-j}\ =&(-1)^jbinom njsum_{i=0}^{n-j}(-1)^{i+j}binom{n-j}{i}\ =&(-1)^{2j}binom njsum_{i=0}^{n-j}(-1)^ibinom{n-j}{i}\ end{align} ]

这个时候我们直接二项式定理,((x+y)^nsum_{i=0}^n binom ni x^i y^{n-i}) 那么

[(-1)^{2j}binom njsum_{i=0}^{n-j}(-1)^ibinom{n-j}{i}=(-1)^{2j}binom nj 0^{n-j} ]

再这里我们令 (0^0=1) ,那么原式显然当且仅当 (j=n) 时为 (1)

由于很难找到这种含 ((-1)^i) 的容斥系数,所以这个基本式作用不大

变式1

[g(n)=sum_{i=0}^nbinom ni f(i)Leftrightarrow f(n)=sum_{i=0}^n(-1)^{n-i}binom ni g(i) ]

很容易证明它,我们的基本式叫做:(g(n)=sum_{i=0}^n(-1)^ibinom nif(i) Leftrightarrow f(n)=sum_{i=0}^n(-1)^ibinom ni g(i))

那么,我们令 (h(x)=(-1)^xf(x)) ,那么,利用基本式,

[g(n)=sum_{i=0}^nbinom ni h(x)Rightarrow frac {h(n)}{(-1)^n}=sum_{i=0}(-1)^ibinom ni g(i)Rightarrow f(n)=sum_{i=0}^n(-1)^{n-i}binom ni g(i) ]

这里给出一个小应用:

题意:错排问题 ,有多少种排列方式,使得 $ p_i neq ?$

解题:虽然我们可以直接套错排公式,这里还是介绍一下二项式反演怎么做

定义 (?(i)) 表示恰好有 (?) 个错开,(?(i)) 表示至多有 (?) 个元素错开

那么有: $ ?(i) = ?!$ , (?(i) = sum_{j=0}(-1)^{i-j}binom ij f(j))

反演一下:(f(n)=sum_{i=0}^n(-1)^{n-i}binom ni g(i))

变式2

[g(n)=sum_{i=n}^mbinom in f(i)Leftrightarrow f(n)=sum_{i=n}^m(-1)^{i-n}binom in g(i) ]

证明略去

推荐这些文章:

数学杂记

二项式反演
形式一:
\[f(n)=\sum_{i=m}^n\binom{n}{i}g(i)\Leftrightarrow g(n)=\sum_{i=m}^n(-1)^{n-i}\binom{n}{i}f(i)
\]形式二:
\[f(n)=\sum_{i=n}^m\binom{i}{n}g(i)\Leftrightarrow g(n)=...

数论 二项式反演 CF1228E题解

设 \(f_{i,j}\) 为恰好 \(i\) 行 \(j\) 列不满足条件的矩阵个数, \(g_{i,j}\) 为钦定 \(i\) 行 \(j\) 列不满足条件的矩阵个数。
容易得到:
\[g_{x,y}=\binom n x \binom n y (k-1)^{n^2-(n-x)(n-y)}k^{(n-x)(n-y)}
\]\[g_...

二项式反演&MIN-MAX容斥目害证

二项式反演
由于用了二项式反演,但是一直没证过,心里一直不踏实于是决定证一下
形式零
首先有多步容斥一开始的柿子:
\[|A_1\bigcup A_2 \bigcup A_3 ..... \bigcup A_n|=\sum\limits_{i=1}^n|A_i|-\sum\limits_{1<=i<j<=n}|A_i\...

关于二维二项式反演的正确性

前言
我第一次看到这个idea是神 \(Fuyuki\) 去年6月份的时候出了一套题目,里面用到了这个东西,不过他当时没有给出证明。后来看到了 \(boshi\) 在 \(Mina\) 上发的计数合集,里面证明了这玩意儿的正确性,我个人认为还是一个非常妙的东西,所以专门开个坑记录一下。
柿子
\[\text{if} \quad f_{n...

「关于我用三个小时推了一遍二项式定理这档事」

前两天考了个模拟赛,有个多项式题中间的递推式形如
\[f_{i,j}=f_{i-1,j-1}+(2^j-1)f_{i-1,j}
\]我一眼看出它其实是个 q-analog 理论的 2-斯特林数,然后调了三个小时发现柿子假了,最后到网上卡了个柿子才写对。于是打算找篇论文学习一下这种柿子都是怎么推的。
然后我就找到了论文 A,然后读 A 发...

CF908G&LOJ6697口胡

为什么我从ACAM做到了数位DP啊
考虑枚举前缀顶着最高位和后缀没有顶着的最高位。
考虑计算一个数对答案的贡献。统计 \(t\) 的出现次数记录到 \(c[t]\) 中。
贡献就是 \(\sum_{i=0}^{9}((\sum_{x=0}^{\sum_{j=i}^{9}c[j]-1}i\times10^{x})-(\sum_{x=0}^...

恒等式日记 2022.3.1

其实是昨天计应数课上的一个东西引出的, 总之, 我们要证明
\[\sum_r \frac 1{n-r} \binom r k = \binom n k (H_n - H_k).
\]首先我们需要证明一个 Lemma:
\[\sum_r \frac{(-1)^{r-1}}r \binom n r = H_n
\]其实很简单:
\[\new...

容斥原理证明

假设有 \(n\) 个基础集合 \(E_1\sim E_n\),那么有
\[\left|\bigcup_{i=1}^n E_i\right|=\sum_{k=1}^n (-1)^{k+1}\sum_{1\le i_1<i_2<...<i_k\le n}|E_{i_1}\cap E_{i_2}\cap\cdots\cap...

一些公式和定理

公式&定理:

两个互为反演的关系矩阵互逆

二项式反演 1
\(\large F(n) = \displaystyle\sum_{i=0}^{n} (-1)^i \binom{n}{i} G(i) \Longleftrightarrow G(n)=\sum_{i=0}^{n}(-1)^i \binom{n}{i}F(i)\)

...

莫比乌斯反演artalter级服务

莫比乌斯反演artalter级服务
其实啊,这个莫反非常的简单套路,就那么几个模型
1.公式
\[
\begin{aligned}
\text{莫比乌斯反演公式如下:}\\
&F(n)=\sum_{d|n}{f(d)}\\
\iff &f(n)=\sum_{d|n}{\mu(d)F(\frac{n}{d})}
\...

文章标题:二项式反演口胡
文章链接:https://www.dianjilingqu.com/1556.html
本文章来源于网络,版权归原作者所有,如果本站文章侵犯了您的权益,请联系我们删除,联系邮箱:saisai#email.cn,感谢支持理解。
THE END
< <上一篇
下一篇>>