Presentation is loading. Please wait.

Presentation is loading. Please wait.

1 第六章 容斥原理及应用 6.2 具有重复的组合 前面我们已经完成了对 n 个不同元素的集合的 r - 组合,其组合数为: 并且完成了 k 类元素都有无穷重复数的多重集合 的 r- 组合 P 43 ,其组合数为:

Similar presentations


Presentation on theme: "1 第六章 容斥原理及应用 6.2 具有重复的组合 前面我们已经完成了对 n 个不同元素的集合的 r - 组合,其组合数为: 并且完成了 k 类元素都有无穷重复数的多重集合 的 r- 组合 P 43 ,其组合数为:"— Presentation transcript:

1

2 1 第六章 容斥原理及应用 6.2 具有重复的组合 前面我们已经完成了对 n 个不同元素的集合的 r - 组合,其组合数为: 并且完成了 k 类元素都有无穷重复数的多重集合 的 r- 组合 P 43 ,其组合数为:

3 2 本节我们将证明与容斥原理相联系的公式, 并给出一种方法来求对于其重复数无任何限 制的多重集的 r- 组合数。 设 T 是一个多重集,并设 T 的某些种类型的元 素 x 具有大于 r 的重复数。此时,通过用 r 代替 x 的 重复数, T 的 r- 组合的个数等于从 T 得到多重集 的 r- 组合的个数,因为每个组合的元素最多是 r 。 如 :{3 · a,  · b, 6 · c,  · d }={3 · a, r · b, 6 · c, r · d }

4 3 因为每个 r- 组合中的元素最多能达到 r 个, 所以对无穷重复数的多重集,实际上只需要 有限重复数 r 就够了。可以总结为:无穷重复数的 多重集 {  · a 1,  · a 2, …..,  · a k } 总能化为有限重复 数的多重集 {n 1 · a 1, n 2 · a 2, ….., n k · a k }, 对于求 r- 组 合的个数,可以确定两个 “ 极端 ” 的情况: 1 ) n 1 = n 2 = …..=n k =1 , T 是一个普通集合。 2 ) n 1 = n 2 = …..=n k = r , T 是重复数足够的集合。

5 4 我们将用容斥原理来解释如何得到其他的解。 下面虽然只是一个例子,但能够很清楚地得 到解法,并且推广到一般情况下: 例 : 确定多重集 T = {3 · a, 4 · b, 5 · c} 的 10- 组合数。 解:在很久前我们遇到过类似的题,见书 P 43 ; 当 时我们用穷举法排出来满足条件的所有组合。 现在我们将容斥原理应用到多重集:

6 5 T * = {  · a,  · b,  · c } 的所有 10- 组合的集合 S 上 令 P 1 表示 T * 的 10- 组合具有多于 3 个 a 的性质; P 2 表示 T * 的 10- 组合具有多于 4 个 b 的性质; P 3 表示 T * 的 10- 组合具有多于 5 个 c 的性质; 此时题意要求的多重集 T 的 10- 组合的数就是 T * 中不具备性质 P 1 , P 2 , P 3 的 10- 组合的数。同样

7 6 令 A i 是由 T * 中满足性质 P i (i =1,2,3) 的那些 10- 组合构成。 的元素数量即 是我们需要的,由容斥原理:

8 7 其中集合 A 1 是由 a 多于 3 个的 T * 的所有 10- 组 合组成;即构成 A 1 中每个 10- 组合都至少有 4 个 a ,如果任意取 A 1 中的一个 10- 组合并且去掉 其中的 4 个 a ,剩下的就是 T * 的 6- 组合。 反之, 如果拿出 T * 的 6- 组合再加入 4 个 a 就得到 T * 的 10- 组合,而且其中至少有 4 个 a ,也就是说 T * 的 10- 组合个数等于 T * 的 6- 组合个数,或者说 A 1 中的 4 个元素已经确定,余下再作三类元素

9 8 选择 6 个的 6- 组合,故: 同理,集合 A 2 是由 b 多于 4 个的 T * 的所有 10- 组 合组成; A 2 中 T * 的 10- 组合个数等于 T * 的 5- 组 合个数。

10 9 集合 A 1 ∩A 2 是至少有 4 个 a 并且至少有 5 个 b 的 T * 的所有 10- 组合组成,实际上这十个元素已 经固定了九个,另外一个可以选择 a,b,c 中任意一 个,共有 3 种, 用前面同样的分析, A 1 ∩A 2 中的一个 10- 组合去掉 其中的 4 个 a 和 5 个 b ,剩下的就是 T * 的 1- 组合。 反之,如果拿出 T * 的 1- 组合再加入 4 个 a 和

11 10 A 1 ∩A 3 中的一个 10- 组合去掉 4 个 a 和 6 个 c 就得到 T * 的 10- 组合,而且其中仅仅有 4 个 a 和 6 个 c 这一 种可能,用多重集的 r- 组合数公式求法: 5 个 b 就得到 T * 的 10- 组合,而且其中至少有 4 个 a 和 5 个 b ,也就是说 T * 的 10- 组合个数等于 T * 的 1- 组合个数,用多重集的 r- 组合数公式求法:

12 11 A 2 ∩A 3 中至少要 5 个 b 和 6 个 c 共 11 个元素,没有 10- 组合,所以有:  A 2 ∩A 3  = 0 ;和  A 1 ∩A 2 ∩A 3  = 0; 那么

13 12 共只有六个 10- 组合,我们可以全部列出来: {3 · a, 4 · b, 3 · c } {3 · a, 3 · b, 4 · c } {3 · a, 2 · b, 5 · c } {2 · a, 4 · b, 4 · c } {2 · a, 3 · b, 5 · c } {1 · a, 4 · b, 5 · c } 由此例题我们也可以看出,当重复数之和 靠近 r- 组合的 r 时,我们可以穷举出所有的 r- 组 合,重复数之和与 r 远时,无法穷举,只能求出 计数。

14 13 我们曾经指出, r- 组合与方程的整数解之间 的关系:多重集 {n 1 · a 1, n 2 · a 2, ….., n k · a k } 的 r- 组合的个数等于方程: x 1 + x 2 + …..+x k = r 的 整数解的个数 (P 44 定理 3.5.1) 。这些解满足: 0 ≤x i ≤ n i (i=1,2,…..k) 这些解的个数可以用上面的方法来求得。

15 14 例:满足 1≤ x 1 ≤ 5, - 2≤ x 2 ≤ 4, 0≤ x 3 ≤ 5, 3≤ x 4 ≤ 9 的方程 x 1 + x 2 + x 3 + x 4 = 18 的整 数解的个数有多少? [ 分析 ] 这一问题与我们上述一般情况的差别在 于解所满足的条件不是 0 ≤x i ≤n i 的形式。因此, 需进行相应的变量变换:令 y 1 = x 1 - 1, y 2 = x 2 +2, y 3 =x 3, y 4 =x 4 - 3

16 15 使得原方程变为 y 1 + y 2 + y 3 + y 4 =16 而原条件变为 0≤y 1 ≤4, 0≤y 2 ≤6, 0≤y 3 ≤5, 0≤y 4 ≤6 对于方程 y 1 + y 2 + y 3 + y 4 =16 若其非负整数解集 是 S ,则以下的问题就是根据容斥原理的具体 计算了。 对于 y i 求整数解,再按下列情况讨论:

17 16 令 P 1 为性质 y 1 ≥5 , P 2 为性质 y 2 ≥7 , P 3 为性质 y 3 ≥6 , P 4 为性质 y 4 ≥7 。 令 A i 为满足性质 P i 的解的集合, 由题意是求集合: 的大小。其中集合 A 1 为 满足性质 y 1 ≥5 的解组成,再作一次变量代换: z 1 = y 1 – 5, z 2 = y 2, z 3 = y 3, z 4 = y 4 ; 求集合 A 1 的解的个数就与下列方程非负整数解 的个数相同, z 1 + z 2 + z 3 + z 4 = 11

18 17 因此: 用类似的方法可以求  A 2  、  A 3  和  A 4  ,他们 分别是下列方程的非负整数解的个数: α 1 + α 2 + α 3 + α 4 = 9 ; β 1 + β 2 + β 3 + β 4 = 10 γ 1 + γ 2 + γ 3 + γ 4 = 9

19 18 而集合 A 1 ∩A 2 是所有满足性质 y 1 ≥5 且 y 2 ≥7 的那些 解组成,再作变量代换 u 1 = y 1 - 5, u 2 = y 2 - 7, u 3 = y 3, u 4 = y 4 ; 那么 A 1 ∩A 2 的解的个数等于方程: u 1 + u 2 + u 3 + u 4 = 4 的非负整数解的个数。

20 19 故 同理得:

21 20 集合 A 1 ∩A 2 ∩A 3 肯定是空集,因为它要的性质 是三个解之和大于 远远超过方程右边的数, 所以 A i 三个以上的交集都为空。  A 1 ∩A 2 ∩A 3  =0………..; 应用容斥原理:

22 21 6.3 错位排列 集合的元素,对于某种特定的情况下有指定 的位置,我们现在可以讨论元素不再指定的位 置上的排列数问题。 例:在一个聚会上,有 10 位绅士要查看他们的 帽子,有多少中方式使得这些绅士中没有人能 够拿到他们来时所戴的帽子? 例:有多少种方法能够将字母 M,A,D,I,S,O,N 拼 写出,并且使得拼出的单词不同于 Madison?

23 22 以上都是错位排列问题,简称为错排; 由于元素性质与讨论不相干,设 n 个元素的集 合 x = {1, 2, 3, …, n} , n 个元素依次给以标号 1 , 2 , … , n 。在 n 个元素的全排列中,求每个元素 都不在自己原来位置上的排列数。 首先每一个错排都是原集合的一个全排列, 记为 i 1,i 2, …, i n 并且元素满足: i 1  1, i 2  2, …, i n  n

24 23 用 D n 表示 {1, 2, 3, …, n} 的错位排列的个数。上 述的绅士帽子和字母拼单词问题就成了求 D 10 和 D 7 的值。下面对部分数的集合求错排数; n = 1 时,没有错位排列, D 1 = 0 n = 2 时,唯一错位排列是: 21 , D 2 = 1 n = 3 时,有两个错位排列: 231 , 312 ; D 3 = 2 (n = 3 时的全排列共 6 个,分别是: 123, 132, 213, 231, 312, 321; 红色的是错排 )

25 24 n = 4 时,共有 24 个排列,其中错位排列有 9 个: 2143 , 3142 , 4123 2341 , 3412 , 4312 2413 , 3421 , 4321 D 4 = 9 定理 6.3.1 对于 n≥ 1 ,有:

26 25 证明:此定理是指 n 个元素都错位的排列数。 设 S 是集合 {1, 2, …, n} 的全部 n! 个排列的集 合中的第 j 个位置上恰好是 j ,那么,集合 A j = { x | x ∈ S ∧ P j (x) } j=1,2,…,n 便是 S 中所有满足性质 P j 排列的集合。 根据以上定义,显然有

27 26 由于 A j 中的每个排列均具有形式 i 1 i 2 … i j-1 j i j+1 … i n 其中, i 1 i 2 … i j-1 i j+1 … i n 是集合 {1,2,…,j-1,j+1,…n} 的一个 (n-1)- 排列。显然,这种排列有 (n-1)! 个。 故此 |A j |=(n-1)! j=1,2,..,n 又由于 A k ∩ A j 中的每个排列均具有形式 i 1 i 2 …i k-1 k i k+1 … i j-1 j i j+1 …i n

28 27 其中 i 1 i 2 …i k-1 i k+1 … i j-1 i j+1 …i n 是集合 {1,2,…,k-1,k+1,…j-1,j+1,…,n} 的一个 (n-2)- 排 列,显然,这种排列有 (n-2)! 个,故此 | A k ∩ A j | = (n-2)! 1 ≤ k<j ≤n 一般来说,对于 {1,2,…,n} 的任意 k- 组合 {i 1, i 2,…, i k }, 我们有:

29 28 另外,由于存在集合 {1, 2, …, n} 的 个 k- 组合 ; 应用容斥原理 P 107 (6-3) 式。

30 29 定理得证。 例: 10 位绅士帽子问题可以用公式计算: 5 字母拼单词问题:

31 30 例:数 1,2,…,9 的全排列中,求偶数在原来位置 上,其余都不在原来位置的错排数目。 解:实际上是 1 , 3 , 5 , 7 , 9 五个数的错排问题, 总数为: 如果只是要求部分元素错位排列,可以修改 为:令 A 1, A 2,…., A k 的表示集合 {1, 2, ……n} 中 部分元素 1, 2, …k ( k ≤ n ) 在原来位置的排列,

32 31 那么其他不变仅有部分元素 1, 2, …k 的错位排列 数是: 由于 k ≤ n ,公式只有 k+1 项,余下项的的 系数均为 0 。

33 32 例:在 8 个字母 A,B,C,D,E,F,G,H 的全排列中, 求 仅使 A,C,E,G 四个字母不在原来上的错排数目。 解: 8 个字母的全排列数是 8 !, n = 8, k = 4 令 A 1, A 2, A 3, A 4, 分别表 A,C,E,G 在原来位置上的排列, 则错排数为:

34 33 例 : 求 8 个字母 A,B,C,D,E,F,G,H 的全排列中只有 4 个不在原来位置的排列数。

35 34 解: 8 个字母中只有 4 个不在原来位置上,其余 4 个字母保持不动,相当于 4 个元素的错排, 但不属于前面奇、偶数例题问题,本题中哪 4 个字母错排?哪 4 个字母不动我们不清楚。首 先任意选取 4 个字母,其数目为 : 这 4 个元素的错排数目: D 4 = 9 故 8 个字母的全排列中有 4 个不在原来位置上的排 列数应为: 9 =630

36 35 我们在学习《高等数学》中 “ 无穷级数 ” 时知道, 利用麦克劳林级数将函数 e x 展开. 由于 e –1 是无穷级数,而 D n 是有限项级数,

37 36 e –1 的前 n 项可以用 D n 除以 n! 来表示

38 37 用无穷交错级数的性质断定: 计算表明, n≥7 时, 至少有三为 小数相同,就是说精确到千分位。这时我们就 认为

39 38 排列与全排列的比。那么随机选择一个排列, 它是错位排列的概率是 。 例:本节开始提出的帽子问题,如果随机将帽 子发给这些绅士,他们收到不是自己帽子的概 率为: D 10 / 10! ,近似于 e –1 。如果绅士的人 数达到 10000 人,他们收到不是自己帽子的概 率依然为: D 10 / 10! ,也近似于 e –1

40 39 错位排列数 D n 的性质 1) D n = (n-1)(D n-2 + D n-1 ) (n=3,4,……) 当 n=1, 2 时, D 1 = 0 , D 2 = 1 ; 这个公式将在第七章中给予证明。我们可以验证 D 3 = (3-1)(D 3-2 + D 3-1 ) = 2(D 1 + D 2 ) =2(0+1)=2 D 4 = (4-1)(D 4-2 + D 4-1 ) = 3(D 2 + D 3 ) =3(1+2)=9 D 5 = 4(2 + 9)=44; D 6 = 5(9 + 44)=265

41 40 2) D n = nD n-1 + (-1) n (n=3,4,……) 由性质 1) D n = (n-1)(D n-2 + D n-1 ) (n=3,4…) 将上式变形为: D n - nD n-1 = - D n +(n-1) D n-2 D n - nD n-1 = - [ D n-1 - (n-1) D n-2 ] 观察等式两边可以看出:左边是第 n 项与 n 倍后项的差,右边是第 n-1 项与 n-1 倍后项的差 的相反数,依次规律再右边应该是第 n-2 项与 n-2 倍后项的差的相反数再相反数,即 (-1) 2 …….

42 41 D n - nD n-1 = - [ D n-1 - (n-1) D n-2 ] = (-1) 2 [ D n-2 - (n-2) D n-3 ] = (-1) 3 [ D n-3 - (n-3) D n-4 ] =……………. = (-1) n-2 [ D 2 - 2 D 1 ] = (-1) n [ 1 - 2×0 ] = (-1) n 所以: D n = nD n-1 + (-1) n (n=3,4,……) 例如 D 7 = 7D 6 + (-1) 7 =7×265 - 1=1854

43 42 例:在一次舞会上有 n 位男生和 n 位女生,这 n 位 女生能够有多少种方法选择男生开始跳第一曲 舞?如果每个人必须换舞伴,那么女生第二曲舞 又有多少种选择方法? 解:第一曲时 n 位男生有 n! 种排列,就有 n! 选法, 第二曲时不能再选择前次的舞伴,因此,可能的 选择为第 n 个的错位排列数 D n 。 例:再假设在这次舞会上 n 位男生和 n 位女生都

44 43 戴有帽子,舞会结束时随机的返还他们 ( 她们 ) 的 帽子,如果每位男生和每位女生都分别得到一 顶男帽和女帽,但又不是他们 ( 她们 ) 自己的,那 么返还给他们 ( 她们 ) 的帽子方法有多少种? 解:如果不限制男生得到男帽女生得到女帽, 就有 (2n)! 种方法,如果有这个限制,就有 n!×n! 种方法。如果没有人得到他 ( 她 ) 自己的帽子,是 错位排列,共有 D n ×D n 种方法。

45 44 总 结 本次课我们介绍了有重复的组合和错排列 的问题,他们应用的前提是容斥原理。 有重复的组合问题重点在求线性方程的非 负整数解;错位排列重点在错位数公式。

46 45 本次授课到此结束 作业如下 : P 120 5, 7, 9 , 12 , 13 5. 确定多重集 S={  ·a, 4 ·b, 5 ·c 7 ·d} 的 10- 组合的 个数。 7. 确定非负整数 x 1 , x 2 , x 3 和 x 4 不超过 8 时方程 x 1 +x 2 +x 3 + x 4 =14 的整数解的个数。

47 46 9. 确定方程 x 1 + x 2 + x 3 + x 4 = 20 满足 1≤ x 1 ≤ 6, 0≤ x 2 ≤ 7, 4≤ x 3 ≤ 8, 2≤ x 4 ≤ 6 的整数解的个数? 12. 确定 {1 , 2 , 3 ,...8} 的恰好有四个整数在 它们的自然位置上的排列数。 13. 确定 {1 , 2 , 3 ,...9} 的至少有一个奇数在 它们的自然位置上的排列数。

48 47 下次上课内容: 6.4 带有禁止位置的排列 6.5 另外的禁排位置问题


Download ppt "1 第六章 容斥原理及应用 6.2 具有重复的组合 前面我们已经完成了对 n 个不同元素的集合的 r - 组合,其组合数为: 并且完成了 k 类元素都有无穷重复数的多重集合 的 r- 组合 P 43 ,其组合数为:"

Similar presentations


Ads by Google