清华大学组合数学4

第三章容斥原理与鸽巢原理
§3.1 容斥原理引论
§3.1 容斥原理引论
§3.1 容斥原理引论
§3.2 容斥原理B
A
§3.2 容斥原理
§3.2 容斥原理
§3.2 容斥原理
§3.2 容斥原理
§3.2 容斥原理
§3.2 容斥原理
§3.2 容斥原理
§3.3 举例
§3.3 举例
§3.3 举例
§3.3 举例
120
4
A A A⎢⎥
==
I I，
§3.3 举例
§3.3 举例
例6。

求完全由n个布尔变量确定的布尔函数的个数。

§3.3 举例
例7。

欧拉函数Φ(n)是求小于n且与n互素的数的个数。

§3.3 举例
•例7续。

欧拉函数Φ(n)是求小于n且与n互素
§3.3 举例
A,B,C,D,E,F,G,H的全排列中只
§3.4 棋盘多项式和有限制排列
§3.4 棋盘多项式和有限制排列
§3.4 棋盘多项式和有限制排列
§3.4 棋盘多项式和有限制排列
n
§3.4 棋盘多项式和有限制排列
§3.4 棋盘多项式和有限制排列
§3.4 棋盘多项式和有限制排列
§3.4 棋盘多项式和有限制排列
§3.4 棋盘多项式和有限制排列
３．有禁区的排列
设对于排列P=P 1 P 2 P 3 P 4，规定P 1≠３，２≠１、４，P ３≠2、４，P 4≠2。

这样的排列对应于有禁区的布子。

如图中有影线的格子表示禁区。

定理设r i 为i 个棋子布入禁区的方案数，i =1,2,3,···,n 。

有禁区的布子方案数（即禁区内不布子的方案数）为n! －r 1(n －1)! ＋r 2(n －2)!－···＋(－1)n r n 设A i 为第i 个棋子布入禁区，其他棋子任意布的方案集，i =1 , 2 , 3, …,n 。

k 个棋子布入禁区，其他n -k 个棋子任意布的方案数为r k (n －k)！n! －r (n －1)! ＋r (n －2)!－···＋(－1)n r 根据容斥原理
∩A2∩···∩An ｜=
§3.5 棋盘多项式和有限制排列
例１，２，３，４四位工人，A，B，C，D 四项任务。

１不干B；２不干B、C;３不干C、；４不干D。

问有多少种可行方案？
A B C D 1
2
3
4
其中有影线的格子表示禁区。

方案数=4!－6(4－1)!+10(4－2)!－4(4－3)!
+0(4－4)!=4
R( )=1+6x+10x2+4x3
例三论错排问题
错排问题对应的是n ×n 的棋盘的主对角线上的格子是禁区的布子问题。

C = ···
n 错排的方案数: n! + ∑(－1)k ( ) (n －k)!= n!∑(－1)k －=P n k=1n n k!
1k R( C ) = ( 1 + x )n = ∑( ) x k 令r k = ( )n k=0k n k n
§3.6 广义的容斥原理
§3.6 广义的容斥原理
§3.6 广义的容斥原理
§3.6 广义的容斥原理
k+i
k+i n-k
§3.6 广义的容斥原理
k+i
n-k
§3.7 广义容斥原理应用举例•例某校有１２个教师，已知教数学的有８位，教物理的
§3.7 容斥原理应用举例
(10,5)。