第3章 容斥原理与鸽巢原理
3.1 De Morgan定理
德摩根（De Morgan）定理：若\(A\)和\(B\)是集合\(U\)的子集，则
-
\(\overline{A\cup B}=\overline{A} \cap \overline{B}\)
-
\(\overline{A\cap B}=\overline{A} \cup \overline{B}\)
德摩根定理的推广：
- \(\overline{A_1 \cup A_2 \cup \cdots \cup A_n }=\overline{A_1} \cap \overline{A_2} \cap \cdots \cap \overline{A_n}\)
- \(\overline{A_1 \cap A_2 \cap \cdots \cap A_n }=\overline{A_1} \cup \overline{A_2} \cup \cdots \cup \overline{A_n}\)
3.2 容斥定理
\[|A \cup B \cup C| =|A|+|B|+|C|-|A \cap B| - |A \cap C| - |B \cap C|+|A \cap B \cap C| \]
容斥原理的推广：
设\(A_1,A_2,...A_n\)是\(n\)个有限的集合，则
\[|A_1 \cup A_2 \cup \ldots \cup A_n| =\sum_{i=1}^n\left|A_i\right| -\sum_{i=1}^n \sum_{j>i}\left|A_i \cap A_j\right| +\sum_{\mathrm{i}=1}^{\mathrm{n}} \sum_{\mathrm{j}>\mathrm{i}} \sum_{\mathrm{k}>\mathrm{j}}\left|\mathrm{A}_{\mathrm{i}} \cap A_j \cap A_k\right|-\ldots +(-1)^{n-1}\left|A_1 \cap A_2 \cap \ldots \cap A_n\right| \]\[|\overline{A_1} \cap \overline{A_2} \cap \ldots \cap \overline{A_n}|=N-|A_1 \cup A_2 \cup \ldots \cup A_n| \]3.3 容斥原理举例
例题：求从1到600的整数中能被2、3、5除尽的数的个数和不能被2、3、5除尽的个数。
解：令A、B、C分别为从1到600的整数中被2、3、5除尽的数的集合。
\(|A|=\lfloor\frac{600}{2}\rfloor=300,|B|=\lfloor\frac{600}{3}\rfloor=200,|C|=\lfloor\frac{600}{5}\rfloor=120\)，
\(|A \cap B|=\lfloor\frac{600}{2\times3}\rfloor=100,|A \cap C|=\lfloor\frac{600}{2\times5}\rfloor=60,|B \cap C|=\lfloor\frac{600}{3\times5}\rfloor=40\)，
\(|A \cap B \cap C|=\lfloor\frac{600}{2\times3\times5}\rfloor=20\)，
被2、3,、5除尽的数的个数为
\[|A \cup B \cup C| =|A|+|B|+|C| - (|A \cap B| - |A \cap C| - |B \cap C|)+|A \cap B \cap C| =300+200+120-(100+60+45)-20=400 \]不能被2、3,、5除尽的数的个数为
\[|\overline{A} \cap \overline{B} \cap \overline{C}|=N-|A \cup B \cup C|=600-400=200 \]例题：求由a、b、c、d四个字母构成的\(n\)位符号串中，a、b、c(每个)至少出现一次的符号串数目。
解：令A、B、C分别为\(n\)位符号串中不出现a、b、c符号的集合。由于\(n\)位符号串中每一位都可取a、b、c、d四种符号中的一个，故不允许出现a的\(n\)位符号串的个数应是\(3^n\)，即\(|A|=|B|=|C|=3^n,|A \cap B|=|A \cap C|=|B \cap C|=2^n,|A \cap B \cap C|=1\)，a、b、c每位都至少出现一次表示为\(|\overline{A} \cap \overline{B} \cap \overline{C}|\)，
\[|\overline{A} \cap \overline{B} \cap \overline{C}| = 4^n-(|A|+|B|+|C|)+(|A \cap B|+|A \cap C|+|C \cap B|)-|A \cap B \cap C| = 4^n-3 \cdot 3^n+3 \cdot 2^n-1 \]3.4 容斥原理的应用
例题：对问题\(x_1+x_2+x_3=15,0\le x_1\le5,0\le x_2\le6,0\le x_3\le7\)，求整数解的数目。
解：如果没有\(0\le x_1\le5,0\le x_2\le6,0\le x_3\le7\)，记所求的整数解的集合为\(S\)，\(|S|=C_{3+15-1}^{15}=C_{17}^{2}=136\)。
分别设\(S\)中满足\(x_1 \ge 6\)的子集为\(A_1\)，满足\(x_2 \ge 7\)的子集为\(A_2\)，满足\(x_3 \ge 8\)的子集为\(A_3\)，问题转化为求\(|\overline{A_1} \cap \overline{A_2} \cap \overline{A_3}|\)。
对于\(A_1\)，相当于\(x_1+x_2+x_3=15-6\)，即\(x_1+x_2+x_3=9\)，求其非负整数解得\(|A_1|=C_{3+9-1}^{9}=55\)。
同理得\(|A_2|=C_{3+8-1}^{8}=45,|A_3|=C_{3+7-1}^{7}=36\)
\(|A_1 \cap A_2|=C_{3+(15-6-7)-1}^{15-6-7}=C_{4}^{2}=6\)
\(|A_1 \cap A_3|=C_{3+(15-6-8)-1}^{15-6-8}=C_{3}^{2}=3\)
\(|A_1 \cap A_2|=C_{3+(15-7-8)-1}^{15-7-8}=C_{2}^{2}=1\)
\(|A_1 \cap A_2 \cap A_3|=0\)
\(|\overline{A_1} \cap \overline{A_2} \cap \overline{A_3}|=139-(55+45+36)+(6+3+1)-0=10\)
例题：求从(0,0)点到(10,5)点得路径中不通过AB，CD，EF，GH的路径数，已知各点坐标为\(A(2,2),B(3,2),C(4,2),D(5,2),E(6,2),F(6,3),G(7,2),H(7,3)\)。
解：从（0，0）点到（10，5）点的所有路径数为\(C_{10+5}^{5}=3003\)（第一章的简单格路问题）
设\(A_1\)表示从（0，0）到（10，5）其中过AB的路径，
设\(A_2\)表示从（0，0）到（10，5）其中过CD的路径，
设\(A_3\)表示从（0，0）到（10，5）其中过EF的路径，
设\(A_4\)表示从（0，0）到（10，5）其中过GH的路径，
因此有
\[|A_1| =(\begin{array}{c} 4 \\ 2 \end{array}) (\begin{array}{c}(10-3)+(5-2) \\ 5-2 \end{array}) =(\begin{array}{l} 4 \\ 2\end{array}) (\begin{array}{l} 10 \\ 3 \end{array}) =6 \times 120 =720 \]同理
\[|A_2| =(\begin{array}{l} 6 \\ 2\end{array}) (\begin{array}{l} 8 \\ 3 \end{array}) =15 \times 56 =840 \]\[|A_3| =(\begin{array}{l} 8 \\ 2\end{array}) (\begin{array}{l} 6 \\ 2 \end{array}) =28 \times 15 =420 \]\[|A_4| =(\begin{array}{l} 9 \\ 2\end{array}) (\begin{array}{l} 5 \\ 2 \end{array}) =36 \times 10 =360 \]\[|A_1 \cap A_2| =(\begin{array}{l} 4 \\ 2\end{array}) (\begin{array}{l} 8 \\ 2 \end{array}) =6 \times 56 =336 \]\[|A_1 \cap A_3| =(\begin{array}{l} 4 \\ 2\end{array}) (\begin{array}{l} 6 \\ 2 \end{array}) =6 \times 15 =90 \]\[|A_1 \cap A_4| =(\begin{array}{l} 4 \\ 2\end{array}) (\begin{array}{l} 5 \\ 2 \end{array}) =6 \times 10 =60 \]\[|A_2 \cap A_3| =(\begin{array}{l} 6 \\ 2\end{array}) (\begin{array}{l} 6 \\ 2 \end{array}) =15 \times 15 =225 \]\[|A_2 \cap A_4| =(\begin{array}{l} 6 \\ 2\end{array}) (\begin{array}{l} 5 \\ 2 \end{array}) =15 \times 10 =150 \]\[|A_3 \cap A_4|=0 \]\[|A_1 \cap A_2 \cap A_3| =(\begin{array}{l} 4 \\ 2\end{array}) (\begin{array}{l} 6 \\ 2 \end{array}) =6 \times 15 =90 \]\[|A_1 \cap A_2 \cap A_4| =(\begin{array}{l} 4 \\ 2\end{array}) (\begin{array}{l} 5 \\ 2 \end{array}) =6 \times 10 =60 \]\[|A_2 \cap A_3 \cap A_4|=0 \]\[|A_1 \cap A_2 \cap A_3 \cap A_4|=0 \]所以
\[|\overline{A_1} \cap \overline{A_2} \cap \overline{A_3} \cap \overline{A_4}|=3003-(720+840+420+360)+(336+90+60+225+150)-(90+60)=3003-2340+861-150=1374 \]3.5 n对夫妻问题
例题：\(n\)对夫妻围圆桌而坐，每个男人都不和他的妻子相邻，有多少种方案？
解：\(n\)对夫妻有\(2n\)个人，\(2n\)个人围圆桌而坐的方案数为\((2n-1)!\)
设\(A_i\)表示第\(i\)对夫妻相邻而坐的集合，\(i=1,2,...,n\)，则问题转化为求
\[|A_1 \cap A_2 \cap \ldots \cap A_n| =N-\sum_{i=1}^n\left|A_i\right| +\sum_{i=1}^n \sum_{j>i}\left|A_i \cap A_j\right| -\ldots +(-1)^{n}\left|A_1 \cap A_2 \cap \ldots \cap A_n\right| \]\(|A_i|\)相当于讲第\(i\)对夫妻作为一个对象围圆桌，同一对夫妻之间可以换位，故
\[|A_i|=2Q_{2n-1}^{2n-1}=2(2n-2)! \]\[|A_i \cap A_j|=2^2Q_{2n-2}^{2n-2}=2^2(2n-3)! \]\[|A_i \cap A_j \cap A_k|=2^3Q_{2n-3}^{2n-3}=2^2(2n-4)! \]\[\cdots \cdots \]\[|A_1 \cap A_2 \cap \cdots A_n|=2^nQ_{2n-n}^{2n-n}=2^n(n-1)! \]故夫妻不相邻方案数为
\[M=(2n-1)! -2(\begin{array}{l} n \\ 1 \end{array})(2n-2)! +2^2(\begin{array}{l} n \\ 2 \end{array})(2n-3)! -\cdots +(-1)^n 2^n(\begin{array}{l} n \\ n \end{array})(n-1)! \\ =\sum_{h=0}^n(-1)^h 2^h\left(\begin{array}{l} n \\ h \end{array}\right)(2n-h-1)! \]例题：\(n\)对夫妻排成一列，每个男人都不和他的妻子相邻，有多少种可能的方案？
解：
\[M=(2n)! -2(\begin{array}{l} n \\ 1 \end{array})(2n-1)! +2^2(\begin{array}{l} n \\ 2 \end{array})(2n-2)! -\cdots +(-1)^n 2^n(\begin{array}{l} n \\ n \end{array})(n)! \\ =\sum_{h=0}^n(-1)^h 2^h\left(\begin{array}{l} n \\ h \end{array}\right)(2n-h)! \]3.6 错排问题
定义：一个排列其中所有的元素都不在原来的位置上，则称这个排列为错排，也叫重排。
证明：\(n\)个元素的错排为\(n!(1-\frac{1}{1!}+\frac{1}{2!}-\cdots \pm \frac{1}{n!})\)
设\(A_i\)为数\(i\)在第\(i\)位上的全体排列，\(i=1,2,..,n\)。因为数字\(i\)不能动，因而有：
\[|A_i|=(n-1)!,i=1,2,...,n \]\[|A_i \cap A_j|=(n-2)!,i,j=1,2,..,n,i\neq j \]\[\cdots \cdots \]每个元素都不在原来位置的排列数为
\[|\overline{A_1} \cap \overline{A_2} \cap \ldots \cap \overline{A_n}| =n! -C(n,1)(n-1)! +C(n, 2)(n-2)! -\cdots -\pm C(n,n)1! \\ =n!(1-\frac{1}{1!}+\frac{1}{2!}-\cdots \pm \frac{1}{n!}) \]例题：1，2，…，9的全排列中，求偶数都在原来的位置上，其余都不在原来位置上的错排数目。
解：实际上是1，3，5，7，9五个数的错排问题，总数为：
\[5!-C(5,1)4!+C(5,2)3!-C(5,3)2!+C(5,4)1!-C(5,5) =120(\frac{1}{2}-\frac{1}{6}+\frac{1}{24}-\frac{1}{120}) =44 \]3.7 棋盘多项式和有禁区的排列
对于\(X={1,2,...,n}\)的一个排列恰好对应了\(n\)个棋子在\(n \times n\)棋盘上的一种布棋方案。以棋盘的行表示\(X\)中的元素element，列表示排列中的位置position。如下图所示这种放棋方案就对应了排列2143。
如果在排列种限制元素\(i\)不能排列在第\(j\)个位置，则相应的布棋方案种的第\(i\)行第\(j\)列的方格不允许放棋子。把所有这些不许放棋的方格称为禁区。
对于\(\{1,2,3,4\}\)的一个排列\(P=e_1e_2e_3e_4\)，规定\(e_1\neq3，e_2\neq1,4，e_3 \neq2,4，e_4 \neq2\)。这样的排列对应于有禁区的布子。如下图有阴影的格子表示禁区。
棋盘多项式：设\(C\)为一棋盘，称\(\sum_{k=0}^{n} r_k(C)x^k\)为\(C\)的棋盘多项式，其中\(r_k(C)\)表示\(k\)个棋子布到棋盘\(C\)的方案数。规定\(r_0(C)=1\)。
性质：
- 设\(C_i\)是棋盘\(C\)的某一指定格子所在的行与列都去掉后所得的棋盘，\(C_e\)是仅去掉该格子后的棋盘，则\(r_k(C)=r_{k-1}(C_i)+r_k(C_e)\)。
- 如果\(C\)由互相分离的\(C_1\)和\(C_2\)组成，即\(C_1\)的任一格子所在的行和列中都没有\(C_2\)的格子，则有\(r_k(C)=\sum_{i=0}^{k}r_i(C_1)r_{k-i}(C_2)\)。
定理：设\(r_i\)为\(i\)个棋子布入禁区的方案数，\(i=1,2,3,...n\)。有禁区的布子方案数（即禁区内不布子的方案数）为，
\[r_0n!-r_1(n-1)!+r_2(n-2)!-\cdots+(-1)^n r_n = \sum_{k=0}^{n} (-1)^{k} r_{k}(n-k)! \]定理证明见棋盘多项式 - 维基百科，自由的百科全书 (wikipedia.org)
例题：如下所示，在\(4\times4\)的棋盘上，打叉的地方为禁区，求棋子无一落入禁区的排列数。
解：首先计算棋盘多项式，即\(r_0(C)+r_1(C)x+r_2(C)x^2+r_3(C)x^3+r_4(C)x^4\)，只需依次计算\(r_0,r_2,r_2,r_3,r_4\)即可。
由规定知\(r_0(C)=1\)，
\(r_1(C)\)即1个棋子布到棋盘\(C\)的方案数，棋盘\(C\)有6个禁区，这一个棋子可以布到这6个地方且不存在其他棋子与这一个棋子冲突，因此\(r_1(C)=6\)；
\(r_2(C)\)即2个棋子布到棋盘\(C\)的方案数，从6个禁区中找到两个不在同一行不在同一列的。有(1,3)和(2,1)，(1,3)和(2,4)，(1,3)和(3,2)，(1,3)和(3,4)，(1,3)和(4,2)，(2,1)和(3,2)，(2,1)和(3,4)，(2,1)和(4,2)，(2,4)和(3,2)，(2,4)和(4,2)，(3,4)和(4,2)，共11种。即\(r_2\)(C)=11；
\(r_3(C)\)即3个棋子布到棋盘\(C\)的方案数，得到\(r_3(C)=7\)；
\(r_4(C)\)即4个棋子布到棋盘\(C\)的方案数，四个棋子要求都不同行不同列，只有一种方案，即\(r_4(C)=1\)；
综上得棋盘多项式为\(1+6x+11x^2+7x^3+x^4\)，再结合定理得无一落入禁区得排列数为\(1\times4!-6\times(4-1)!+11\times(4-2)!-7\times(4-3)!+1\times(4-4)! = 24-36+22-7+1=4\)。
3.8 有限制的排列
-
有禁区排列是对元素排列位置的限制，计算的是绝对禁用位置；
-
有限制排列讲的是相对禁用位置，它限制的是对元素之间的相邻关系的限制 。也称为有限制条件（模式）的排列
-
这里谈的有限制排列与前面章节提到的“受限多重排列”不同。
3.9 鸽巢原理
鸽巢原理是组合数学中最简单也是最基本的原理，也叫抽屉原理。
-
若有n个鸽子巢，n+1个鸽子，则至少有一个巢内有至少有两个鸽子。
-
\(m\)只各自，\(n\)个鸽巢，至少有一个鸽巢里有不少于\(\lfloor\frac{m-1}{n}\rfloor+1\)只鸽子。
-
\(m_1,m_2,...,m_n\)都是正整数，并有\(m_1+m_2+\cdots+m_n-n+1\)个鸽子住进\(n\)个鸽巢，则至少对某个\(i\)有第\(i\)个巢中至少有\(m_i\)个鸽子，\(i=1,2,...,n\)。
-
设\(k\)和\(n\)都是任意正整数，若至少有\(kn+1\)只鸽子分配在\(n\)个鸽巢，则至少有一个鸽巢里有至少\(k+1\)只鸽子。
-
若取\(n(m-1)+1\)个球放进\(n\)个盒子，则至少有一个盒子有\(m\)个球。
-
若\(m_1,m_2,...,m_n\)是正整数，且\(\frac{m_1+m_2+...+m_n}{n} \gt {r-1}\)，则\(m_1,m_2,...,m_n\)中至少有一个数不小于\(r\)。