组合数学详解

正题

排列组合

$$\begin{gathered} (a+b{)}^m=\sum _{i=0}^m{C}_m^i{a}^i{b}^{m-i} \\ \sum _{i=0}^m{C}_n^i{C}_m^i=C_{n+m}^m \\ \sum _{i=0}^{n}i{C}_n^i=2^{n-1}n \\ \sum _{i=0}^n{i}^2{C}_n^i=2^{n-2}n(n+1) \\ \sum _{i=0}^n{C}_i^k=C_{n+1}^{k+1} \\ {C}_n^r{C}_r^k=C_n^k{C}_{n-k}^{r-k} \\ {C}_n^k{k}^{\underline{i}}=C_{n-i}^{k-i}{n}^{\underline{i}} \end{gathered}$$
1.广义二项式定理。
2.可以看成 $n$ 个里面选 $i$ 个，再从 $m$ 个里面选 $m-i$ 个，考虑直接从前 $n$ 个和后 $m$ 个里面选出 $m$ 个，每一个方案肯定都会被算到。
3.相当于计算的是子集大小和，对于每一个元素来说，被计算的次数肯定是$2^{n-1}$，当然也可以用导数证明
4.计算的是选出一个子集，子集大小的平方和，相当于把两个球放进 $i$ 个有标号的箱子的方案数，同样可以反着考虑，假若只有一个箱子有球，那么答案是 $n{2}^{n-1}$ ，如果有两个箱子有球，那么答案就是 $n(n-1)2^{n-2}$ 。同样也可以用生成函数求导证明。
考虑把上面的两条式子推广，那么就有
$$\sum _{i=0}^n{i}^k{C}_n^i=\sum _{j=1}^k{C}_n^{j}S(k,j)j!2^{n-j}$$
5.第五条可以用组合意义来证明，考虑在一个长为 $n+1$ 的序列当中选出 $k+1$ 个数，左边相当于枚举所选中的最右边的数。用杨辉三角也很好证明，大概 $C_k^k$ 就是将挪到 $C_{k+1}^{k+1}$上，然后不断两两相加就可以得到。
6.直接考虑每个点被染成第几种颜色就可以了。
7.化系数可得

二项式反演

二项式反演基于二项式定理，证明将两式相互带入即可，不再赘述。
f ( n ) = ∑ k = 0 n ( − 1 ) k C n k g ( k ) ⇔ g ( n ) = ∑ k = 0 n ( − 1 ) k C n k f ( k ) f ( n ) = ∑ k = 0 n C n k g ( k ) ⇔ g ( n ) = ∑ k = 0 n ( − 1 ) n − k C n k f ( k ) f ( k ) = ∑ i = k n ( − 1 ) i C i k g ( i ) ⇔ g ( k ) = ∑ i = k n ( − 1 ) i C i k f ( i ) f ( k ) = ∑ i = k n C i k g ( i ) ⇔ g ( k ) = ∑ i = k n ( − 1 ) i − k C i k f ( i ) f(n)=\sum_{k=0}^n(-1)^kC_n^kg(k)\Leftrightarrow g(n)=\sum_{k=0}^n(-1)^kC_n^kf(k)\\ f(n)=\sum_{k=0}^nC_n^kg(k)\Leftrightarrow g(n)=\sum_{k=0}^n(-1)^{n-k}C_n^kf(k)\\ f(k)=\sum_{i=k}^n (-1)^iC_i^kg(i)\Leftrightarrow g(k)=\sum_{i=k}^n(-1)^iC_i^kf(i)\\ f(k)=\sum_{i=k}^nC_i^kg(i)\Leftrightarrow g(k)=\sum_{i=k}^n (-1)^{i-k}C_i^kf(i)\\ f(n)=k=0∑n​(−1)kCnk​g(k)⇔g(n)=k=0∑n​(−1)