容斥原理

深碍√TFBOYSˉ_ 2021-12-16 03:04 344阅读 0赞

*  容斥原理
    
     *  基本的容斥原理
     *  反演
     *  二项式反演
     *  Möbius反演

## 容斥原理 ##

大力推荐《组合数学》第6章第一节与最后一节。

### 基本的容斥原理 ###

求任意相交集合的并集中对象个数的公式

\\\[\\overline\{A\_1\}\\bigcap \\overline\{A\_2\}\\bigcap...\\bigcap\\overline\{A\_m\}=|S| - \\sum|A\_i|+\\sum|A\_i\\bigcap A\_j|-|A\_i\\bigcap A\_j\\bigcap A\_k|+....+(-1)^m|\\bigcap\_\{i=1\}^n A\_i|（1.1）\\\]  
(P.S. S是全集)

解释：

A\_i是一个性质.

求不满足**这些性质**的集合的大小.

证明的思路：只要证明满足条件的对答案贡献1,不满足条件的对答案贡献0

证明：

一个元素不满足上述所有性质.

那么贡献为

\$1-0+0...(-1)^m0=1\$

满足其中n个性质的元素x

对于x.

x对于集合S的贡献是1 = \$\\dbinom\{n\}\{0\}\$

对于满足一条性质的\$-\\dbinom\{n\}\{1\}\$

满足两条性质的\$\\dbinom\{n\}\{2\}\$

。。。

根据二项式定理可得

\$\\dbinom\{n\}\{0\} - \\dbinom\{n\}\{1\} + \\dbinom\{n\}\{2\} - \\dbinom\{n\}\{3\}+....(-1)^m\\dbinom\{n\}\{n\} = 0\$

\$(1-1)^n=\\sum\_\{k=0\}^n -1^k\\dbinom\{n\}\{k\}\$

还有一个公式

集合S中至少具有性质\$A\_1,A\_2,A\_3....A\_m\$之一的元素个数

\$|A\_1\\bigcup A\_2\\bigcup A\_3....\\bigcup A\_m| = \\sum\_\{|A\_i|\}-\\sum|A\_i\\bigcap A\_j|+....\$

证明：

\$|A\_1\\bigcup A\_2\\bigcup A\_3....\\bigcup A\_m| = |S| - \\overline\{|A\_1\\bigcup A\_2\\bigcup A\_3....\\bigcup A\_m|\}\$

又有

\$\\overline\{|A\_1\\bigcup A\_2\\bigcup A\_3....\\bigcup A\_m|\} = \\overline\{A\_1\}\\bigcap\\overline\{A\_2\}\\bigcap\\overline\{A\_3\}\\bigcap...\\overline\\bigcap\{A\_m\}\$

就有

\$|A\_1\\bigcup A\_2\\bigcup A\_3....\\bigcup A\_m| = |S| - \\overline\{A\_1\}\\bigcap\\overline\{A\_2\}\\bigcap\\overline\{A\_3\}\\bigcap...\\overline\\bigcap\{A\_m\}(1.2)\$

与公式1.1结合起来就得到1.2了

题目：  
错位排列

我们先说点水爆了的内容吧！说从前有 n 个人，编号为 1, … , n。这 n 个人站成一排，编
    号为 i 的人不能站在第 i 个。求方案数。 n ≤ $10^5$

`转自`[vfk的炫酷反演魔术][vfk]

直接搞非常困难，考虑容斥原理设\$A\_i\$表示第i个人在i位置上的方案数  
因为我们要求的是不满足\$A\_i(\\forall i)\$  
所以套用公式1.1

转化一下就是下面这个式子：  
\$ANS = \\sum\_\{k = 0\}^n (-1)^k \* \\dbinom\{n\}\{k\} (n - k)!\$

### 反演 ###

对于一个数列f，另外一个数列g，满足如下条件

\$g\_n = \\sum\_\{i=0\}^n a\_\{ni\}f\_i\$

反演就是利用g来表示f

\$f\_n = \\sum\_\{i = 0\}^n b\_\{ni\}g\_i\$

### 二项式反演 ###

二项式反演：

\$f(n) = \\sum\_\{i = 0\}^\{n\} (-1)^\{i\}\\binom\{n\}\{i\}g(i) \\Leftrightarrow g(n) = \\sum\_\{i = 0\}^\{n\} (-1)^\{i\} \\binom\{n\}\{i\}f(i)\$

\$f(n) = \\sum\_\{i = 0\}^\{n\}\\binom\{n\}\{i\}g(i) \\Leftrightarrow g(n) = \\sum\_\{i = 0\}^\{n\} (-1)^\{n - i\} \\binom\{n\}\{i\} f(i)\$

证明详见：[sigongzi][]

还有另外两种形式

\$f(k) = \\sum\_\{i = k\}^\{n\} \\binom\{i\}\{k\}g(i) \\Leftrightarrow g(k) = \\sum\_\{i = k\}^\{n\} (-1)^\{i - k\} \\binom\{i\}\{k\}f(i)\$

\$f(k) = \\sum\_\{i = k\}^\{n\} (-1)^\{i\}\\binom\{i\}\{k\}g(i) \\Leftrightarrow g(k) = \\sum\_\{i = k\}^\{n\} (-1)^\{i\} \\binom\{i\}\{k\}f(i)\$  
题目：[戳这][Link 1]

### Möbius反演 ###

子集反演

我们在\$n\$元集合中定义一个函数\$F(Xm)\$

补充一点偏序集的概念：

eg：记号：

定义了偏序\$\\le\$的集合X有时也叫做偏序集，记作\$（x，\\le）\$

转载于:https://www.cnblogs.com/gaozhuoyuan/p/10590770.html

[vfk]: http://vfleaking.blog.uoj.ac/slide/87#/
[sigongzi]: https://www.cnblogs.com/ivorysi/
[Link 1]: https://www.cnblogs.com/gaozhuoyuan/p/10595676.html#%E4%BA%8C%E9%A1%B9%E5%BC%8F%E5%8F%8D%E6%BC%94%E4%BE%8B%E9%A2%98