第4章组合.ppt

否则这 m 个和式被m 除后都有一个非零余数，即余数为 1,2,…,m-1 中的一个，由鸽笼原理，必有两个和式除以 m 的余数相同。设这两个和 式分别为 a1+ a2+…+ ak 和 a1+ a2+…+ al，kl 其相同的余数为r，即 a1+ a2+…+ ak = am+r, a1+ a2+…+ al = bm+r 其中a,b均为整数。相减得 ： ak+1+ak+2+…+al = (b- a)m 即 ak+1+ ak+2+…+ al 能被 m 整除。 2 容斥原理 定义　所谓容斥，是指我们计算某类物的数目时，要排斥那些不应包含在这个计数中的数目，但同时要包容那些被错误地排斥了的数目，以此补偿，这种原理称为容斥原理，又称为包含排斥原理。 DeMorgan定理 二、 容斥原理 设 S 为全集，集合A 的补集记为 ，易知集合有 下列性质： A （1） （2.5） （2） (2.7) 推广 (2.7）式，即可得到定理6（容斥原理）。 最简单的计数问题是求有限集合A和B的并的元素数目。 A B 定理1 设A1 , A2 , …, Am均为有限集，m≥2，则 （2.8） 证明* 对m 用归纳法。 m =2 即为(2.7)式。 于是 (2.10) 设 （2.9） （2.11） 代（2.9）和 (2.11) 入（2.10）, 得 而 推论 设全集 S 为有限集，对集合 A1 , …, Am 有 证明 （2.12） 再将 (2.8) 式代入上式便得(2.12) 式。 例 5 求1到1000的整数中，不能被5，6和8任一个整除的整数个数。 解 取全集S = {1,2,…,1000}，令 A1 = { i︱ 且5 整除 i }，A2 = { i︱ 且6 整除 i } A3 = { i︱ 且8 整除 i } 于是有 ， ， ， 于是 其中符号 lcm{6，8} 表示 6 和 8 的最小公倍数。 表示非负实数 x 的整数部分。又 = 1000-(200+166+125)+(33+25+41)-8 = 600 即 1 到 1000 的整数中，不能被5，6 和 8 任一个整除的整数有600个。 例 6 设有2个红球, 3个白球, 4个蓝球和5个黑球, 同色球均相同, 求从这些球中取出10个球的组合数。 解 令 S 为从给定的四类球（假定都有足够多的数量） 中取出10个球的组合所构成的集合，则 = C (13, 10) = C (13, 3) = 286 再令 A = {x︱ x ?S , x中至少含有3个红球} B = {x︱ x ?S , x中至少含有4个白球} C = {x︱ x ?S , x中至少含有5个蓝球} D = {x︱ x ?S , x中至少含有6个黑球} 有 |A| = F(4, 7) = C (4+7-1, 7) = C (10, 7) = 120 |B| = F(4, 6) = C (4+6-1, 6) = C (9, 6) = 84 |C| = F(4, 5) = C (4+5-1, 5) = C (8, 5) = 56 |D| = F(4, 4) = C (4+4-1, 4) = C (7, 4) = 35 |A∩B| = F(4, 3) )= C(6, 3) = 20 |A∩C| = F(4, 2) = C(5, 2) = 10 |A∩D| = |B∩C| = F(4, 1) = C(4, 1) = 4 由容斥原理, 所求数为 = 286 - (120+84+56+35) + (20+10+4+4+1) = 286-295+39 = 30 例 8. 某软件公司的程序员都熟悉C++或VB，其中熟悉C++的共47人，熟悉VB的共35人，C++和VB都熟悉的共23人，问该公司共有多少程序员？ 解：设A, B分别表示熟悉C++和VB的程序员集合，则该