容斥原理

容斥原理是一种重要的组合数学方法，可以让你求解任意大小的集合，或者计算复合事件的概率。

定理：

            在计数时，必须注意无一重复，无一遗漏。为了使重叠部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理。

德摩根(De Morgan)定理

     若A和B是集合U的子集，则 

 

原理：

     1。如果被计数的事物有A、B两类，那么，A类B类元素个数总和= 属于A类元素个数+ 属于B类元素个数—既是A类又是B类的元素个数 。

               （A∪B = A+B - A∩B)

        2。如果被计数的事物有A、B、C三类，那么，A类和B类和C类元素个数总和= A类元素个数+ B类元素个数+C类元素个数—既是A类又是B类的元                素个数—既是A类又是C类的元素个数—既是B类又是C类的元素个数+既是A类又是B类而且是C类的元素个数。

               （A∪B∪C = A+B+C - A∩B - B∩C - C∩A + A∩B∩C）

应用：

一个简单的排列问题

        由0到9的数字组成排列，要求第一个数大于1，最后一个数小于8，一共有多少种排列？

         我们可以来计算它的逆问题，即第一个元素<=1或者最后一个元素>=8的情况。

         我们设第一个元素<=1时有X组排列，最后一个元素>=8时有Y组排列。那么通过容斥原理来解决就可以写成：

          

         经过简单的组合运算，我们得到了结果：

         

         然后被总的排列数10!减，就是最终的答案了。

2.        （0,1,2）序列问题

         长度为n的由数字0，1，2组成的序列，要求每个数字至少出现1次，这样的序列有多少种？

         同样的，我们转向它的逆问题。也就是不出现这些数字的序列 不出现其中某些数字的序列。

         我们定义Ai(i=0…2)表示不出现数字i的序列数，那么由容斥原理，我们得到该逆问题的结果为：

         

        可以发现每个Ai的值都为2^n（因为这些序列中只能包含两种数字）。而所有的两两组合都为1（它们只包含1种                      数字）。最后，三个集合的交集为0。（因为它不包含数字，所以不存在）

        要记得我们解决的是它的逆问题，所以要用总数减掉，得到最终结果：

         

方程整数解问题

         给出一个方程：

        

         其中。

        求这个方程的整数解有多少组。

        我们先不去理会xi<=8的条件，来考虑所有正整数解的情况。这个很容易用组合数来求解，我们要把20个元素分成6组，也就         是添加5块“夹板”，然后在25个位置中找5块“夹板”的位置。

         

         然后通过容斥原理来讨论它的逆问题，也就是x>=9时的解。

         我们定义Ak为xk>=9并且其他xi>=0时的集合，同样我们用上面的添加“夹板”法来计算Ak的大小，因为有9个位置已经           被xk所利用了，所以：

         

         然后计算两个这样的集合Ak、Ap的交集：

         

         因为所有x的和不能超过20，所以三个或三个以上这样的集合时是不能同时出现的，它们的交集都为0。最后我们用总数剪         掉用容斥原理所求逆问题的答案，就得到了最终结果：

         

求指定区间内与n互素的数的个数：

       给出整数n和r。求区间[1;r]中与n互素的数的个数。

         去解决它的逆问题，求不与n互素的数的个数。

         考虑n的所有素因子pi(i=1…k)

         在[1;r]中有多少数能被pi整除呢？它就是：

       

         然而，如果我们单纯将所有结果相加，会得到错误答案。有些数可能被统计多次（被好几个素因子整除）。所以，我们要         运用容斥原理来解决。

         我们可以用2^k的算法求出所有的pi组合，然后计算每种组合的pi乘积，通过容斥原理来对结果进行加减处理。

         关于此问题的最终实现：

求在给定区间内，能被给定集合至少一个数整除的数个数

       给出n个整数ai和整数r。求在区间[1;r]中，至少能被一个ai整除的数有多少。

         解决此题的思路和上题差不多，计算ai所能组成的各种集合（这里将集合中ai的最小公倍数作为除数）在区间中满足的数的个数，然后利用容                  斥原理实现加减。

         此题中实现所有集合的枚举，需要2^n的复杂度，求解lcm需要O(nlogr)的复杂度。

能满足一定数目匹配的字符串的个数问题

       给出n个匹配串，它们长度相同，其中有一些’?’表示待匹配的字母。然后给出一个整数k，求能正好匹配k个匹配串的字符串的个数。更进一                    步，求至少匹配k个匹配串的字符串的个数。

         首先我们会发现，我们很容易找到能匹配所有匹配串的字符串。只需要对比所有匹配串，去在每一列中找出现的字母（或者这一列全是’?’，或              者这一列出现了唯一的字母，否则这样的字符串就存在），最后所有字母组成的单词即为所求。

         现在我们来学习如何解决第一个问题：能正好匹配k个匹配串的字符串。

         我们在n个匹配串中选出k个，作为集合X，统计满足集合X中匹配的字符串数。求解这个问题时应用容斥原理，对X的所有超集进行运算，得到                 每个X集合的结果：

       

         此处f(Y)代表满足匹配集合Y的字符串数。

         如果我们将所有的ans(X)相加，就可以得到最终结果：

         

         这样，就得到了一个复杂度的解法。

        这个算法可以作一些改进，因为在求解ans(X)时有些Y集合是重复的。

         回到利用容斥原理公式可以发现，当选定一个Y时，所有 中X的结果都是相同的，其符号都为。所以可以用如下公式求解：

         

        这样就得到了一个复杂度的解法。

        现在我们来求解第二个问题：能满足至少k个匹配的字符串有多少个。

        显然的，我们可以用问题一的方法来计算满足k到n的所有结果。问题一的结论依然成立，不同之处在于这个问题中的X不是大小都为k的，而是>=k的所有集合。

        如此进行计算，最后将f(Y)作为另一个因子：将所有的ans做和，有点类似二项式展开：

在《具体数学》( Graham, Knuth, Patashnik. "Concrete Mathematics" [1998] )中，介绍了一个著名的关于二项式系数的公式：

根据这个公式，可以将前面的结果进行化简：

那么，对于这个问题，我们也得到了一个的解法：

路径的数目问题

       在一个的方格阵中，有k个格子是不可穿越的墙。一开始在格子(1,1)（最左下角的格子）中有一个机器人。这个机器人只能向上或向右行进，最后它将到达           位于格子(n,m)的笼子里，其间不能经过障碍物格子。求一共有多少种路线可以到达终点。

         为了方便区分所有障碍物格子，我们建立坐标系，用(x,y)表示格子的坐标。

         首先我们考虑没有障碍物的时候：也就是如何求从一个点到另一个点的路径数。如果从一个点在一个方向要走x个格子，在另一个方向要走y个格子，那么通过简单的           组合原理可以得知结果为：

         

         现在来考虑有障碍物时的情况，我们可以利用容斥原理：求出至少经过一个障碍物时的路径数。

         对于这个例子，你可以枚举所有障碍物的子集，作为需要要经过的，计算经过该集合障碍物的路径数（求从原点到第一个障碍物的路径数、第一个障碍物到第二个障          碍物的路径数…最后对这些路径数求乘积），然后通过容斥原理，对这些结果作加法或减法。

         然而，它是一个非多项式的解法，复杂度。下面我们将介绍一个多项式的解法。

         我们运用动态规划：令d[i][j]代表从第i个点到第j个点，不经过任何障碍物时的路径数（当然除了i和j）。那么我们总共需要k+2个点，包括k个障碍物点以及起点和终          点。

         首先我们算出从i点到j点的所有路径数，然后减掉经过障碍物的那些“坏”的路线。让我们看看如何计算“坏”的路线：枚举i和j之间的所有障碍物点i<l<j，那么从i到j                    的“坏”路径数就是所有d[i][l]和d[l][j]的乘积最后求和。再被总路径数减掉就是d[i][j]的结果。

         我们已经知道计算总路径数的复杂度为 ，那么该解法的总复杂度为 。

 

        （译注：当然也有O(nm)的dp解法，根据n、m

上一篇： 容斥原理

下一篇： 算法基础学习笔记 - ⑬ 高斯消除法 组合计数法 容差原则