二项式反演学习笔记

定义

一般形式

$$f_n=\sum \limits_{i=0}^{n}(-1)^i\cdot {n\choose i}\cdot g_i\Leftrightarrow g_n=\sum \limits_{i=0}^{n}(-1)^{i}\cdot {n\choose i}\cdot f_i$$

OI中常见的形式

$$f_n=\sum \limits_{i=0}^{n}{n\choose i}\cdot g_i\Leftrightarrow g_n=\sum \limits_{i=0}^{n}(-1)^{n-i}\cdot {n\choose i}\cdot f_i$$

代数证明

直接按上边讲的带进去大力推式子就可以辣~

$$a_{i, j}={i\choose j}, \ b_{i, j}=(-1)^{i-j}\cdot {i\choose j}$$

$$\begin{split}\sum \limits_{j=i}^{n}a_{j, i}\cdot b_{n, j}
&=\sum \limits_{j=i}^{n}{j\choose i}\cdot {n\choose j}\cdot (-1)^{n-j}\\
&=\sum \limits_{j=i}^{n}{n\choose i}\cdot {n-i\choose j-i}\cdot (-1)^{n-j}\\
&={n\choose i}\cdot \sum \limits_{j=0}^{n-i}{n-i\choose j}\cdot (-1)^{n-i-j}\\
&=[i==n]
\end{split}$$

证毕撒花~

感性理解

假设有一个集合$S$,有一些特别的集合$A_{1\dots n}$,已知任意$i$个集合的交集大小均为$g_i$,特别地,$g_0=|S|$,问$S$中不在特别集合里的部分的大小

$$\begin{split}&\ \ \ \ \ |\complement_SA_1\cap\complement_SA_1\cap \dots \cap \complement_SA_n|\\
&=|S|-\sum |A_{i}|+\sum |A_{i}\cap A_j|+\dots +(-1)^n|A_1\cap A_2\cap \dots\cap A_n|\\
&=g_0-{n\choose 1}g_1+{n\choose 2}g_2+\dots +(-1)^n\cdot {n\choose n}\cdot g_n\\
&=\sum \limits_{i=0}^{n}(-1)^i\cdot {n\choose i}\cdot g_i
\end{split}$$

假设$f_i$为任意$i$个补集的交集的大小,特别地,$f_0=|S|$,则显然有$$f_n=
\sum \limits_{i=0}^{n}(-1)^i\cdot {n\choose i}\cdot g_i $$通过容斥原理,我们还可以得到$$\begin{split} &\ \ \ \ \ |A_1\cap A_2\cap \dots \cap A_n|\\
&=|S|-\sum |\complement_SA_i|+\sum |\complement_SA_i\cap \complement SA_j|+\dots +(-1)^n\cdot |\complement_SA_1\cap\complement_SA_1\cap \dots \cap \complement_SA_n|\\ &=f_0+{n\choose 1}\cdot f_1-{n\choose 2}\cdot f_2+\dots +(-1)^n\cdot {n\choose n}\cdot f_n\\ &=\sum \limits_{i=0}^n(-1)^i\cdot {n\choose i}\cdot f_i
\end{split}$$

故原式成立~

应用

求Stirling数

将$n^k=\sum \limits_{i=0}^{n}S_k^i\cdot {n\choose i}\cdot i!$带入二项式反演得
$$\begin{split}
S_k^n\cdot n!&=\sum \limits_{i=0}^n(-1)^{n-i}\cdot {n\choose i}\cdot i^k\\
S_k^n&=\sum \limits_{i=0}^n\frac{(-1)^{n-i}}{(n-i)!}\cdot \frac{i^k}{i!}
\end{split}$$

使用NTT加速求卷积的过程即可

发表评论

电子邮件地址不会被公开。 必填项已用*标注