10
§3.7 广义容斥原理应用举例
• 例 某校有１２个教师，已知教数学的有８位，教物理的 有６位，教化学的５位；数、理５位，数、化４位，理、 化３位；数理化３位。问教其他课的有几位？只教一门的 有几位？正好教两门的有几位？ • 解 令教数学的教师属于A1，教物理的属于A2，教化学 的属于A3。则P0＝12， • P1＝| A1 |+| A2|+| A3 |＝8+6+5＝19; • P2＝| A1∩A2|+ | A1∩A3|+| A2∩A3|＝12； • P3＝| A1∩A2∩A3|＝3； • 故 教其他课的老师数为： • Q0＝P0 －P1 +P2－P3＝２ • 恰好一门的教师数： • Q1＝P1－2P2 + 3P3＝4 • 恰好教两门的老师数为： • Q2＝P2－3P3＝3
§3.6 广义的容斥原理
M为修数学的学生集合；P 为修物理的学生集合；C 为 修化学的学生集合；
1)单修一门数学的学生有多少？
｜M∩P∩C｜ | M | (| M
P||M C |) | M P C | 108
2)只修一门课的学生有多少?
只修物理的学生有
|P M |C M C || P | (| M P || C | (| M P | | P C |) | M C | | P C |) | M
7
§3.6 广义的容斥原理
定理
k+i Qk = ∑ (－1)i( )Pk+i i i=0
n-k
证１分三种情况来讨论： 1）设某一元素恰有k种性质，则其对Pk的某一项的贡 献为１，而对Pk+1，Pk+2 , · · · ,Pn的贡献都是０。对右边 项贡献为1；左边项贡献为1。
P3 = | A1∩A2 ∩A3 |+ | A1∩A2 ∩A4 |+ | A1∩A3 ∩A4 |+ | A2∩A3 ∩A4 | Q3= | A1∩A2 ∩A3 ∩A4 |+ | A1∩A2 ∩A3 ∩A4 |+| A1∩A2 ∩A3 ∩A4 |+| A1∩A2 ∩A3 ∩A4 |
§3. 7 容斥原理应用举例
(10,5)
经过AB,CD的路径数为 |A1∩A2|=C(4,2)C(8,3); F H 经过AB,EF的路径数为 A B C D E G |A1∩A3|=C(4,2)C(6,2); 经过AB,HG的路径数为 |A1∩A4|=C(4,2)C(5,2); (0,0) 经过CD,EF的路径数为 经过AB,CD,EF的路径 |A2∩A3|=C(6,2)C(6,2); |A1∩A2 ∩A3 |=C(4,2)C(6,2); 经过CD,HG的路径数为 经过AB,CD,HG的路径 |A2∩A4|=C(6,2)C(5,2); |A1∩A2 ∩A4 |=C(4,2)C(5,2); 经过EF,HG的路径数为 |A2∩A3 ∩A4 |=0 |A3∩A4|=0; | A1∩A2 ∩A3 ∩A4 |=0
2）若某一元的性质少于k种，则其对Pk，Pk+1，· · · ，Pn 的贡献都是０。对右边项贡献为0；左边项贡献为0。
8
(
k j ki k j j (k j )! (k i )! j! (k j )! j! ( )( ) )( ) k! j! ( j i )!i! k i ki k ( j i )!(k i )! i! k! j!
§3.6 广义的容斥原理
定理 前例中只修一门课的学生为：
｜M∩P∩C｜+｜M∩P∩C｜+｜M∩P∩C｜ 2 i i+1
k+i Qk = ∑ (－1)i( )Pk+i i=0 i
n-k
= Q1= ∑ (－1) ( i ) Pi+1 i =0 = P1 － 2P2 + 3P3
在一般公式中，若令 P0 = N， Q0 = | A1∩A2∩···∩An |，即原来的容斥原理。 Q1 = P1 － 2P2 + 3P3 Q2 = P2 - 3P3
P|| P C|| M
P C | 66 P C | 81
P C | 255
5
只修化学的学生有
｜M∩P∩C｜+｜M∩P∩C｜+｜M∩P∩C｜
(| M | | P | | C |) 2(| M C |) 3 | M
§3.6 广义的容斥原理
设有与性质１, 2 , · · · , n相关的元素n个，Ai为满足第 i 种性质的所有元素的集合. 设｟(n,k)是［1,n］的所有k-子集的集合,定义Pk为至 少有k种性质的元素的元次,表示为 P0 = N，P1 = | A1 | + | A2 | + · · · + | An |， P2 = | A1∩A2 |+ | A1∩A3 |+ · · · + | An - 1∩An | Pk = ∑ | ∩Ai |
11
§3. 7 容斥原理应用举例
例 三论错排问题 错排问题对应的是n×n的棋盘的主对角线 上的格子是禁区的布子问题。
C=
· · · )n = ∑ ( k=0
n n n
R( C ) = ( 1 + x
n k ) x k
错排的方案数: n! +
∑(－1)k (
(n － k)! k=1 1 k = n!∑ ( － 1) － =P n k! k=0
解 可得如下的带禁区的棋盘其中有阴影的表示禁区．
A
Ⅰ
B
C
禁区的棋子多项式为： R( )
Ⅱ
=R( ) R( ) Ⅲ =(1+x)(1+3x+x2 ) =1+4x+4x2+ x 3 故方案数＝3!－4· 2!+4 · 1!－1 · 0!＝1
1)单修一门数学的学生有多少？ ｜M∩P∩C｜ 2)只修一门课的学生有多少? ｜M∩P∩C｜+｜M∩P∩C｜+｜M∩P∩C｜ 3) 只修两门课的学生有多少？ ｜M∩P∩C｜+｜M∩P∩C｜+｜M∩P∩C｜
I∈￠(n ,k) i ∈I
Qk为恰有k种性质的元素的个数。
Qk = ∑ | (∩ Ai)∩ ( ∩ Aj)|
i ∈I I∈￠(n ,k)
j ∈I
6
§3.6 广义的容斥原理
• 举例 n=4, k=3;
• P3 = | A1∩A2 ∩A3 |+ | A1∩A2 ∩A4 |+ | A1∩A3 ∩A4 |+ | A2∩A3 ∩A4 | • Q3= | A1∩A2 ∩A3 ∩A4 |+ | A1∩A2 ∩A3 ∩A4 |+| A1∩A2 ∩A3 ∩A4 |+| A1∩A2 ∩A3 ∩A4 |
S ( n,1) S ( n,2) S ( n, m ), n m S ( n,1) S ( n,2) S ( n, n), n m
S ( n, m ) C (n 1, n m ) C (n 1, m 1)
G( x) 1 (1 x )(1 x 2 ) (1 x m )
n k)
令rk = (
n ) k
§3. 7 容斥原理应用举例
例 有障碍的格路问题:
从(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)
F A B C D E G H
3) n对夫妻围圆桌而坐且夫妻不相邻的方案数 解: n对夫妻围圆桌而坐,没有约束的方案数为 |S| = (2n-1)! Ai表示第i对夫妻相邻而坐的集合 |Ai| = 2 (2n -2 )! 共C(n,1)个 |Ai ∩ Aj| = 22 (2n -3 )! 共C(n,2)个 ….. 故不相邻的方案数为 (2n-1)! – 2 C(n,1)(2n-2)! + 22 C(n,2)(2n-3)!- … n2n(n-1)! +(-1) n
§3. 7 容斥原理应用举例
m个有区别盒子,无空盒的方案数: N = | A1∩A2 …. ∩An |= mn – C(m,1)(m-1)n +C(m,2)(m-2)n ……+(-1)mC(m,m)(m-m)n
= ∑ (-1)kC(m,k)(m-k)n
k=0
m
而第二类Stirling数要求盒子无区别,则: m 1 S(n,m) = m! ∑ (-1)kC(m,k)(m-k)n k=0 推论: 因为S(m,m) = 1,
...
An N A1
n i 1 j i
A2
N Ai Ai - Ai
i=1 j>i k>j n n
Aj Ak ...
பைடு நூலகம்
Aj A2 ...
(1) A1
An
(5)
1
棋盘多项式和有限制排列
• 令rk(C)表示k个棋子布到棋盘C上的方案数。
定义 设C为一棋盘，称R(C)= ∑ rk(C) xk k=0 为C的棋盘多项式。 规定 r0(C)=1，包括C=Ф时。
§3.2 容斥原理
• 容斥原理指的就是（4）和（5）式。
A1
n i 1
A2
...
n
An Aj Ak ... An
Ai Ai
i 1 j i
+ Ai
i=1 j>i k>j
n
Aj ...
( 1) n 1 A1
A2
(4)
... An 1 An
A1
A2
n i 1
(10,5)
(0,0)
解:所有的路径数为C(15,5); 经过AB的路径数为|A1|=C(2+2,2)C(7+3,3); 经过CD的路径数为|A2|=C(4+2,2)C(5+3,3); 经过EF的路径数为|A3|=C(8,2)C(6,2); 经过GH的路径数为|A4|=C(9,2)C(5,2);