1.2排列与组合解析课件

1、1.2 排列与组合1.2 一一对应原理第1页，共39页。1.2 排列与组合定义 从n个不同的元素中，取r个不重复的元素，按次序排列，称为从n个中取r个的无重排列。排列的全体组成的集合用 P(n,r)表示。1.2.1 排列所有不同排列的个数称为排列数，也记为P(n,r)。或Prn，或Arn。当r=n时称为全排列。所有不同全排列的个数记为Pn或An。第2页，共39页。1.2 排列与组合第1个盒子有n种不同选择；第2个有n-1种选择；，第r个有n-r+1种选择。故由乘法原理有 P(n,r)=n(n-1)(n-r+1) =n!/(n-r)!从n个中取r个的排列的典型例子是(取球模型):从n个有区别的球

2、中,取出r个,放入r个有标志的盒子里,且无一空盒。第3页，共39页。1.2 排列与组合规定特别，当r=n时有显然第4页，共39页。例1.2.1 由5种颜色的星状物，20种不同的花排列成如下图案：两边是星状物，中间是3朵花，问共有多少种这样的图案？ 两边是星状物，从五种颜色的星状物中取两个的排列的排列数是 P(5,2)=2020种不同的花取3种排列的排列数是P(20,3)=20 19 18=6840根据乘法法则，可得不同的图案数为20 6840=1368001.2 排列与组合第5页，共39页。例1.2.2 A单位有7名代表，B单位有3位代表，排成一列合影，如果要求B单位的3人排在一起，问有多少种

3、不同的排列方案。若A单位的2人排在队伍两端，B单位的3人不能相邻，问有多少种不同的排列方案？B单位3人按一个元素参加排列，则有 P(8,8)P(3,3)=8！3！=241920A单位的人排法固定后A*A*A*A*A*A*A，B单位第一人有6种选择，第二人有5种，第三人有4种，因此答案为 P(7,7)P(6,3)=7!654=6048001.2 排列与组合第6页，共39页。于是我们只需要计算Si即可。例1.2.3 求由1,3,5,7组成的不重复出现的整数的总和解：这样的整数可以是1位数,2位数,3位数,4位数, 显然，一位数之和 S1=1+3+5+7=16；1.2 排列与组合S=S1+S2+S3

4、+S4,若设 Si，i=1,2,3,4，是i位数的总和，则两位数有：13,15,17,31,35,37,51,53,57,71,73,75, 所以 S2=3(1+3+5+7)10+3(1+3+5+7)= 480+48=528第7页，共39页。S4=6(1+3+5+7)1000+6(1+3+5+7)100+6(1+3+5+7)10+6(1+3+5+7)=96000+9600+960+96=106656S3=6(1+3+5+7)100+6(1+3+5+7)10+6(1+3+5+7) =9600+960+96=10656S=16+528+10656+106656=117856同理1.2 排列与组合第

5、8页，共39页。1.2 排列与组合例1.2.4 假设一高速路口有4个出口，现有9辆车子从这4个口下高速，问有多少种不同的下法？解法一 假设出口编号为：K1，K2，K3，K4； 9辆车的编号为1,2,3,4,5,6,7,8,91号车选择出口有4种；2号车选择就有5种，因为当2号车与1号车选同一出口时，两车有前后顺序的问题；同理3号车有6种选择；依此类推，9号车应有12种选择。故不同的下法共有 4*5*6*12=12!/3!第9页，共39页。1.2 排列与组合解法二 如果只有一个出口，则显然9辆车的不同下法为 9！；如果有两个出口，则可以加入一个分隔符F与车辆号一起进行排列，在F的左右排列可看作是

6、分别从两个出口的一种下法，故此时的下法为 10！。本题有4个出口，应加入三个分隔符，所以不同的下法有 12!/3!.注意到，分隔标记F是无区别的第10页，共39页。1.2 排列与组合解法三 在9辆车的标号与3个分隔符共同组成的12个标记中，首先选出3个作为分隔符，不同选法有C(12,3)，然后余下的9个作为车辆标号进行排列，应有9!种不同方案，故总的下法有 C(12,3)*9!=12!/3!注意 本解法用到了组合的概念，它也可以作为基本的组合模型第11页，共39页。1.2 排列与组合定义 从n个不同元素中取r个不重复的元素组成一个子集，而不考虑其元素的顺序，称为从n个中取r个的无重组合。组合的

7、全体组成的集合用 C(n,r) 表示，所有不同组合的个数记为 C(n,r)或 Cnr若球不同，盒子相同，是从n个不同元素中取r个不重复的组合的模型。1.2.2 组合第12页，共39页。若球不同，盒子相同，则是从n个中取r个的组合的模型。若放入盒子后再将盒子标号区别，则又回到排列模型。每一个组合可有r!个标号方案。故有 C(n,r)r!=P(n,r),即 C(n,r)=P(n,r)/r!= n!r!(n-r)!1.2 排列与组合第13页，共39页。1.2 排列与组合例1.2.5 有5本不同的俄文书，7本不同的英文书，10本不同的中文书。如果从中任1)取2本不同文字的书；2)取2本相同文字的书；3

8、)任取两本书问各有多少种不同的取法？解 1) 57+510+710=155; 2) C(5,2)+C(7,2)+C(10,2)=10+21+45=76; 3) 155+76=231=C(5+7+10,2)第14页，共39页。1.2 排列与组合例1.2.6 从1,300中取3个不同的数，使这3个数的和能被3整除，有多少种方案？解 将1,300分成3类： A=i|i1(mod 3)=1,4,7,298, B=i|i2(mod 3)=2,5,8,299, C=i|i3(mod 3)=3,6,9,300. 要满足条件，有四种解法： 1) 3个数同属于A; 2) 3个数同属于B 3) 3个数同属于C;

9、4) A,B,C各取一数.故共有3C(100,3)+1003 =485100+1000000=1485100第15页，共39页。1.2 排列与组合例1.2.7 甲和乙两单位共11个成员，其中甲单位7人，乙单位4人，拟从中组成一个5人小组： 1 要求包含乙单位恰好2人； 2 要求至少包含乙单位2人； 3 要求乙单位某一人与甲单位特定一人不能同时在这个小组 试求各有多少种方案。1 C(4,2)C(7,3)2 C(4,2)C(7,3)+C(4,3)C(7,2)+C(4,4)C(7,1)3 C(10,5)+C(9,4)，或C(11,5)-C(9,3)，第16页，共39页。1.2 排列与组合定义 从n个

10、不同的元素中，取r个不重复的元素，按次序排列在一个圆周上，称为从n个中取r个的无重圆周排列。圆周排列的全体组成的集合用 Q(n,r)表示。1.2.3 圆周排列所有不同圆周排列的排列数，也记为Q(n,r)。或Qrn。注意：圆周排列的特点是没有起点与终点第17页，共39页。1.2 排列与组合对圆周排列来说，12345,51234,45123,34512,23451是一样的；一般地，圆周排列数为 Q(n,r)=P(n，r)/r =n!/(n-r)!r)123423451123412345123451234123445123123434512特别，Q(n,n)=(n-1)!第18页，共39页。例1.2

11、.8 5个男生，3个女生围一圆桌而坐，若没有任何要求则有多少种方案；若要求男生B不和女生G相邻而坐则有多少种方案；若要求3个女生不相邻又有多少种方案 如果没有要求，则圆周排列数为 Q(8,8)=7！=5040若要求男生B不和女生G相邻而坐，则排列数为Q(8,8)-2Q(7,7)=5040-1440=3600若要求3个女生不相邻，则可得不同的方案数为4！5 4 3=14401.2 排列与组合第19页，共39页。例1.2.9 n对夫妻围一圆桌而坐，若没有任何要求则有多少种方案；若要求每对夫妻相邻而坐则有多少种方案；若要求每对夫妻不相邻又有多少种方案?1.2 排列与组合 如果没有要求，则圆周排列数为

12、 Q(2n,2n)=(2n-1)!若要求每对夫妻相邻而坐，则排列数为2nQ(n,n)=2n(n-1)!若要求每对夫妻都不相邻，则计算不同的方案数较为复杂，以后（第三章相容性以后）再介绍。第20页，共39页。例1.2.10 若有2n个人分两个圆桌而坐，每桌n个人,若没有任何要求则有多少种方案；若有2n对夫妻分两个圆桌而坐，每桌n对,要求每对夫妻相邻而坐则有多少种方案；若要求每对夫妻都不座在同一张桌子上又有多少种方案?1.2 排列与组合2n个人分别坐在两张圆桌上的方案数为 C(2n,n)(n-1)!(n-1)!=(2n)!/n2若是2n对夫妻且要求每对夫妻相邻而坐，则方案数为C(2n,n)(n-1

13、)!2n(n-1)!2n=(2n)!22n/n2若要求每对夫妻都不在同一张桌子上，则不同的方案数为C(2,1)n(n-1)!(n-1)!=2n(n-1)!)2第21页，共39页。1.2 排列与组合定义 从n个不同的元素中，可重复地取r个元素，作为一组，称为从n个中取r个的可重组合。例如，从A=1,2,3中，可重复取2个的组合有1,1、1,2、1,3、2,2、2,3、3,3，共6个。1.2.4 允许重复组合与不相邻组合可重组合的模型是r个球是无区别的，n个盒子是有标记的，将r个球放入n个盒子，每个盒子允许多于一个球。注意：做允许重复组合时，r可以小于也可以大于n；每个盒子允许多于一个球，也允许空

14、盒；r表示球的个数，n表示盒子的个数。第22页，共39页。1.2 排列与组合定理 从n个不同的元素中，可重复地取r个元素，作可重组合，其组合数为 C(n+r-1,r)。只要证明：从n个不同元素中取r个作允许重复的组合和从n+r-1个不同元素中取r个作不允许重复的组合是一一对应的即可。假设n个不同元素集合A=1,2，n，从中允许重复地取出r个元素：a1，a2，ar，并且满足1a1a2arn。记：bi=ai+i-1，i=1,2，r，则1b1b2brn+r-1.即bi构成B=1,2，n+r-1上的一个不允许重复组合。显然，ai与bi是一一对应的。第23页，共39页。例1.2.11 (x+y+z)4的

15、展开式有多少项。 由于 (x+y+z)4=(x+y+z)(x+y+z)(x+y+z)(x+y+z)展开式相当于从每个括号内取一项相乘，可视为4个无区别的球(x+y+z)放入3个有标记x,y,z的盒子,每盒允许多于一个球。例如，x2yz表示x盒子有两个球，y,z盒子有一个球。所以等价于3个元素取4个作允许重复的组合，项数为C(3+4-1,4)=151.2 排列与组合第24页，共39页。例1.2.12 线性方程组x1+x2+xn=b的非负整数解的个数。 一个解 x1=a1,x2=a2,xn=an相当于xi盒子有ai个球，即一个解对应了一个将b个无区别的球放入n个有标记的盒子，允许一盒多于一个球。故

16、方程组非负整数解的数目等价于1到n的正整数取b个作允许重复的组合数所以，解的个数为 C(n+b-1,b)例如，x1+x2+x3=4的非负整数解的个数是C(3+4-1,4)=15，分别为：(4,0,0),(3,1,0),(3,0,1),(2,2,0),(2,1,1),(2,0,2),(1,3,0),(1,2,1),(1,1,2),(1,0,3),(0,4,0),(0,3,1),(0,2,2),(0,1,3),(0,0,4)1.2 排列与组合第25页，共39页。1.2 排列与组合定义 所谓不相邻组合是指从A=1,2，n中取r个不相邻的数的组合。例如，从A=1,2,3,4,5中，任取2个的不相邻组合

17、有1,3、1,4、1,5、2,4、2,5、3,5，共6个。注意：不相邻组合是一种有限制的组合。第26页，共39页。1.2 排列与组合定理 从n个不同的元素中，取r个元素作不相邻组合，其组合数为 C(n-r+1,r)。只要证明：从n个不同元素中取r个作不相邻组合和从n-r+1个不同元素中取r个作不允许重复的组合是一一对应的即可。假设n个不同元素集合A=1,2，n，从中任取出r个不相邻元素：a1，a2，ar，并且满足1a1a2arn，aiai+1-1。记：bi=ai-i+1，i=1,2，r，则1b1b2brn-r+1.即bi构成B=1,2，n-r+1上的一个不允许重复组合。显然，ai与bi是一一对

18、应的。第27页，共39页。1.2 排列与组合例如，多重集A=a, a, a, b, b, c, c, c=3a, 2b, 3c,，在A上任取两个元素的组合有a,a,a,b,a,c,b,b,b,c,c,c,共6个。1.2.5 不尽相异元素的组合注意：不是8个元素取2个，也不是3个元素取2个组合。定义 如果集合A有n个元素，其中元素a1有n1个，a2有n2个，ak有nk个，n1+n2+nk=n，则记集合A=n1a1，n2a2，nkak称为多重集合。多重集上的组合称为不尽相异元素组合第28页，共39页。1.2 排列与组合注： 不尽相异元素的组合数的一般计算方法，在下一章(第二章母函数以后)给出。例1

19、.2.13 如果集合A有n个不同元素，有m个相同元素，即A=1a1，1a2，1an，ma0，从中任取r个元素的组合。其不同的组合数是多少。不取a0，从n个不同元素中取r个，有C(n,r)种；取1个a0，从n个不同元素中取r-1个，有C(n,r-1)种；取2个a0，从n个不同元素中取r-2个，有C(n,r-2)种；一般地，取k个a0，从n个不同元素中取r-k个，有C(n,r-k)种；故任取r个元素的组合数等于 C(n,r)+C(n,r-1)+C(n,0)。第29页，共39页。1.2 排列与组合注：在以上解法中，假设了nr，mr。如果nr，mr, 则组合数等于 C(n,n)+C(n,n-1)+C(

20、n,0)。如果mr，nr，则组合数等于 C(n,r)+C(n,r-1)+C(n,r-m)。如果nr，mr，则组合数等于 C(n,n)+C(n,n-1)+C(n,r-m)。第30页，共39页。1.2 排列与组合定义 如果在排列中限定了某些元素在某些位置的出现方式或次数，则称为有限制排列。例如，缺位排列是不允许某些元素在某些位置出现(0次)；1.2.6 有限制排列错位排列是第i个元素不允许出现在第i个位置；多位排列是允许元素以多种方式出现(可1次以上)。第31页，共39页。1.2 排列与组合定义 将n2个数排成n行n列的一个数表用来表示一个数，其值等于所有可能取自不同行不同列的n个元素乘积的和，称

21、为积和式，即例如，第32页，共39页。1.2 排列与组合注意到：在以上二阶和三阶积和式的展开式中，对应的恰好是全排列的项。特别有排列数可表示为如果我们将行视为元素列视为位置，aij表示元素i排在j位置方式与可能性，即aij=0表示元素i不允许排在j位置；aij=1表示元素i允许排在j位置；aij=k表示元素i允许以k种方式排在j位置；则积和式的值表示该限定排列的排列数。第33页，共39页。例1.2.14 P，Q，R，S四位工人，A，B，C，D四项任务。条件如下：P不干B；Q不干B、C；R不干C、D；S不干D。问有多少种可行方案？例1.2.15 0,1,2,3能组成多少个不重复数字的4位偶数1.2 排列与组合第34页，共39页。例