二项式反演-526互联

组合恒等式

\[\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}\\ \binom{n}{n_1,n_2,\ldots,n_k}=\frac{(n_1+n_2+\ldots+n_k)!}{n_1!n_2!\ldots n_k!}\\ \sum_{i=0}^{n}\binom{n}{i}a^ib^{n-i}=(a+b)^n\\ \sum_{n_1+n_2+\ldots+n_k=n}\binom{n}{n_1,n_2,\ldots,n_k}x_1^{n_1}x_2^{n_2}\ldots x_k^{n_k}=(x_1+x_2+\ldots+x_k)^n\\ \sum_{i=0}^{n}\binom{n}{i}=2^n(a=b=1)\\ \sum_{i=0}^n(-1)^i\binom{n}{i}=[n=0](a=1,b=-1)\\ \sum_{i=0}^{m}\binom{n}{i}\binom{m}{m-i}=\binom{n+m}{m}(n\ge m)\\ \sum_{i=0}^{n}\binom{n}{i}^2=\binom{2n}{n}(上式令n=m)\\ \sum_{i=0}^{n}i\binom{n}{i}=n2^{n-1}(对第5行求导)\\ \sum_{i=0}^{n}i^2\binom{n}{i}=n(n-1)2^{n-2}\\ \sum_{i=0}^{n}\binom{i}{k}=\binom{n+1}{k+1}\\ \binom{n}{r}\binom{r}{k}=\binom{n}{k}\binom{n-k}{r-k}\\ \sum_{i=0}^{n}\binom{n-i}{i}=Fib_{n+1}\\ \sum_{k=0}^r\binom{m}{k}\binom{n}{r-k}=\binom{n+m}{r}\\ \sum_{k=0}^n\binom{m}{k}\binom{n}{k}=\binom{n+m}{m} \]

以下是离散数学的习题

\[1.求证\sum_{k=0}^n(-1)^k\binom{n}{k}2^{n-k}=1 \]

证明：

\[Ans=(-1+2)^n=1 \]

\[2.求证\sum_{k=1}^{n+1}\frac{1}{k}\binom{n}{k-1}=\frac{2^{n+1}-1}{n+1} \]

~~证明:不会~~

写一下std：

\[法一: (1+x)^n=\sum_{k=0}^n\binom{n}{k}x^k\\ \int_0^n (1+x)^n=\int_0^n \sum_{k=0}^n\binom{n}{k}\\ \frac{(x+1)^{n+1}-1}{n+1}=\sum_{jk=0}^n\binom{n}{k}\frac{x^{k+1}}{k+1} \\令x=1,得\frac{2^{n+1}-1}{n+1}=\sum_{k=0}^n\binom{n}{k}\frac{1}{k+1}=\sum_{k=1}^{n+1}\frac{1}{k}\binom{n}{k-1} \\\\ 法二:\sum_{k=1}^{n+1}\frac{1}{k}\binom{n}{k-1}=1+\sum_{k=2}^{n+1}\frac{1}{k}\binom{n}{k-1}=1+\sum_{k=1}^{n}\frac{1}{k+1}\binom{n}{k} \\因为\binom{n}{k}=\frac{n}{k}\binom{n-1}{k-1},所以\binom{n}{k}=\frac{k+1}{n+1}\binom{n+1}{k+1}\\ Ans=1+\sum_{k=1}^n\frac{1}{n+1}\binom{n+1}{k+1}=\sum_{k=0}^n\frac{1}{n+1}\binom{n+1}{k+1}\\=\frac{1}{n+1}\sum_{k=0}^{n}\binom{n+1}{k+1}=\frac{2^{n+1}-1}{n+1} \\ \]

\[3.\sum_{k=0}^m\binom{n-k}{m-k} \\=\sum_{k=0}^{m}\binom{n-k}{n-m}=\sum_{k=n-m}^m\binom{k}{n-m}=\sum_{k=0}^{m}\binom{k}{n-m} \\因为\sum_{i=0}^n\binom{i}{k}=\binom{n+1}{k+1} \\ Ans=\binom{n+1}{n-m+1}=\binom{n+1}{m} \\ \]

\[4.求证\sum_{k=r}^n(-1)^k\binom{n}{k}\binom{k}{r}=0 \\Ans=\sum_{k=r}^n(-1)^k\binom{n}{r}\binom{n-r}{k-r}=\sum_{k'=0}^{n-r}(-1)^{k'+r}\binom{n}{r}\binom{n-r}{k'} \\=(-1)^r\binom{n}{r}\sum_{k'=0}^{n-r}(-1)^{k'}\binom{n-r}{k'}=0 \\ \]

\[5.求证：\sum_{k=0}^{n-1}\binom{n}{k}\binom{n}{k+1}=\binom{2n}{n-1} \\Ans=\sum_{k=0}^{n-1}\binom{n}{k}\binom{n}{(n-1)-k} \\因为\sum_{k=0}^{r}\binom{n}{r}\binom{m}{r-k}=\binom{n+m}{r} \\所以Ans=\binom{2n}{n-1} \\ \]

\[6.\sum_{k=0}^n(-1)^k\frac{1}{k+1}\binom{n}{k}=\frac{1}{n+1} \\Ans=\sum_{k=0}^n(-1)^k\frac{1}{n+1}\binom{n+1}{k+1}=\frac{1}{n+1}\sum_{k=1}^n(-1)^{k+1}\binom{n}{k} \\=\frac{1}{n+1}(1-\sum_{k=0}^n(-1)^k\binom{n}{k})=\frac{1}{n+1} \\ \]

\[7.\sum_{k=0}^m\binom{n-k}{m-k}\binom{r+k}{k}=\binom{n+r+1}{m} \]

不贴证明了

二项式反演

记\(f_n\)表示恰好使用 \(n\) 个不同元素形成特定结构的方案数，\(g_n\) 表示从 \(n\) 个不同元素中选出 \(i \geq 0\) 个元素形成特定结构的总方案数。

\[g_n=\sum_{i=0}^{n}\binom{n}{i}f_i \iff f_n=\sum_{i=0}^{n}(-1)^{n-i}\binom{n}{i}g_i \]

证明一下:
将\(g_i\)展开

\[f_n=\sum_{i=0}^n\binom{n}{i}(-1)^{n-i}\sum_{j=0}^i\binom{i}{j}f_j \\ =\sum_{j=0}^nf_j\sum_{i=j}^n\binom{n}{i}\binom{i}{j}(-1)^{n-i} \]

因为

\[\binom{n}{r}\binom{r}{k}=\binom{n}{k}\binom{n-k}{r-k} \]

带入有:

\[f_n=\sum_{j=0}^nf_j\sum_{i=j}^n\binom{n}{j}\binom{n-j}{i-j}(-1)^{n-i}\\ =\sum_{j=0}^n\binom{n}{j}f_j\sum_{i=j}^n\binom{n-j}{i-j}(-1)^{n-i} \]

设\(k=i-j,则k\in[0,n-j]\)

\[f_n=\sum_{j=0}^n\binom{n}{j}f_j\sum_{k=0}^{n-j}\binom{n-j}{k}(-1)^{n-j-k} \]

因为

\[\sum_{i=0}^n\binom{n}{i}(-1)^{n-i}=[n=0] \]

所以：

\[f_n=\sum_{j=0}^n\binom{n}{j}f_j[n-j=0] \\=f_n \]

除了上面那个式子以外，还有一个二项式反演的式子很常见，如下，证明过程类似，此处不在赘述。上述的等价式子是“至多\(n\)个/\(n\)种的方案数量”和“恰好
\(n\)个/\(n\)种的方案数量”之间的关系，此处是“至少\(n\)个/\(n\)种的方案数量”和“恰好\(n\)个/\(n\)种的方案数量”。

\[g_k=\sum_{i=k}^{n}\binom{i}{k}f_i\iff f_k=\sum_{i=k}^n(-1)^{i-k}\binom{i}{k}g_i \]

故二项式反演可以归结为一下两个式子

形式1

\(g_n\)表示至多\(n\)个/\(n\)种的方案数量，
\(f_n\)恰好\(n\)个/\(n\)种的方案数量

\[g_n=\sum_{i=0}^{n}\binom{n}{i}f_i \iff f_n=\sum_{i=0}^{n}(-1)^{n-i}\binom{n}{i}g_i \]

形式2

\(g_k\)表示至少个\(k\)/\(k\)种的方案数量，
\(f_k\)恰好\(k\)个/\(k\)种的方案数量

\[g_k=\sum_{i=k}^{n}\binom{i}{k}f_i\iff f_k=\sum_{i=k}^n(-1)^{i-k}\binom{i}{k}g_i \]

除此之外，还有两种：

形式三

\[g_n=\sum_{i=0}^n(-1)^i\binom{n}{i}f_i\iff f_n=\sum_{i=0}^n(-1)^i\binom{n}{i}g_i \]

形式四：

\[g_k=\sum_{i=k}^n(-1)^i\binom{i}{k}f_i\iff f_k=\sum_{i=k}^n(-1)^i\binom{i}{k}g_i \]

这两个式子十分对称，~~但却不常用~~

高维反演

看cmd的博客吧，我不会证。
反正就是系数之积

应用：第二类斯特林数：

\(n\)个不同的球放入\(m\)个不同的盒子，要求每个盒子非空，共有几种方案？

定义\(g_{n,m}\)为\(n\)个不同的球放入\(m\)个不同的盒子，至多有\(m\)个非空的方案数，\(f_{n,m}\)为恰好为\(m\)个的方案数

\[g_{n,m}=m^n \\ g_{n,m}=\sum_{i=0}^m\binom{m}{i}f_{n,i} \\ f_{n,m}=\sum_{i=0}^m(-1)^{m-i}\binom{m}{i}g_{n,i} \]

例题

染色问题

给定从左到右\(n\)个球，将这\(n\)个球用\(k\)种颜色染色。要求相邻两个球必须是不同的颜色，问有多少种染色方案。

用\(g_x\)表示至多\(x\)种颜色的方案数，\(f_x\)表示恰好用\(x\)种的方案数

\[g_k=\sum_{i=0}^k\binom{k}{i}f_i \\ g_k=k(k-1)^{n-1} \\ f_k=\sum_{i=0}^k(-1)^{k-i}\binom{k}{i}g_i \]

信封问题

某人写了 \(n\) 封信和 \(n\) 个信封，如果所有的信都装错了信封。求所有信都装错信封共有多少种不同情况,对\(998244353\)取模。

\(1\le n\le 10^7\)

设\(f_n\)表示恰好有\(n\)个位置错开，\(g_n\)表示至多有\(n\)个位置错开。

则\(g_n=n!\)

\[f_n=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}g_i \\ =\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}i!\\ =\sum_{i=0}^n(-1)^{n-i}\frac{n!}{(n-i)!} \\ =n!\sum_{i=0}^n\frac{(-1)^i}{i!} \]