【本文未完待续】
在前几周学长教了我一道容斥题之后，我发现：我好像没学过容斥！
从全错排开始
全错排有一个通项公式，这个式子固然可以用组合方式证明，但这里用代数方式再来推一遍，更加本质一些。
\[\begin{aligned} Ans & = \sum _{所有排列p}\prod_{i = 1}^n [p_i\neq i] \cr 因为&[p_i\neq i]的条件不好弄，考虑将其转化为[p_i = i]\cr & = \sum _{所有排列p}\prod_{i = 1}^n (1-[p_i = i])\cr & = \sum _{所有排列p}\sum_{s\subseteq [1,n]}(-1)^{n-|s|}\prod_{i \in s} [p_i = i]\cr 发现&每个集合的贡献只与其大小有关，考虑枚举其大小\cr & = \sum _{所有排列p}\sum_{j=1}^n(-1)^{n-j}\sum_{s\subseteq [1,n],|s|=j}\prod_{i \in s} [p_i = i]\cr 来一&手换序求和\cr & = \sum_{j=1}^n(-1)^{n-j}\binom{n}{j} \sum _{所有排列p}\prod_{i \in s} [p_i = i]\cr \end{aligned}\]于是把问题转化成了：钦定排列中若干个位置与值对应，剩下的位置不管的排列个数。
这个问题很好解决，不再赘述。
在容斥问题中，最终问题往往都转化成这样的形式：钦定满足k个条件，剩下的条件不管。
K错排
作者：@ethan-enhe
本文为作者原创，转载请注明出处：本文链接
阅读量: