《离散数学课第3章3》由会员分享，可在线阅读，更多相关《离散数学课第3章3（128页珍藏版）》请在金锄头文库上搜索。
1、1 离散数学DiscreteMathematics 第三章计数技术 学习内容 3 1TheBasicofCounting计数的基础3 2ThePigeonholePrinciple鸽巢原理3 3PermutationsandCombinations排列与组合3 4RecurrenceandDivide and Conquer递推与分治3 5GeneratingFunction生成函数3 6inclusion exclusion容斥原理应用 PermutationsandCombinations排列与组合GeneralizedPermutationsandCombinations一般性的排列和组
2、合GeneratingPermutationsandCombinations生成排列和组合 排列与组合PermutationsandCombinations Introduction Torecallpermutationsandcombinations回顾以前学过的关于排列与组合的知识Tounderstandpermutationsandcombinationsfromdifferentdegrees从不同的角度理解排列与组合Tosolvecountingproblemsusingthem使用排列与组合解决计数问题Toshowhowtheoremsareprovedbycombinatori
3、alarguments 排列与组合PermutationsandCombinations ForexampleInhowmanywayscanweselectthreestudentsfromagroupoffivestudentstostandinlineforapicture 从5个学生种选出3个学生站成一排照相 一共有多少种选择的方式 p 5 3 5 4 3 60Thisexampleillustrateshoworderedarrangementsofdistinctobjectscanbecounted Thisleadstosometerminology 这个例子显示了如何计数不同
4、目标的顺序安排问题 并引入一些术语 排列 Permutations Notation P n r 排列 Permutations Definition Apermutationofasetofdistinctobjectsisanorderedarrangementoftheseobjects Anorderedarrangementofrelementsofasetiscalledanr permutation 不同个体集合的一个排列是这些个体的一种有序安排 一个集合的r个元素的有序安排叫做r排列 Example1设S 1 2 3 3 1 2是S的一个排列 3 2是S的一个2排列 一个n元集
5、的r排列数积为P n r 我们可以使用乘积法则求出P n r Theorem1 Ifnisapositiveintegerandrisanintegerwith1 r n thentherearer permutationsofasetwithndistinctelements 具有n个不同元素的集合的r排列数是P n r n n 1 n 2 n r 1 从定理1得出P n r n n 1 n 2 n r 1 n n r 特别地有 P n n n 排列 Permutations Example2在进入竞赛的100个不同的人中有多少种方法选出一个一等奖得主 一个二等奖得主和一个三等奖得主 Sol
6、ution 不管哪个人得哪个奖 选取3个得奖人的方法是从100个元素的集合中有序选择3个元素的方法数 即100个元素的集合的3 排列数 因此 答案是P 100 3 100 99 98 970200 Example3假定有8个赛跑运动员 第一名得到一枚金牌 第二名得到一枚银牌 第三名得到一枚铜牌 如果比赛可能出现所有可能的结果 有多少种不同的颁奖方式 Solution 颁奖方式就是8元素的集合的3 排列数 因此存在P 8 3 8 7 6 336种可能的颁奖方式 Example4假定一个女推销员要访问8个不同的城市 她的访问必须从某个指定的城市开始 但对其他7个城市的访问可以按照任何次序进行 当访
7、问这些城市时 这个女推销员可以有多少种可能的次序 Solution 由于第一个城市是确定的 而其他7个城市可以使任意的顺序 故城市之间可能的路径数是7个元素的排列数 因此 这个女推销员有7 7 6 5 4 3 2 1 5040种方式选择她的旅行 比如说 如果这个女推销员想要在城市中找出具有最短距离的路径 并且她对每一条可能的路径计算总距离 那么她必须考虑5040条路径 Example5字母ABCDEFGH有多少种排列包含串ABC Solution 由于字母ABC必须成组出线 我们可以通过找6个对象 即组ABC和单个字母D E F G和H的排列数得到答案 由于这6个对象可以按任何次序出线 存在6
8、 6 5 4 3 2 1 720种ABCDEFGHZ字母的排列 其中ABC成组出现 Example 集合 a b c d e f g 有多少个排列 Solution 本题就是一个7元集合的全排列问题 因此 答案是p 7 7 7 6 5 4 3 2 1 5040 example a b c d e f g 有多少个排列以a结尾 Solution 符合题意的7元素排列中都是以字母a结尾 其他6个位置可以是任何次序的排列 故以a结尾的排列数有6 6 5 4 3 2 1 720个 Solution 7个子母中有A和E两个元音字母 所以符合要求的排列中 前两个字母只能从两个元音字母中选择可能的方法数是2
9、 对于后面五个辅音字母可能的排列数是5 所以完成符合题意的排列的所有可能的排列数为2 5 example 以A B C D E F G7个字母组成的排列中在多少个排列中是两个元音字母在五个辅音字母之前的 Example 一个组有n个男士和n个女士 如果把他们男女相间地排成一排 有多少种方式 Solution 我们假设这一排列可以有不同性别的排头 首先我们先考虑n个男士的排列 所有的排列数P n n n 同样的我们也可以得到n个女士的排列数也为n 现在将n个男士与n个女士相间的排列 我们可以采取先将女士排列好 然后往其中进行男士的排列 并存在男士作为排头或女士作为排头的两种情况 由乘积法则可以知
10、道总的排列方式数为 example 有多少种方式使得10个女士和6个男士站成一排并且没有两个男士彼此相邻 提示 先放女士 后考虑男士的位置 Solution 首先考虑女士的排列 一共有10个女士可能的排列数为P 10 10 然后由10个女生组成的排列形成了11个空隙 然后我们分别将6名男士安排站入11个空隙中 所有可能的方式数为P 11 6 因此完成整个任务的排列数为P 10 10 P 11 6 10 11 5 Solution a 将B单位3个人的某一排列作为一个元素 参加A单位进行排列 可得方案数为 7 1 8 且B单位的3人有3 种排列 由乘法原理 总排列方案数为8 3 example
11、A单位有7位代表 B单位有3位代表 排成一列合影 要求B单位3人排在一起 a 问有多少种不同的排列方案 b 若B单位的3人不能相邻 且A单位的2人排在两端 问有多少种不同的排列方案 b 先对A单位的7人进行排列 所有可能的排列数共有7 种 假设A1A2A3A4A5A6A7是A的一个排列 两端固定后 B单位3人中的第一人有6种选择A1 A2 A3 A4 A5 A6 A7即上面 的位置 第二位为了不与第一位相邻 故只有5种选择 第三位有4种选择 故排列总数为7 6 5 4 604800 组合 Combinations Definition Anr combinationofelementsofas
12、etisanunorderedselectionofrelementsfromtheset 集合元素的一个r组合是从这个集合无序选取的r个元素 Example6设S是集合 1 2 3 4 那么 1 3 4 是S的一个3组合 Note Anr combinationissimplyasubsetofasetwithrelements 一个r组合是这个集合的一个r个元素的子集 Notation符号 Example7因为 a b c d 的2 组合是 a b a c a d b c b d 和 c d 6个子集 我们有C 4 2 6 注意 我们可以用关于集合的r排列数的公式确定n元素的集合的r组合数
13、 为此只需注意到集合的r排列可以按下述方法得到 先构成集合的r组合 然后排列这些组合种的元素 下面的定理给出了C n r 的值 组合 Combinations Theorem2 Thenumberofr combinationofasetwithnelements wherenisapositiveintegerandrisanintegerwith0 r n equals设n是正整数 r是满足0 r n的整数 n元素的集合的r组合数等于C n r n r n r proof 可以如下得到这个集合的r排列 首先得到集合的C n r 个r 组合 然后以P n r 种方式排序每个r组合中的元素 这
14、可以用P r r 种方式来做 因此 P n r C n r P r r 这就推出 注意 该公式在n和r很大的时候 计算并不方便 且有可能产生的值不是一个整数 在实践中 可以从分子和分母中消去分母的大因式中所有的项 把分子中所有没有消去的项相乘 然后除以分母中较小的因式 下面给出一个关于集合r组合数的有用的恒等式 推论1 设n和r是满足r n的非负整数 那么C n r C n n r Proof 由定理2得到和因此 C n r C n n r Example8有多少种方式从10个选手的网球队中选择5个选手外出参加在另一个学校的比赛 Solution 答案由10元素集合的5 组合数给出 根据定理2
15、 这个组合数是 Example9一组30个人被培训作为宇航员去完成首次登陆火星的任务 有多少种方式选出6个人的小组来完成这个任务 假设所有的小组成员有同样的工作 Solution 因为不考虑这些人被选的次序 从30个人中选6个人的小组的方式数是30元素集合的6 组合数 根据定理2 这个组合数是 Example10有多少个长为n的二进制串恰好包含r个1 Solution 在长为n的二进制串中r个1的位置构成了集合 1 2 n 的r组合 因此有C n r 个长为n的二进制串恰好包含r个1 Example11为开发学校的离散数学课程要选出一个委员会 如果数学系有9个教师 计算机科学系有11个教师 而
16、这个委员会要由3个数学系的教师和4个计算机科学系的教师组成 那么有多少种选择方式 Solution 由乘积法则 答案是9元素集合的3组合数与11元素集合的4组合数之积 根据定理2 选择这个委员会的方式数是 example 一个10元素集合有多少个子集含有奇数个元素 Solution 10元素集合的含有奇数个元素的子集分别有 1元素子集 3元素子集 5元素子集 7元素子集 9元素子集所以我们可以得到10元素集合含有奇数元素的所有子集数即为C 10 1 C 10 3 C 10 5 C 10 7 C 10 7 512 example Asoccerclubhas8femaleand7malemembers Fortoday smatch howmanypossibleconfigurationsarethere 英式足球俱乐部有8名女性和7名男性 对于今天的比赛 有多少可能性的搭配 1 Thecoachwantstohave6femaleand5maleplayersonthegrass 俱乐部想要6名女性和5名男性参加比赛 2 Thecoachwantstohave11playerswit
