第三章排列组合.ppt

组合数学课件 制作授课：王继顺 课程简介 目录（1） 目录（2） 第3章 排列与组合 §3.1 加法法则 §3.1 加法法则例1 §3.1 加法法则例2、3 §3.1 乘法法则 §3.1 乘法法则例4 §3.1 乘法法则例5 §3.1 乘法法则例6 引例 例1 （1）从{1,2,3,…,9}中选取数字构成四位数，如果要求每位数字都不相同，问有多少种选法？ （2）从中{1,2,3,…,9}选取数字构成四位数，问有多少种选法？ 例2 （1）从5种不同的球中每次选3个不同的球，问有多少种取法？ （2）从5种不同的球中（每种球的个数至少为3个）每次取出3个球，问有多少种取法？ §3.1 重集的概念 §3.2 线排列 §3.2 线排列推论1 §3.2 线排列推论2 §3.2 线排列例1 §3.2 线排列例2 §3.2 线排列例3 3.2.1 线排列 §3.2 圆排列 §3.2 圆排列例4 §3.2 圆排列例5 §3.3 无重组合 §3.3 无重组合推论1 §3.3 无重组合推论2 §3.3 无重组合推论3 §3.3 无重组合例1 §3.3 无重组合例2 §3.3 无重组合例3 §3.3 无重组合例4 §3.3 无重组合例5 §3.3 无重组合例6 §3.3 无重组合例6 §3.3 无重组合例6 §3.2 重排列 §3.2 重排列例6 证明 (组合数的计数方法) S的一个排列就是它的n个元素的一个全排列。因为S中有n1个a1 ，在排列时要占据n1个位置，这些位置的选法是C(n, n1 )种。接下去，我们在剩下的n- n1个位置中选择n2个放a2 ，选法是C(n-n1 ,n2) 。通过类似的分析可以得到，我么有C(n-n1-n2 , n3)种方法放a3 ,…,有C(n-n1-n2 -…-nk-1 , nk)种方法放ak 。根据乘法法则，S的排列数 §3.2 重排列计数 §3.2 重排列例8 §3.2 项链排列 §3.3 重复组合 §3.3 重复组合例7 §3.3 重复组合例10 第3章 小结 第3章 习题 结束 3.2.3 （无重）组合 例 题 例3*、某车站有1到6个入口处，每个入口处每次只能进一个人，问一小组9个人进站的方案数有多少？ 解I：按照从入口1到入口6的顺序可得到9个人一个排列，再把两个入口间设上一个标志，加上这5个标志相当于每一个排列有14个元素，其中5个标志没有区别，但其位置将区分各入口的进站人数，相当于14个元素集合的5?组合，故进站方案数为 9!×C(14,5)=726485760 解II：同上分析，问题转化为重集{1*p1,1*p2,…,1*p9,5*标志}的全排列（pi代表9个人，i=1,…,9），故进站方案数为 14!/5!=726485760 解III：考虑9个人选择方案，第1个人有6种选择，第2个人除了选择入口，还要考虑在第1个人的前面或后面，故有7种选择…同理，第9个人有14种选择，根据乘法法则，故进站方案数为 6×7×…×14=726485760 §3.2 集合的排列与组合 3.2.3 （无重）组合 例 题 例4*、求5位数中至少出现一个6，而被3整除的数的个数。 解：10进制数被3整除的充要条件是各位数的和能被3整除。据此可进行如下讨论： ①从左往右计，如最后一个6出现在个位，则十百千位各有10种选择，万位有3种可能，根据乘法法则，总个数为3×103 ； ②如最后一个6出现在十位，则个位有9种选择，百千位各有10种选择，万位有3种可能，根据乘法法则，总个数为3×102×9 ； ③如最后一个6出现在百位，则个十位各有9种选择，千位有10种选择，万位有3种可能，根据乘法法则，总个数为3×10×92； ④如最后一个6出现在千位，则个十百位各有9种选择，万位有3种可能，根据乘法法则，总个数为3×93； ⑤如最后一个6出现在万位，则个十百位各有9种选择，千位有3种可能，根据乘法法则，总个数为3×93 ； 根据加法法则，符合条件的整数个数为 3×103 + 3×102×9 + 3×10×92 + 3×93 + 3×93 =12504 §3.2 集合的排列与组合 3.2.3 （无重）组合 例 题 例5*、求1000!的末尾有几个零。 解：此问题在于求将1000!分解为素数的乘积时，2和5的幂是多少。末尾零的个数应该等于2和5的幂中较小的那个数。 1~1000中5的倍数的数共200个，其中有40个52的倍数，这40个数中有8个53的倍数，而这8个数中又有1个54的倍数，故1000!分解为素数的乘积时， 5的幂应该是 200+40+8+1=249 显然，2的幂必然大于249，因此1000!的末尾有249个零。 §3.2 集合的排列与组合 3.2.3 （无重