组合数学第三章[排列与组合].ppt

第三章 排列组合 §3.1 计数原理：加法法则与乘法法则 §3.2 排列与组合 §3.3 循环排列 §3.4 多重集的排列 §3.5 多重集的组合 §3.1 计数原理：加法法则与乘法法则 1. 加法法则 [描述1]设事件A有m种产生方式，事件B有n种产生方式，则事件A或B之一有m+n种产生方式。 [描述2]从两堆物体中选择一个物体，从第一堆中有p种选法，从第二堆中有q种选法，则共有p+q种选法。 [描述3：用集合论描述] 若 |A| = m , |B| = n , A?B = ? , 则 |A?B| = m + n 。 [描述4：一般性描述] 若集合S有一个划分{S1,S2,...,Sm}，则对S计数可转换为对Si的计数： |S|=|S1|+|S2|+...+|Sm| 这里，S应划分成“不太多的易于处理的部分”。 [例1] 某班选修企业管理的有 18 人，不选的有 10 人，则该班共有 18 + 10 = 28 人。 [例2] 北京每天直达上海的客车共有5次，客机有3次，则每天由北京直达上海的旅行方式有 5 + 3 = 8 种。 2. 乘法法则 [描述1]设事件A有m种产生式，事件B有n种产生方式，则事件A与B有 m · n种产生方式。 [描述2]如果一项任务有p个结果，而不论第一项任务的结果如何，第二项任务有q种结果，则这两项任务连续执行有p×q种结果。 [描述3：用集合论描述] 若 |A| = m , |B| = n , A?B = {(a,b) | a ?A,b ? B}, 则 |A ? B| = m · n 。 乘法法则可视为加法法则的推论。 [例3] 某种字符串由两个字符组成，第一个字符可选自{a，b，c，d，e}，第二个字符可选自{1，2，3}，则这种字符串共有5 ?3 = 15 个。 [例4] 从A到B有三条道路，从B到C有两条道路，则从A经B到C有3?2=6条道路供选择。 [例5] 某种样式的运动服的着色由底色和装饰条纹的颜色配成。底色可选红、蓝、橙、黄，条纹色可选黑、白，则共有4?2 = 8种着色方案。 注意：若此例改成底色和条纹都用红、蓝、橙、黄4种颜色的话，则方案数不是4 ? 4 = 16， 而只有 4 ? 3 = 12 种。 这说明，在乘法法则中要注意事件 A 和 事件 B 的相互独立性。 [例6] 两位数字可组成多少两位互异且非零（位）的二位数? [解1]对于二位数ab，a可从1~9中任选，b可从余下8个数中任选，故有9×8=72种。 [解2]二位数共90个，包括9个个位为0的，9个两位数字相同的，90-9-9个满足要求。 [例7] 在1000和9999之间有多少个具有不同数字位的奇数？ [解]个位在1,3,5,7,9中任选（5种），千位在1~9间除个位之外任选（8种），十位在0~9中除去个位和千位的数字中任选（8种），百位在剩下的7位中任选，故有5×8×8×7＝2240个。 [例8] 在0和10000之间有多少个整数恰好有一位数字是5？ [解1]令S1、S2、S3、S4分别表示1、2、3、4位整数集合。则 |S1|=1（即5） |S2|=9+8（5x和x5，不包括55和05） |S3|=8×9+8×9+9×9=225 (x5x) (xx5) (5xx) |S4|=8×9×9+8×9×9+8×9×9+9×9×9 =2763 [解2]通过在前面补0将所有数看作4位数（如0014），即S1~S4分别是5在第1~4位上的整数集合，则每个|Si|= 9×9×9 ，故|S|=4×729=2916。 [例9] 求小于10000的含1的正整数的个数。 [解1] 小于10000的不含1的正整数可看做4位数，但0000除外。故有 9×9×9×9-1=6560个。 于是，含1的整数有： 9999-6560=3439个。 [解2] 全部4位数有104个,而不含1的4位数有94个，故含1的4位数为：104 －94 = 3439个。 [例10 ] 求小于10000的含0的正整数的个数。 [解] 不含0的1位数有9个，2位数有92个，3位数有93个，4位数有94个 。故不含0小于10000的正整数有 9+92+93+94= 7380个 含0小于10000的正整数有 9999-7380=2619个 注意：不能完全照搬例9。 §3.2 排列与