组合恒等式
\[\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\)展开
因为
\[\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\)种的方案数量”。
故二项式反演可以归结为一下两个式子
形式1
\(g_n\)表示至多\(n\)个/\(n\)种的方案数量，
\(f_n\)恰好\(n\)个/\(n\)种的方案数量
形式2
\(g_k\)表示至少个\(k\)/\(k\)种的方案数量，
\(f_k\)恰好\(k\)个/\(k\)种的方案数量
除此之外，还有两种：
形式三
\[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!} \]P4859 已经没有什么好害怕的了
给定两个长度为\(n(1\le n\le 2000)\)
的数组{\(a_i\)},{\(b_i\)}，将其两两配对，求有多少种配对方法使得\(a_i>b_i\)的对数比\(a_i\le b_i\)的对数恰好多\(k\)个。
设\(a_i>b_i\)的对数为\(x\)，则\(x+(x-k)=n\)
即\(x=\frac{n+k}{2}\),
将\(a,b\)排序，然后预处理出\(c_i\)：表示\(b\)中有多少个数比\(a_i\)小
设\(f_{i,j}\)表示前\(i\)个数中至少有\(j\)个数满足\(a_k>b_k\)
然后是状态转移：
- 一种是前\(i-1\)个数已经匹配了\(j\)个数
- 另一种是前\(i-1\)个数匹配了\(j-1\)个数，自己还有\(c_i-(j-1)\)个数可用
此时设\(f_i\)为恰好有\(n\)对的情况，\(g_i\)为至少有\(i\)对的情况
其余的位置可以任意填值，也就是全排列：
\[g_i=g_{n,i}\times (n-i)! \]因为
\[g_k=\sum_{i=k}^n\binom{i}{k}f_i \]带入形式2可得:
\[f_k=\sum_{i=k}^n(-1)^{i-k}\binom{k}{i}g_i \]BZOJ2839 集合计数
一个包含\(n(1\le n\le 10^6)\)个不同的数的有\(2^n\)个子集，重这些子集中取出若干集合（至少\(1\)个），使它们的交集元素个数恰好为\(k\)，求解方案数，答案对\(10^9+7\)
取模。
设\(f_k\)为恰好交集为\(k\)个，\(g_k\)为至少有\(k\)个
对于\(g_k\)，我们随意选择\(k\)个，为\(\binom{n}{k}\),然后剩余的随便选，方案数为\(2^{n-k}\),然后我们要选出若干个集合，而且不能为空,方案数为\(2^{2^{n-k}}-1\),故\(g_k=\binom{n}{k}(2^{2^{n-k}}-1)\)
然后反演
\(f_k=\sum_{i=k}^n(-1)^{i-k}\binom{i}{k}g_i\)