3 组合数学第三章排列组合.ppt

第三章 排列与组合 §3.1 加法原理与乘法原理 §3.1 加法原理与乘法原理 §3.2 集合元素的排列 * * 1.加法原理 A到B有三种交通方式： 空：m 种选择 陆：n 种选择 海：k 种选择 则共有 m+n+k 种走法 m n k A B 2、乘法原理 北京到广州有两段路程： 北京到武汉：m 种 武汉到广州：n 种 则共有 m*n 种走法 m n 北京 武汉 广州 例1 学习计划要求学生要选一门课程：数学课或生物课或计算机课。数学有5门供选择，生物有3门供选择，计算机有10门供选择。学生有多少种选择方式？ 答：5+3+10=18 学习计划要求学生从三类课程各选一门：数学课、生物课、计算机课。数学有5门供选择，生物有3门供选择，计算机有10门供选择。学生有多少种选择方式？ 答：5*3*10=150 例2 粉笔有3种不同长度，8种不同颜色，4种不同直径。共有多少种粉笔？ 答：3*8*4=96 电视节目要从5男6女、2男童和4女童中各选一人组成一个代表队。有多少种选择方式？ 答：5*6*2*4=240 例3 电视节目要从5男6女、2男童和4女童中选一人出线。有多少种选择方式？ 答：5+6+2+4=17 例4 解： 例4 解1： 冰箱里有6个桔子和9个苹果。要拿出一些水果装成果篮。要是篮子不空，共有多少种装法？ 桔子：0 – 6；苹果：0 - 9 包括空篮：7*10=70 篮子不空：70-1=69 解2： s1=没有桔子的装法：9 s2=至少有1个桔子的装法：6*10 由加法原理 S=s1+s2 篮子不空： 9+60=69 例5 解： 在1000和9999之间有多少个具有不同数字的奇数？ 1-9 0-9 0-9 奇数 选数顺序：个、千、百、十 n = 5*8*8*7=2240 例6 解： 用1、1、1、3、8可组成多少个不同的五位数？ 选数顺序：8、3、1 n = 5*4*1=20 选数顺序：8、1、3 n = 5*c(4,3)*1=20 选数顺序：1、8、3 n = c(5,3)*2*1=20 1.r-排列 集合S有n个不同元素，从中选出r个元素排成一队（考虑排队的顺序），称为一个r-排列。 所有r - 排列的个数记为P (n, r)。 定理3.2.1 证明： 乘法公式 推 论 P(n,0)=1, P(n,1)=n, P(n,n-1)=n! P(n,n)=n! 例1 用字母 a,b,c,d,e 组成4个字母的词，每个字母最多出现一次： 例2 P(5,4)=5*4*3*2=120 P(26,4)=26*25*24*23=26！/22！ P(5,5)=5*4*3*2*1=120 P(5,1)=5 15迷阵有多少种排列方法？ sss 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 P(16,16)=16！ 例3 用26个字母排列，是元音 a,e,i,o,u 组不相继出现，有多少种排法？ （1）排列所有辅音：P(21,21)=21！ （2）在辅音前后的22个空档中排元音: P(22,5)=22!/17! 总排法：n=21!*22!/17! 例4 用1,2,…,9可以组成多少个数码相异的7位数，5和6不以任何顺序相继出现？ (1)用1,2,…,9可以组成多少个数码相异的7位数? T=P(9,7)=9!/2!=181440 (2)其中5和6相连的数有多少? 除5,6以外的7个数，5个位置——P(7,5) 5,6捆绑后插入6个空档之一 —— 6 5,6进行全排列—— 2 S2=2*6*7!/2!=30240 (3) S=T-S1=181440-30240=151200 解1 例4 用1,2,…,9可以组成多少个数码相异的7位数，5和6不以任何顺序相继出现？ 分4种情况 用加法原理： S=5040+2*35280+75600=151200 解2 (1)5,6不出现： P(7,7)=7!=5040 (2)有5无6： 7*P(7,6)=7*7!=35280 (3)有6无5： 7*P(7,6)=7*7!=35280 (4)5,6不相连出现： 5首位,6不相连： 5*P(7,5)=5*