二项式反演学习笔记
yangzichen1203
·
·
算法·理论
:::success[二项式反演的内容和意义]
设 f_n 表示恰好用 n 个物品的方案数，g_n 表示 n 个物品任意选的方案数。
如果我们知道 f 求 g，显然
g_n=\sum_{i=0}^n\binom{n}{i}f_i
但通常 g 是好求的，f 不好求，此时就可以使用二项式反演求出 f：
f_n=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}g_i
:::
:::::::::success[二项式反演的证明]
我们先证明以下两个引理：
1.\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}=[n=0]
2.\binom{n}{r}\binom{r}{k}=\binom{n}{k}\binom{n-k}{r-k}
::::::info[引理 1 的证明]
:::info[二项式定理]
(ax+b)^n=\sum_{i=0}^na^ib^{n-i}\binom{n}{i}x^i
:::
当 n=0 时，答案显然为 1。
当 n\neq0 时
\because(x-1)^n=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}x^i
\therefore\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}=(1-1)^n=0
即
\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}=[n=0]
Q.E.D.
::::::
::::::info[引理 2 的证明]
:::info[组合数计算公式]
\binom{n}{m}=\frac{n!}{m!(n-m)!}
:::
左式
=\frac{n!}{r!(n-r)!}\cdot\frac{r!}{k!(r-k)!}
=\frac{n!}{k!(n-r)!(r-k)!}
右式
=\frac{n!}{k!(n-k)!}\cdot\frac{(n-k)!}{(n-r)!(r-k)!}
=\frac{n!}{k!(n-r)!(r-k)!}
Q.E.D.
::::::
证明完引理后，我们开始正式证明：
考虑从结论出发
\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}g_i
=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}\sum_{j=0}^i\binom{i}{j}f_j
=\sum_{i=0}^n\sum_{j=0}^i(-1)^{n-i}\binom{n}{i}\binom{i}{j}f_j
=\sum_{j=0}^n\sum_{i=j}^n(-1)^{n-i}\binom{n}{i}\binom{i}{j}f_j
=\sum_{j=0}^n\sum_{i=j}^n(-1)^{n-i}\binom{n}{j}\binom{n-j}{i-j}f_j
=\sum_{j=0}^n\binom{n}{j}f_j\sum_{i=j}^n(-1)^{n-i}\binom{n-j}{i-j}
推不下去了，考虑换元 k=i-j，即 i=j+k。
=\sum_{j=0}^n\binom{n}{j}f_j\sum_{k=0}^{n-j}(-1)^{n-(j+k)}\binom{n-j}{k}
=\sum_{j=0}^n\binom{n}{j}f_j\sum_{k=0}^{n-j}(-1)^{(n-j)-k}\binom{n-j}{k}
=\sum_{j=0}^n\binom{n}{j}f_j[n-j=0]
=\binom{n}{n}f_n
=f_n
Q.E.D.
:::::::::