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

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 另外的禁排位置问题