卢开澄组合数学--组合数学第三章

卢开澄组合数学--

§3.1 容斥原理引论第三章 容斥原理和鸽巢原理 §1 容斥原理引论例 [1,20]中2或3的倍数的个数 [解] 2的倍数是：2,4,6,8,10, 12,14,16,18,20。 10个

卢开澄组合数学--

§3.2 容斥原理3的倍数是：3,6,9,12,15, 18。 6个 但答案不是10+6=16 个，因为6, 12,18在两类中重复计数，应减 去。故答案是：16-3=13

卢开澄组合数学--

§3.2 容斥原理容斥原理研究有限集合的交或并 的计数。 [DeMorgan定理] 论域U,补集 AA {x | x U 且x A} ,有

(a)

A B A B

(b) A B A B

卢开澄组合数学--

§3.2 容斥原理证：(a)的证明。 设 x A B ,则 x A B x A B 相当于 x A和 x B 同时成立，亦即x A B x A B

(1)

卢开澄组合数学--

§3.2 容斥原理反之，若 x A B,即x A和x B

故 x A和x B.亦即x A B x A B x A B

(2)

由(1)和(2)得x A B x A B

(b)的证明和(a)类似，从略.

卢开澄组合数学--

§3.2 容斥原理DeMogan定理的推广：设A1, A2 ,..., An是U的子集则 (a) 1 A2 ... An A1 A2 ... An A( b )A 1 A 2 ... A n A1 A 2 ... A n

证明：只证(a). N=2时定理已证。 设定理对n是正确的，即假定：

卢开澄组合数学--

§3.2 容斥原理A1 A2 ... An A A2 ... An 1则 A1 A2 ... An An 1 ( A1 ... An ) An 1 ( A1 A2 ... An An 1 A1 A2 ... An An 1

正确

即定理对n+1也是正确的。

卢开澄组合数学--

§3.2 容斥原理

§2定理：

容斥原理

最简单的计数问题是求有限集合A 和B的并的元素数目。显然有A B A B A B (1)

即具有性质A或B的元素的个数等于具

卢开澄组合数学--

§3.2 容斥原理有性质A和B的元素个数。 U AA B

B

卢开澄组合数学--

§3.2 容斥原理证 若A∩B=φ,则 | A∪B |= |A| + |B| | A |=| A ∩( B∪B) | =| (A∩B)∪(A∩B)| =| A∩B | + | A∩B | (1) 同理 | B | =| B∩A | + | B∩A | ( 2 ) | A∪B |=|(A∩( B∪B))∪(B∩(A∪A))| =|(A∩B)∪(A∩B)∪(B∩A)∪(B∩A)| =| A∩B| + |A∩B | + | B∩A| ( 3 )

卢开澄组合数学--

§3.2 容斥原理( 3 ) -( 1 ) -( 2 ) 得 | A∪B |-| A |-| B | =| A∩B| + |A∩B | + | B∩A| -( | A∩B | + | A∩B | ) -( | B∩A | + | B∩A | ) =- | A∩B | ∴| A∪B |=| A | + | B |-| A∩B |

卢开澄组合数学--

§3.2 容斥原理定理：A B C A B C A B - A C B C A B C

(2)

证明： A B C ( A B) C A B C ( A B) C

卢开澄组合数学--

§3.2 容斥原理根据 ( A B) C ( A C ) ( B C )

A B C A B C A B ( A C) (B C ) A B C A B - A C B C A B C

卢开澄组合数学--

§3.2 容斥原理AA B

B

A C

B C

A B C

C

卢开澄组合数学--

§3.2 容斥原理 例一个学校只有三门课程：数学、 物理、化学。已知修这三门课的学生 分别有170

、130、120人；同时修 数学、物理两门课的学生45人；同时 修数学、化学的20人；同时修物理化 学的22人。同时修三门的3人。问这学 校共有多少学生？

卢开澄组合数学--

§3.2 容斥原理令：M为修数学的学生集合； P 为修物理的学生集合； C 为修化学的学生集合；M 170, P 130, C 120, M P 45 M C 20, P C 22, M P C 3