浅谈容斥

不会数数

Posted by ethan-zhou on November 18, 2021

【本文未完待续】

在前几周学长教了我一道容斥题之后,我发现:我好像没学过容斥!


从全错排开始

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

\[\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
本文为作者原创,转载请注明出处:本文链接



icon