组合数学_第3章_容斥原理与鸽巢原理

第3章 容斥原理与鸽巢原理

3.1 De Morgan定理

德摩根（De Morgan）定理：若$A$和$B$是集合$U$的子集，则

1. $\overline{A\cup B}=\overline{A}\cap \overline{B}$

2. $\overline{A\cap B}=\overline{A}\cup \overline{B}$

德摩根定理的推广：

1. $\overline{A_1\cup A_2\cup \cdots \cup A_n}=\overline{A_1}\cap \overline{A_2}\cap \cdots \cap \overline{A_n}$
2. $\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 \dots \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|-\dots +(-1{)}^{n-1}\left|A_1\cap A_2\cap \dots \cap A_n\right|$$

$$|\overline{A_1}\cap \overline{A_2}\cap \dots \cap \overline{A_n}|=N-|A_1\cup A_2\cup \dots \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\times 3}\rfloor =100,|A\cap C|=\lfloor \frac{600}{2\times 5}\rfloor =60,|B\cap C|=\lfloor \frac{600}{3\times 5}\rfloor =40$，

$|A\cap B\cap C|=\lfloor \frac{600}{2\times 3\times 5}\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\le 5,0\le x_2\le 6,0\le x_3\le 7$，求整数解的数目。

解：如果没有$0\le x_1\le 5,0\le x_2\le 6,0\le x_3\le 7$，记所求的整数解的集合为$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 \dots \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|-\dots +(-1{)}^n\left|A_1\cap A_2\cap \dots \cap A_n\right|$$
$|A_i|$相当于讲第$i$对夫妻作为一个对象围圆桌，同一对夫妻之间可以换位，故
$$|A_i|=2Q_{2n-1}^{2n-1}=2(2n-2)!$$

$$|A_i\cap A_j|=2^2{Q}_{2n-2}^{2n-2}=2^2(2n-3)!$$

$$|A_i\cap A_j\cap A_k|=2^3{Q}_{2n-3}^{2n-3}=2^2(2n-4)!$$

$$\cdots \cdots$$

$$|A_1\cap A_2\cap \cdots A_n|=2^n{Q}_{2n-n}^{2n-n}=2^n(n-1)!$$

故夫妻不相邻方案数为
$$\begin{gathered} 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)! \end{gathered}$$

---

例题：$n$对夫妻排成一列，每个男人都不和他的妻子相邻，有多少种可能的方案？

解：
$$\begin{gathered} 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)! \end{gathered}$$

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\ne j$$

$$\cdots \cdots$$

每个元素都不在原来位置的排列数为
$$\begin{gathered} |\overline{A_1}\cap \overline{A_2}\cap \dots \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!}) \end{gathered}$$

---

例题：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 } \{1,2,3,4\} {1,2,3,4}的一个排列$P=e_1{e}_2{e}_3{e}_4$，规定$e_1\ne 3，e_2\ne 1,4，e_3\ne 2,4，e_4\ne 2$。这样的排列对应于有禁区的布子。如下图有阴影的格子表示禁区。

---

棋盘多项式：设$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_{0}n!-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\times 4$的棋盘上，打叉的地方为禁区，求棋子无一落入禁区的排列数。

解：首先计算棋盘多项式，即$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$©=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\times 4!-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}>r-1$，则$m_1,m_2,...,m_n$中至少有一个数不小于$r$。

3.9.1 整除问题

例题：如果有$n+1$个正整数，而这些整数是小于或等于$2n$，是否一定会有一对数是互素的？为什么？

解：证明，如果从 { 1 , 2 , . . . , 2 n } \{1,2,...,2n\} {1,2,...,2n}中选择$n+1$个整数，那么存在两个整数，它们之间差为1。

设选择的$n+1$个整数为$a_1,a_2,...,a_{n+1},a_1<a_2<...<a_n$，令$b_1=a_1+1,b_2=a_2+1,...,b_n=a_n+1$,

则$1<b_1<b_2<...<b_n\le 2n$。

$a_1,a_2,...,a_{n+1},b_1,b_2,...,b_n$这$2n+1$个数，但范围只有$2n$，所以其中至少有一对相等，且$b_j=a_j+1$，$b_j=a_k$所有$a_k$和$a_j$只相差1。因此得证。

3.9.2 图形问题

例题：在边长为1的等边三角形内任意选择5个点，存在两个点，其间距最多为$\frac{1}{2}$。在边长为1的等边三角形内任意选择10个点，存在两个点，其间距最多为$\frac{1}{3}$.

解：

有4个小三角形，任选5个点，必有两个点在同一小三角形内。/有9个小三角形，任选10个点必有两个点在同一小三角形内。鸽巢原理。

3.9.3 连续累加问题

例题：设$a_1,a_2,...a_m$是正整数序列，则至少存在$k$和$l$，$1\le k<l\le m$，使得和$a_k+a_{k+1}+\cdots +a_l$是$m$的倍数。

证明：设$S_h={\sum }_{i=1}^h{a}_i$，$S_h\equiv r_{h}modm,0\le r_h\le m-1,h=1,2,...,m$。若存在$l$，$S_l\equiv 0modm$，则命题成立。否则，$1\le r_h\le m-1$，但$h=1,2,...,m$，由鸽巢原理知，存在$r_k=r_h$，即$S_k\equiv S_{h}modm$，不妨设$h>k$，则$S_h-S_k=a_{k+1}+a_{k+2}+\cdots +a_h\equiv 0modm$。

---

例题：一个孩子每天至少做一题，总共做7周，每周总共不超过11题。必存在连续若干天在次期间这个孩子恰好做了20题。

证明：设$a_1,a_2,...a_{49}$，$S_k=a_1+a_2+\cdots +a_k$，即证必定存在$0\le k<l\le 49，a_{k+1}+a_{k+2}+\cdots +a_l=20$，即$S_l-S_k=20$。

其中$1\le S_1,S_2,...S_{49}\le 77$，构造$b_1=S_1+20,...,b_{49}=S_{49}+20\le 97$。

$1\le S_1,S_2,...,S_{49},b_1,b_2,...b_{49}\le 97$，98个元素，但最高只能取到97，根据鸽巢原理其中必有两个元素相等。即存在$b_k=S_l$，而$b_k=S_k+20$，所以$S_k+20=S_l$，即$S_l-S_k=20$。

类似问题：生产产品、看电视、做运动…

---

例题：设$a_1,a_2,...a_{100}$是由1和2组成的序列，已知从其任一数开始的顺序10个数的和不超过16，即$a_i+a_{i+1}+\cdots +a_{i+9}\le 16,1\le i\le 91$，则至少存在$h$和$k$，$k>h$，使得$a_h+a_{h+1}+\cdots +a_k=39$。

证明：令$S_j={\sum }_{i=1}^j{a}_i,j=1,2,...,100$，显然$S_1<S_2<\cdots <S_{100}$，且$S_{100}\le 10\times 16=160$

做序列$S_1,S_2,...,S_{100},S_1+39,...S_{100}+39$共200项。其中最大项$S_{100}+39\le 160+39=199$。

由鸽巢原理，必有两项相等，而且必是前段中的某项与后段中的某项相等，设$S_k=S_h+39,k>h,S_k-S_h=39$，即$a_h+a_{h+1}+\cdots +a_k=39$