组合数学排列组合课件.pptx

《组合数学排列组合课件.pptx》由会员分享，可在线阅读，更多相关《组合数学排列组合课件.pptx（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 第三章第三章 排列与组合排列与组合3.1 .1 加法原理与乘法原理加法原理与乘法原理 1.1.加法原理加法原理nnSSS,S,SS 11,则则剖剖分分成成设设集集合合 A A到到B B有三种交通方式：有三种交通方式： 空：空：m m 种选择种选择 陆：陆：n n 种选择种选择 海：海：k k 种选择种选择 则共有则共有 m+n+k m+n+k 种走法种走法mnkAB3.1 .1 加法原理与乘法原理加法原理与乘法原理 2 2、乘法原理、乘法原理BASBbAabaS 则则设设集集合合,),( 北京到广州有两段路程：北京到广州有两段路程： 北京到武汉：北京到武汉：m m 种种 武汉到广州：武汉到广

2、州：n n 种种 则共有则共有 m m* *n n 种走法种走法mn北京北京武汉武汉广州广州例例1 1 学习计划要求学生要选一门课程：数学课学习计划要求学生要选一门课程：数学课或或生生物课物课或或计算机课。数学有计算机课。数学有5 5门供选择，生物有门供选择，生物有3 3门门供选择，计算机有供选择，计算机有1010门供选择。学生有多少种选门供选择。学生有多少种选择方式？择方式？ 答：答：5+3+10=18 5+3+10=18 学习计划要求学生从三类课程各选一门：数学学习计划要求学生从三类课程各选一门：数学课、生物课、计算机课。数学有课、生物课、计算机课。数学有5 5门供选择，生门供选择，生物有

3、物有3 3门供选择，计算机有门供选择，计算机有1010门供选择。学生有门供选择。学生有多少种选择方式？多少种选择方式？ 答：答：5 5* *3 3* *10=150 10=150 例例2 2 粉笔有粉笔有3 3种不同长度，种不同长度，8 8种不同颜色，种不同颜色，4 4种不同直种不同直径。共有多少种粉笔？径。共有多少种粉笔？ 答：答：3 3* *8 8* *4=96 4=96 电视节目要从电视节目要从5 5男男6 6女、女、2 2男童和男童和4 4女童中各选一女童中各选一人组成一个代表队。有多少种选择方式？人组成一个代表队。有多少种选择方式？ 答：答：5 5* *6 6* *2 2* *4=2

4、40 4=240 例例3 3 电视节目要从电视节目要从5 5男男6 6女、女、2 2男童和男童和4 4女童中选一人女童中选一人出线。有多少种选择方式？出线。有多少种选择方式？ 答：答：5+6+2+4=17 5+6+2+4=17 例例4 4有有多多少少个个正正因因子子？问问设设mm8724131153 解：解：knml131153: 每每个个因因子子都都形形如如80702040 knml10809835 例例4 4解解1 1： 冰箱里有冰箱里有6 6个桔子和个桔子和9 9个苹果。要拿出一些水果个苹果。要拿出一些水果装成果篮。要是篮子不空，共有多少种装法？装成果篮。要是篮子不空，共有多少种装法？

5、桔子：桔子：0 0 6 6；苹果：；苹果：0 - 9 0 - 9 包括空篮：包括空篮：7 7* *10=7010=70 篮子不空：篮子不空：70-1=69 70-1=69 解解2 2： s1= s1=没有桔子的装法：没有桔子的装法：9 9 s2= s2=至少有至少有1 1个桔子的装法：个桔子的装法：6 6* *10 10 由加法原理由加法原理 S=s1+s2S=s1+s2 篮子不空：篮子不空： 9+60=69 9+60=69 例例5 5解：解： 在在10001000和和99999999之间有多少个具有不同数字之间有多少个具有不同数字的奇数？的奇数？ 1-91-9 0 0-9-9 0 0-9-9

6、 奇数 选数顺序：个、千、百、十选数顺序：个、千、百、十 n = 5n = 5* *8 8* *8 8* *7=22407=2240 例例6 6解：解： 用用1 1、1 1、1 1、3 3、8 8可组成多少个可组成多少个不同的五位数？不同的五位数？ 选数顺序：选数顺序：8 8、3 3、1 1 n = 5n = 5* *4 4* *1=201=20 选数顺序：选数顺序：8 8、1 1、3 3 n = 5n = 5* *c(4,3)c(4,3)* *1=201=20 选数顺序：选数顺序：1 1、8 8、3 3 n = c(5,3)n = c(5,3)* *2 2* *1=201=20 3.23.2

7、 集合元素的排列集合元素的排列 1.r-1.r-排列排列 集合集合S S有有n n个不同元素，从中选出个不同元素，从中选出r r个元素排成个元素排成一队（考虑排队的顺序），称为一个一队（考虑排队的顺序），称为一个r-r-排列。排列。 所有所有r - - 排列的个数记为排列的个数记为P (n, r)。cbacabbcabacacbabccbcabcbaacabcbacbaS,:-3,:-2,:-1,排列排列排列排列排列排列的选排列有的选排列有集合集合 定理定理3.2.13.2.1)1()1()!(!),( rnnnrnnrnP证明：证明：乘法公式乘法公式推推 论论!),(nnnP 全全排排列列P

8、(n,0)=1, P(n,1)=n,P(n,0)=1, P(n,1)=n,P(n,n-1)=n! P(n,n)=n!P(n,n-1)=n! P(n,n)=n!例例1 1 用字母用字母 a,b,c,d,e 组成组成4 4个字母的词，每个字个字母的词，每个字母最多出现一次：母最多出现一次：例例2 2P(5,4)=5P(5,4)=5* *4 4* *3 3* *2=1202=120P(26,4)=26P(26,4)=26* *2525* *2424* *23=2623=26！/22/22！ P(5,5)=5P(5,5)=5* *4 4* *3 3* *2 2* *1=1201=120P(5,1)=5

9、P(5,1)=51515迷阵有多少种排列方法？迷阵有多少种排列方法？123456789101112131415sssP(16,16)=16P(16,16)=16！ 例例3 3 用用2626个字母排列，是元音个字母排列，是元音 a,e,i,o,u 组不相继组不相继出现，有多少种排法？出现，有多少种排法？（1 1）排列所有辅音：）排列所有辅音：P(21,21)=21P(21,21)=21！（2 2）在辅音前后的）在辅音前后的2222个空档中排元音个空档中排元音: : P(22,5)=22!/17! P(22,5)=22!/17!总排法：总排法：n=21!n=21!* *22!/17!22!/17!

10、例例4 4 用用1,2,1,2,9,9可以组成多少个数码相异的可以组成多少个数码相异的7 7位数，位数，5 5和和6 6不以任何顺序相继出现？不以任何顺序相继出现？ (1) (1)用用1,2,1,2,9,9可以组成多少个数码相异可以组成多少个数码相异的的7 7位数位数? ? T=P(9,7)=9!/2!=181440 T=P(9,7)=9!/2!=181440 (2) (2)其中其中5 5和和6 6相连的数有多少相连的数有多少? ? 除除5,65,6以外的以外的7 7个数，个数，5 5个位置个位置P(7,5)P(7,5) 5,6 5,6捆绑后插入捆绑后插入6 6个空档之一个空档之一 6 6 5

11、,6 5,6进行全排列进行全排列 2 2 S2=2 S2=2* *6 6* *7!/2!=302407!/2!=30240 (3) S=T-S1=181440-30240=151200 (3) S=T-S1=181440-30240=151200解解1 1例例4 4 用用1,2,1,2,9,9可以组成多少个数码相异的可以组成多少个数码相异的7 7位数，位数，5 5和和6 6不以任何顺序相继出现？不以任何顺序相继出现？ 分分4 4种情况种情况 用加法原理：用加法原理： S=5040+2S=5040+2* *35280+75600=15120035280+75600=151200解解2 2 (1)

12、5,6 (1)5,6不出现：不出现： P(7,7)=7!=5040P(7,7)=7!=5040 (2) (2)有有5 5无无6 6： 7 7* *P(7,6)=7P(7,6)=7* *7!=352807!=35280 (3) (3)有有6 6无无5 5： 7 7* *P(7,6)=7P(7,6)=7* *7!=352807!=35280 (4)5,6 (4)5,6不相连出现：不相连出现：5 5首位首位,6,6不相连：不相连： 5 5* *P(7,5)=5P(7,5)=5* *7!/2!=126007!/2!=126005 5末位末位,6,6不相连：不相连： 5 5* *P(7,5)=5P(7,

13、5)=5* *7!/2!=126007!/2!=126005 5在其它位置：在其它位置： 5 5* *4 4* *P(7,5)=50400P(7,5)=50400 共共 2 2* *12600+50400=7560012600+50400=75600)!(!),(rnrnrrnPr 排列数排列数循环循环2.2.循环循环r-r-排列排列 从集合从集合S S的的n n个元素中选出个元素中选出r r个个, ,把它们排成把它们排成1 1个个圆圈（考虑顺序），称为一个循环圆圈（考虑顺序），称为一个循环r-r-排列。排列。)!1(),( nnnnPn排排列列数数循循环环定理定理3.2.23.2.2证明：证

14、明： r r个个r-r-线性排列对应线性排列对应1 1个个r-r-循环排列循环排列. .例例5 5 将将1212种记号标在旋转的圆鼓上，有多少种种记号标在旋转的圆鼓上，有多少种标法？标法？ n=P(12,12)/12=11! n=P(12,12)/12=11!解解1 1 (1) (1)任意坐：任意坐： n=9!n=9! (2) (2)不相邻：不相邻：A A先就坐，先就坐，B B不相邻：不相邻：7 7 其余其余8 8人排序：人排序：8 8！ m=7m=7* *8 8！ (3) P=m/n=7(3) P=m/n=7* *8!/9!=7/98!/9!=7/9例例6 6 10 10个人为圆桌任意就坐，

15、求指定的两个人个人为圆桌任意就坐，求指定的两个人A A与与B B不相邻的概率。不相邻的概率。解解2 2 (1) (1)任意坐：任意坐： n=9!n=9! (2)A,B (2)A,B相邻：相邻：A A先就坐，先就坐，B B左右相邻：左右相邻：2 2 其余其余8 8人排序：人排序：8 8！ k=2k=2* *8 8！ (3)(3)不相邻：不相邻：m=9!-2m=9!-2* *8!8! (4) (4) 两人不相邻的概率两人不相邻的概率 P=m/n=P=m/n=（9!-29!-2* *8!)/9!=1-2/9=7/98!)/9!=1-2/9=7/9例例6 6 10 10个人为圆桌任意就坐，求指定的两个

16、人个人为圆桌任意就坐，求指定的两个人A A与与B B不相邻的概率。不相邻的概率。3.3 集合元素的组合集合元素的组合 集合集合S S有有n n个不同元素，从中选出个不同元素，从中选出r r个元素组成一个元素组成一组（不考虑排列顺序），称为组（不考虑排列顺序），称为S S的一个的一个r-r-组合。组合。 n n个元素的所有个元素的所有r 组合的个数记为组合的个数记为,3,dcbdcadbacbadcbaS组合有组合有的的集合集合 rnCrn或或)!( !),(rnrnrrnPrn 定理定理3.3.13.3.1特别：特别：rnnrnCC 2)1(, nnCnCCnnn2101,nnnnnCCC21

17、0 定理定理3.3.23.3.2解解 (1) (1)每每2 2个点唯一确定一条直线个点唯一确定一条直线 例例1 1 平面上有平面上有2525个点，没有个点，没有3 3点共线。这些点能点共线。这些点能够确定多少条直线？确定多少个三角形？够确定多少条直线？确定多少个三角形？ (2) (2)每每3 3个点唯一确定一个三角形个点唯一确定一个三角形 30022425!23!2!25225 Cn32232425!22!3!25325 Cn解解 (1) (1)选择选择1212个人来上课：个人来上课： 例例2 2 15 15选修数学课，其中选修数学课，其中1212人来上课，他们随人来上课，他们随便坐在教室的便

18、坐在教室的2525个座位上。个座位上。 共有多少中不同坐法？共有多少中不同坐法？ (2)25 (2)25个座位中选择个座位中选择1212个给他们坐：个给他们坐：! 3 ! 21! 511251 C!13!12!251225 C (3)12 (3)12人的选择座位（排列）：人的选择座位（排列）：!12)12,12( P 由乘法原理：由乘法原理：!13!3!12!25!15 n证明证明 (1) (1) 从从 1,2, 1,2,n ,n 中选出中选出2-2-组合有组合有 例例4 4 利用计数的方法证明：利用计数的方法证明：2nC2)1()1(210 nnn (2) (2) 另一种选法：另一种选法：

19、最大数为最大数为k k的的2-2-组合共有组合共有k-1k-1个，个，k=1,2,k=1,2,n ,n 有加法原理，共有有加法原理，共有 0+1+2+0+1+2+(n-1) +(n-1) 个个2-2-组合组合 所以所以2)1()1(2102 nnCnn3.4 多重集的排列多重集的排列 篮子里有篮子里有2 2个苹果，个苹果，1 1个桔子，个桔子，3 3个香蕉，篮子里个香蕉，篮子里的水果构成的水果构成“多重集多重集”。 acbc acbc，cbcc,abaccbcc,abac都是都是S S个元素个元素4 4 排列。排列。3 ,1 ,2,cbacccbaaS 多重集多重集S S中选出中选出r r个元

20、素进行有序排放，构成一个元素进行有序排放，构成一个多重集的个多重集的r-r-排列。排列。 其中其中2,1,32,1,3是元素的重复数。当元素可以无限多次是元素的重复数。当元素可以无限多次使用时，重复数为无穷。使用时，重复数为无穷。排排列列的的个个数数为为的的则则无无穷穷重重复复数数有有个个不不同同元元素素，每每个个元元素素有有设设多多重重集集rkrSk ,S定理定理3.4.13.4.1例例1 1 最多最多5 5位数的位数的8 8进制数有多少个？进制数有多少个？解解58,7,2, 1,0S n所所以以。的排列数为的排列数为则则分别为分别为复数复数个不同元素，元素的重个不同元素，元素的重有有设多重

21、集设多重集!,S2121kknnnnSnnnk定理定理3.4.23.4.2证明证明例例2 2 单词单词MISSISSIPPIMISSISSIPPI中字母的排列数是多少？中字母的排列数是多少？所所以以,P2,S4 , I4 ,M1S 解解!2!4!4!1!11 n例例3 3排排列列的的个个数数。的的求求设设 8,4 ,2,3SScba解解 S S有有9 9个元素，组成个元素，组成8-8-排列，需去除排列，需去除1 1个个420!4!2!2!8: ana去去除除280!4!1 !3!8: bnb去去除除560!3!2!3!8: cnc去去除除1260560280420 例例4 4 8 8* *8

22、8棋盘上，非攻击车的放法。棋盘上，非攻击车的放法。！个个颜颜色色相相同同的的车车8:8 n!888！个个颜颜色色各各不不相相同同的的车车： n设设8 8个车中有个车中有1 1个红车，个红车，3 3个蓝车，个蓝车，4 4个黄车。个黄车。所所以以,Y4 ,B3,R1S !4!3!1!8!4!3!1!8!82 n种。种。击车的摆放方法有击车的摆放方法有的棋盘上，非攻的棋盘上，非攻。则在。则在个个种颜色的车种颜色的车种颜色，第种颜色，第个车共有个车共有设设!,2121kkinnnnnnnnnnnnikn 定理定理3.4.33.4.33.5 多重集的组合多重集的组合 多重集多重集S S中中r r个元素进

23、行无序选择，构成一个多个元素进行无序选择，构成一个多重集的重集的r-r-组合。组合。 篮子里有篮子里有2 2个苹果，个苹果，1 1个桔子，个桔子，3 3个香蕉，篮子里个香蕉，篮子里的水果构成的水果构成“多重集多重集”。3 ,1 ,2,cbacccbaaS S S的的7-7-组合是组合是S S本身，个数为本身，个数为1 1； S S的的1-1-组合是元素种类，个数为组合是元素种类，个数为3 3； S S的的3-3-组合有：组合有： 2a,1b，2a,1c，1a,1b,1c， 1a,2c， 1b,2c，3c111111,S kkrrkrCCkknrkrrSk或或组组合合数数等等于于的的则则无无穷穷

24、重重复复数数有有种种不不同同元元素素，每每个个元元素素有有设设多多重重集集定理定理3.5.13.5.1证明证明设设S S的的r-r-组合为组合为,2211kkaxaxaxrxxxxki 21,为为非非负负整整数数其其中中即该方程非负整数解的个数。即该方程非负整数解的个数。个个1x个个2x个个nx R R个红个红1 1、k-1k-1个蓝个蓝1 1的一个排列的一个排列 对应方程的一组非负整数解。对应方程的一组非负整数解。的的排排列列数数组组合合数数等等于于集集合合的的)1( ,bkarrS 111)!1( !)!1(!21kknrkrkrkrnnn例例1 1解解有有多多少少组组非非负负整整数数解解

25、？，方方程程50132043214321 xxxxxxxx5y0,y1,y3,44332211 xxxxy令令.114321有有多多少少组组非非负负整整数数解解等等价价为为 yyyy364!3!11!141114111411 例例2 2解解组组合合数数目目有有多多少少？的的次次的的每每种种元元素素至至少少出出现现一一要要求求设设 10S,S,dcbaS1y1,y1,y1,44332211 xxxxy令令的的非非负负整整数数解解等等价价为为64321 yyyy84!3!6!9696 146 的的整整数数解解数数。，且且等等同同于于11111043214321 xxxxxxxx例例3 3解解 从从

26、1,2,1,2,k,k中取出（可重复取）一些项组成中取出（可重复取）一些项组成长度为长度为r r的非降数列，这样的数列有多少？的非降数列，这样的数列有多少？ 每个重复组合与一个非降数列一一对应。每个重复组合与一个非降数列一一对应。,2, 1kS rk-rrS1:组组合合数数为为的的例例4 4解解8,2, 1 S 面包房生产面包房生产8 8种面包圈，每种面包圈，每1212个面包圈装个面包圈装一盒。有多少种不同装法？一盒。有多少种不同装法？ 由于每盒面包圈与排列顺序无关，是无限由于每盒面包圈与排列顺序无关，是无限重复的多重集组合问题。重复的多重集组合问题。!7!12!1912 1812:12 组组合合数数为为的的S习题（第习题（第4 4版）版）4 4，8 8，1717，2121，3232，3838