7.3 容斥原理与鸽巢原理

7.3 容斥原理与鸽巢原理

第七章 组合数学

全文均为手敲，如果发现有误，请于评论区交流讨论留言，作者会及时修改

7.3 容斥原理与鸽巢原理

1. 鸽巢原理

   将 n + 1 n+1 n+1个物体放入 n n n个盒子，则至少有一个盒子包含至少两个物体。

2. 鸽巢原理的加强形式

   将 q 1 + q 2 + ⋯ + q n − n + 1 q_1+q_2+cdots+q_n-n+1 q1​+q2​+⋯+qn​−n+1个物体放进 n n n个盒子里，则或者第 1 1 1个盒子至少含 q 1 q_1 q1​个物体，或者第 2 2 2个盒子至少含 q 2 q_2 q2​个物体， ⋯ cdots ⋯，或者第 n n n个盒子至少含 q n q_n qn​个物体。

3. 鸽巢原理的推广

   将 n ( r − 1 ) + 1 n(r-1)+1 n(r−1)+1个物体放入 n n n个盒子，则至少有一个盒子包含至少 r r r个物体。

4. 平均值原理

   若 n n n个非负整数的平均数大于 r − 1 r-1 r−1，则至少有一个非负整数大于等于 r r r。

5. R a m s e y Ramsey Ramsey问题

   对完全图 K r K_r Kr​进行红蓝二染色，对任何染色都存在红色 K m K_m Km​或蓝色 K N K_N KN​的最小图的阶 a m i n a_{min} amin​记作 r ( m , n ) r(m,n) r(m,n)，且满足以下性质

   ( 1 ) r ( m , n ) = r ( n , m ) ( 2 ) r ( m , 2 ) = m , r ( 3 , 3 ) = 6 , r ( 3 , 4 ) = 9 , r ( 3 , 3 , 3 ) = 17 ( 3 ) 对于 m , n ≥ 2 , 有 r ( m , n ) ≤ r ( m − 1 , n ) + r ( m , n − 1 ) begin{aligned} &(1)r(m,n)=r(n,m)\ &(2)r(m,2)=m,r(3,3)=6,r(3,4)=9,r(3,3,3)=17\ &(3)对于m,nge 2,有r(m,n)le r(m-1,n)+r(m,n-1) end{aligned} ​(1)r(m,n)=r(n,m)(2)r(m,2)=m,r(3,3)=6,r(3,4)=9,r(3,3,3)=17(3)对于m,n≥2,有r(m,n)≤r(m−1,n)+r(m,n−1)​

6. 容斥原理

   ∣ A ∪ B ∣ = ∣ A ∣ + ∣ B ∣ − ∣ A ∩ B ∣ |Acup B|=|A|+|B|-|Acap B| ∣A∪B∣=∣A∣+∣B∣−∣A∩B∣

   ∣ A ∪ B ∪ C ∣ = ∣ A ∣ + ∣ B ∣ + ∣ C ∣ − ∣ A ∩ B ∣ − ∣ A ∩ C ∣ − ∣ B ∩ C ∣ + ∣ A ∩ B ∩ C ∣ |Acup Bcup C|=|A|+|B|+|C|-|Acap B|-|Acap C|-|Bcap C|+|Acap Bcap C| ∣A∪B∪C∣=∣A∣+∣B∣+∣C∣−∣A∩B∣−∣A∩C∣−∣B∩C∣+∣A∩B∩C∣

   以上规律可以推广到 n n n个集合

   以及可以考虑德摩根律求解 ∣ A ∩ B ∩ C ∣ |Acap Bcap C| ∣A∩B∩C∣等

7. 错位排列

   D n = n ! ∑ k = 0 n ( − 1 ) k k ! D_n=n!sum_{k=0}^nfrac{(-1)^k}{k!} Dn​=n!k=0∑n​k!(−1)k​

   错位排列满足一定的递推关系

   { D n = ( n − 1 ) ( D n − 1 + D n − 2 ) ( n ≥ 3 ) D n = n D n − 1 + ( − 1 ) n D 1 = 0 , D 2 = 1 begin{cases} &D_n=(n-1)(D_{n-1}+D_{n-2})(nge 3)\ &D_n=nD_{n-1}+(-1)^n\ &D_1=0,D_2=1 end{cases} ⎩ ⎨ ⎧​​Dn​=(n−1)(Dn−1​+Dn−2​)(n≥3)Dn​=nDn−1​+(−1)nD1​=0,D2​=1​

8. 非攻击型车的禁区排列数

   记 r i r_i ri​为有 i i i个棋子布置到禁区的方案数，则放置 n n n个相同的非攻击性车到 n × n ntimes n n×n棋盘上的方案数为

   n ! − r 1 ( n − 1 ) ! + r 2 ( n − 2 ) ! − ⋯ + ( − 1 ) n r n n!-r_1(n-1)!+r_2(n-2)!-cdots+(-1)^nr_n n!−r1​(n−1)!+r2​(n−2)!−⋯+(−1)nrn​

   如果非攻击性车是可区分的，还应乘对应的排列数。

9. 容斥原理的一般公式

   设 p k p_k pk​为至少有 k k k种性质的元素个数， q k q_k qk​为恰有 k k k种性质的元素个数，则

   q k = p k − ( k + 1 1 ) p k + 1 + ( k + 2 2 ) p k + 2 + ⋯ + ( − 1 ) n − k ( n n − k ) p n q_k=p_k-begin{pmatrix}k+1\1end{pmatrix}p_{k+1}+begin{pmatrix}k+2\2end{pmatrix}p_{k+2}+cdots+(-1)^{n-k}begin{pmatrix}n\n-kend{pmatrix}p_n qk​=pk​−(k+11​)pk+1​+(k+22​)pk+2​+⋯+(−1)n−k(nn−k​)pn​

10. 记 Q n Q_n Qn​为 { 1 , ⋯ , n } {1,cdots,n} {1,⋯,n}中不出现 12 , 23 , ⋯ , ( n − 1 ) n 12,23,cdots,(n-1)n 12,23,⋯,(n−1)n这些模式的排列数，则

    Q n = n ! − ( n − 1 q ) ( n − 1 ) ! + ( n − 2 2 ) ( n − 2 ) ! + ⋯ + ( − 1 ) n − 1 ( n − 1 n − 1 ) 1 ! Q_n=n!-begin{pmatrix}n-1\qend{pmatrix}(n-1)!+begin{pmatrix}n-2\2end{pmatrix}(n-2)!+cdots+(-1)^{n-1}begin{pmatrix}n-1\n-1end{pmatrix}1! Qn​=n!−(n−1q​)(n−1)!+(n−22​)(n−2)!+⋯+(−1)n−1(n−1n−1​)1!

    且 Q n = D n + D n − 1 Q_n=D_n+D_{n-1} Qn​=Dn​+Dn−1​