浅谈容斥

【本文未完待续】

在前几周学长教了我一道容斥题之后，我发现：我好像没学过容斥！

---

从全错排开始

全错排有一个通项公式，这个式子固然可以用组合方式证明，但这里用代数方式再来推一遍，更加本质一些。

Ans=∑所有排列p∏i=1n[pi≠i]因为[pi≠i]的条件不好弄，考虑将其转化为[pi=i]=∑所有排列p∏i=1n(1−[pi=i])=∑所有排列p∑s⊆[1,n](−1)n−∣s∣∏i∈s[pi=i]发现每个集合的贡献只与其大小有关，考虑枚举其大小=∑所有排列p∑j=1n(−1)n−j∑s⊆[1,n],∣s∣=j∏i∈s[pi=i]来一手换序求和=∑j=1n(−1)n−j(nj)∑所有排列p∏i∈s[pi=i]\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}Ans因为发现来一​=所有排列p∑​i=1∏n​[pi​=i][pi​=i]的条件不好弄，考虑将其转化为[pi​=i]=所有排列p∑​i=1∏n​(1−[pi​=i])=所有排列p∑​s⊆[1,n]∑​(−1)n−∣s∣i∈s∏​[pi​=i]每个集合的贡献只与其大小有关，考虑枚举其大小=所有排列p∑​j=1∑n​(−1)n−js⊆[1,n],∣s∣=j∑​i∈s∏​[pi​=i]手换序求和=j=1∑n​(−1)n−j(jn​)所有排列p∑​i∈s∏​[pi​=i]​

于是把问题转化成了：钦定排列中若干个位置与值对应，剩下的位置不管的排列个数。

这个问题很好解决，不再赘述。

在容斥问题中，最终问题往往都转化成这样的形式：钦定满足k个条件，剩下的条件不管。

---

作者：@ethan-enhe
本文为作者原创，转载请注明出处：本文链接

阅读量 6

---

• Previous
  浅谈tarjan

---