《《组合数学讲》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《组合数学讲》PPT课件.ppt（59页珍藏版）》请在金锄头文库上搜索。
1、前言前言组合数学是一个古老而又年轻的数学分支。组合数学是一个古老而又年轻的数学分支。据传说，大禹在据传说，大禹在4000多年前就观察到神龟背多年前就观察到神龟背上的幻方上的幻方.幻方可以看作是一个幻方可以看作是一个3阶方阵，其元素是阶方阵，其元素是1到到9的正整数，每行、的正整数，每行、每列以及两条对角线每列以及两条对角线的和都是的和都是15。519372486前言前言1666年莱布尼兹所著年莱布尼兹所著组合学论文组合学论文一书一书问世，这是组合数学的第一部专著。书中首问世，这是组合数学的第一部专著。书中首次使用了组合论（次使用了组合论（Combinatorics）一词。）一词。组合数学的蓬勃
2、发展则是在计算机问世和组合数学的蓬勃发展则是在计算机问世和普遍应用之后。由于组合数学涉及面广，内普遍应用之后。由于组合数学涉及面广，内容庞杂，并且仍在很快地发展着，因而还没容庞杂，并且仍在很快地发展着，因而还没有一个统一而有效的理论体系。这与数学分有一个统一而有效的理论体系。这与数学分析形成了对照。析形成了对照。组合数学研究的中心问题是按一定规则将组合数学研究的中心问题是按一定规则将一些事物安排成各式各样模式的问题。包括一些事物安排成各式各样模式的问题。包括安排的存在问题、计数问题、构造问题以及安排的存在问题、计数问题、构造问题以及给出了优化标准后如何求出最优安排问题。给出了优化标准后如何求出
3、最优安排问题。前言前言组合数学经常使用的方法并不高深复杂。最组合数学经常使用的方法并不高深复杂。最主要的方法是计数时的合理分类和组合模型的主要的方法是计数时的合理分类和组合模型的转换。转换。但是，要学好组合数学并非易事，既需要但是，要学好组合数学并非易事，既需要一定的数学修养，也要进行相当的训练。一定的数学修养，也要进行相当的训练。第一章第一章 排列与组合排列与组合n1.1 1.1 加法法则与乘法法则加法法则与乘法法则. .加法法则加法法则设事件设事件A有有m种产生方种产生方式，事件式，事件B有有n种产生方式，则事件种产生方式，则事件A或或B之一有之一有m+n种产生方式。种产生方式。集合论语言
4、：集合论语言：若若|A|=m,|B|=n,A B=,则则|A B|=m+n。第一章第一章 排列与组合排列与组合例例某班选修企业管理的有某班选修企业管理的有18人，人，不选的有不选的有10人，则该班共有人，则该班共有18+10=28人。人。例例北京每天直达上海的客车有北京每天直达上海的客车有5次，次，客机有客机有3次，次，则每天由北京直达上海的则每天由北京直达上海的旅行方式有旅行方式有5+3=8种。种。第一章第一章 排列与组合排列与组合乘法法则乘法法则设事件设事件A有有m种产生式，种产生式，事件事件B有有n种产生方式，则事件种产生方式，则事件A与与B有有mn种产生方式。种产生方式。集合论语言：集
5、合论语言：若若|A|=m,|B|=n,A B=(a,b)|a A,b B,则则|A B|=mn。第一章第一章 排列与组合排列与组合例例某种字符串由两个字符组成，第某种字符串由两个字符组成，第一个字符可选自一个字符可选自a，b，c，d，e，第二个字符可选自第二个字符可选自1，2，3，则这，则这种字符串共有种字符串共有5 3=15个。个。例例从从A到到B有三条道路，从有三条道路，从B到到C有两条道路，则从有两条道路，则从A经经B到到C有有3 2=6条道路。条道路。第一章第一章 排列与组合排列与组合n例例 某种样式的运动服的着色由底色和某种样式的运动服的着色由底色和装饰条纹的颜色配成。底色可选红、蓝
6、、装饰条纹的颜色配成。底色可选红、蓝、橙、黄，条纹色可选黑、白，则共有橙、黄，条纹色可选黑、白，则共有4 4 2 2 = 8= 8种着色方案。种着色方案。n若此例改成底色和条纹都用红、蓝、橙、若此例改成底色和条纹都用红、蓝、橙、黄四种颜色的话，则方案数就不是黄四种颜色的话，则方案数就不是4 4 4 = 4 = 1616， 而只有而只有 4 4 3 = 12 3 = 12 种。种。n在乘法法则中要注意事件在乘法法则中要注意事件 A A 和和 事件事件 B B 的相互相容性。的相互相容性。第一章第一章 排列与组合排列与组合例例 1)1)求小于求小于1000010000的含的含1 1的正整数的个数的
7、正整数的个数 2)2)求小于求小于1000010000的含的含0 0的正整数的个数的正整数的个数1)1)小于小于1000010000的不含的不含1 1的正整数可看做的正整数可看做4 4位位数数, ,但但00000000除外除外. . 故有故有9 99 99 99 91 165606560个个. . 含含1 1的有：的有：999999996560=34396560=3439个个另另: : 全部全部4 4位数有位数有10104 4 个个, ,不含不含1 1的四位数的四位数有有9 94 4个个, ,含含1 1的的4 4位数为两个的差位数为两个的差: 10: 104 49 94 4 = 3439= 3
8、439个个第一章第一章 排列与组合排列与组合2)2)“含含0 0”和和“含含1 1”不可直接套用。不可直接套用。00190019含含1 1但不含但不含0 0。 在组合的习题中有许多类似的在组合的习题中有许多类似的隐含隐含的的规定，要特别留神。规定，要特别留神。 不含不含0 0的的1 1位数有位数有9 9个，个，2 2位数有位数有9 92 2个，个，3 3位数有位数有9 93 3个，个，4 4位数有位数有9 94 4个个 不含不含0 0小于小于1000010000的正整数有的正整数有9+99+92 2+9+93 3+9+94 4=(9=(95 51)/(91)/(91)=73801)=7380个
9、个含含0 0小于小于1000010000的正整数有的正整数有 999999997380=26197380=2619个个第一章第一章 排列与组合排列与组合n n1.21.2排列与组合排列与组合n定义：定义：从从n n个不同的元素中，取个不同的元素中，取r r个不重复个不重复的元素，按次序排列，称为从的元素，按次序排列，称为从n n个中取个中取r r个个的的排列排列。其排列的个数记为。其排列的个数记为P(n,r)(n,r)表示。表示。nr 若取出若取出r r个元素而不考虑次序，则称从个元素而不考虑次序，则称从n n个不同元中取个不同元中取r r个元的组合。其组合的个个元的组合。其组合的个数记为数记
10、为C(n,r)C(n,r)或（或（ ）第一章第一章 排列与组合排列与组合规定：规定：从从n n个不同元中取个不同元中取n n个的排列称为个的排列称为n n的的全排全排列列第一章第一章 排列与组合排列与组合我们有下列排列与组合的计数公式：我们有下列排列与组合的计数公式：特别地，对于全排列有特别地，对于全排列有P(n,n)=n!。第一章第一章 排列与组合排列与组合n从从n n个中取个中取r r个的排列的典型例子是从个的排列的典型例子是从n n个不同的球中个不同的球中, ,取出取出r r个个, ,放入放入r r个不同的个不同的盒子里盒子里, ,每盒每盒1 1个。第个。第1 1个盒子有个盒子有n n种
11、选择，种选择，第第2 2个有个有n-1n-1种选择，种选择，第，第r r个有个有n-n-r+1r+1种选择。种选择。n故有故有P(n,r)=n(n-1)P(n,r)=n(n-1) (n-r+1) (n-r+1)n有时也用有时也用nrnr记记P(n,r)第一章第一章 排列与组合排列与组合n若球不同，盒子相同，则是从若球不同，盒子相同，则是从n n个中取个中取r r个的个的组合组合的模型。若放入盒子后再将盒的模型。若放入盒子后再将盒子标号区别，则又回到排列模型。每一子标号区别，则又回到排列模型。每一个组合可有个组合可有r!r!个标号方案。个标号方案。n故有故有 C(n,r)C(n,r)r!=P(n
12、,r),r!=P(n,r),n nr rn!n! r!(n-r)! r!(n-r)!nC(n,r)C(n,r)=P(n,r)/r!=nr/r!=P(n,r)/r!=nr/r! =( )= =( )=第一章第一章 排列与组合排列与组合n例例 有有5 5本不同的日文书，本不同的日文书，7 7本不同的英文本不同的英文书，书，1010本不同的中文书。本不同的中文书。1)1)取取2 2本不同文字的书；本不同文字的书；2)2)取取2 2本相同文字的书；本相同文字的书；3)3)任取两本书任取两本书请问有多少种不同的取法？请问有多少种不同的取法？解：解：1)51)57+57+510+710+710=155;1
13、0=155; 2)C(5,2)+C(7,2)+C(10,2)=10+21+45=76; 2)C(5,2)+C(7,2)+C(10,2)=10+21+45=76; 3) 155+76=231=( ) 3) 155+76=231=( )5+7+105+7+10 2 2第一章第一章 排列与组合排列与组合n例例 从从1,3001,300中取中取3 3个不同的数，使这个不同的数，使这3 3个数的个数的和能被和能被3 3整除，有多少种方案？整除，有多少种方案？解：将解：将1,3001,300分成分成3 3类：类： A=i|i1(mod 3)=1,4,7,A=i|i1(mod 3)=1,4,7,298,29
14、8, B=i|i2(mod 3)=2,5,8, B=i|i2(mod 3)=2,5,8,299,299, C=i|i3(mod 3)=3,6,9, C=i|i3(mod 3)=3,6,9,300.,300.要满足条件，有四种解法：要满足条件，有四种解法： 1)31)3个数同属于个数同属于A; 2)3A; 2)3个数同属于个数同属于B B 3)3 3)3个数同属于个数同属于C; 4)A,B,CC; 4)A,B,C各取一数各取一数. .故共有故共有3C(100,3)+1003C(100,3)+1003 3 =1485100 =1485100第一章第一章 排列与组合排列与组合n定义：从定义：从n n
15、个不同元素中允许重复地取个不同元素中允许重复地取r r个元素个元素作排列，称为作排列，称为n n元可重元可重r-r-排列，其排列数为排列，其排列数为n nr rn例：由数字例：由数字1 1，2 2，3 3可组成多少个两位数？并写可组成多少个两位数？并写出这些两位数。出这些两位数。n解：这是三元可重解：这是三元可重2-2-排列问题。其排列数为排列问题。其排列数为3 32 2=9=9。这些两位数为。这些两位数为11,12,13,21,22,23,31,32,3311,12,13,21,22,23,31,32,33。n n1 1个个a a1 1,n,n2 2个个a a2 2, ,n nk k个个a
16、ak k的全排列的个数为的全排列的个数为: :第一章第一章 排列与组合排列与组合n定义：从定义：从n个不同元素中取个不同元素中取r个元素围成一圈，个元素围成一圈，称为从称为从n个不同元中取个不同元中取r个元的圆排列，其排个元的圆排列，其排列数记为列数记为K(n,r)。我们有：。我们有：123r-1r这是因为这是因为r个不同的个不同的线排列（即一般的线排列（即一般的排列）对应于一个排列）对应于一个圆排列。圆排列。第一章第一章 排列与组合排列与组合n例：例：4个女生和个女生和4个男生围圆桌相间而坐，试个男生围圆桌相间而坐，试问有多少种不同的入座方式？问有多少种不同的入座方式？n解：先让女生入座，这
17、是一个解：先让女生入座，这是一个4的圆排列问的圆排列问题。有题。有K（4，4）4!=4！/44!=3！4!。n例例:由四种颜色的珠子各一颗，可以做成多少由四种颜色的珠子各一颗，可以做成多少种不同的项链？种不同的项链？n解：注意项链可以翻转。解：注意项链可以翻转。第一章第一章 排列与组合排列与组合n定义：从定义：从n个不同元中允许重复地取个不同元中允许重复地取r个元的个元的组合，称为组合，称为n元可重元可重r-组合，其组合数记为组合，其组合数记为F(n,r)。用集合描述为：重集。用集合描述为：重集a1,a2,an的的r-组合数为组合数为F(n,r)。结论：结论：F(n,r)=C(n+r-1,r)
18、，其中，其中n,r均为正整数。均为正整数。证明要点：设证明要点：设a1,a2,ar是从是从1,2,n中任取的一中任取的一个可重个可重r-组合，不妨设：组合，不妨设：1a1a2arn从而有：从而有：1a1a2+1a3+2ar+r-1n+r-1第一章第一章 排列与组合排列与组合n例例: :某车站有某车站有6 6个入口处，每个入口处每个入口处，每个入口处每次只能进一人，一组次只能进一人，一组9 9个人进站的方案有个人进站的方案有多少？多少？ 解解 一进站方案表示成：一进站方案表示成：0001100101010000011001010100其中其中“0 0”表示人，表示人，“1 1”表示门框，其中表示
19、门框，其中“0 0”是不同元，是不同元，“1 1”是相同元。给是相同元。给“1 1”n n个门只用个门只用n-1n-1个门框。任意进站方个门框。任意进站方案可表示成上面案可表示成上面1414个元素的一个排列。个元素的一个排列。第一章第一章 排列与组合排列与组合n 解法解法11标号可产生标号可产生5!5!个个1414个元的全排列。个元的全排列。n故若设故若设x x为所求方案，则为所求方案，则n x x5!=14!5!=14!n x=14!/5!=726485760 x=14!/5!=726485760n 解法解法22在在1414个元的排列中先确定个元的排列中先确定“1 1”的的位置，有位置，有C
20、(14,5)C(14,5)种选择，在确定人的位种选择，在确定人的位置，有置，有9 9！种选择。！种选择。n故故C(14,5)C(14,5)9!9!即所求即所求第一章第一章 排列与组合排列与组合n 解法解法33把全部选择分解成若干步，使每步把全部选择分解成若干步，使每步宜于计算。不妨设宜于计算。不妨设9 9个人编成个人编成1 1至至9 9号。号。1 1号号有有6 6种选择；种选择；2 2号除可有号除可有1 1号的所有选择外，号的所有选择外，还可（也必须）选择当与还可（也必须）选择当与1 1号同一门时在号同一门时在1 1号的前面还是后面，故号的前面还是后面，故2 2号有号有7 7种选择；种选择；3
21、 3号号的选择方法同的选择方法同2 2号，故共有号，故共有8 8种。种。n以此类推，以此类推，9 9号有号有1414种选择。种选择。n故所求方案为故所求方案为6 67 7 8 81414种。种。第一章第一章 排列与组合排列与组合n n1.31.3模型转换模型转换n“一一对应一一对应”概念是一个在计数中极为基概念是一个在计数中极为基本的概念。一一对应既是单射又是满射。本的概念。一一对应既是单射又是满射。n如我们说如我们说A A集合有集合有n n个元素个元素 |A|=n|A|=n，无非是，无非是建立了将建立了将A A中元与中元与1,n1,n元一一对应的关系元一一对应的关系. .n在组合计数时往往借
22、助于一一对应实现模在组合计数时往往借助于一一对应实现模型转换。型转换。n比如要对比如要对A A集合计数，但直接计数有困难集合计数，但直接计数有困难, ,于是可设法构造一易于计数的于是可设法构造一易于计数的B B，使得，使得A A与与B B一一对应。一一对应。第一章第一章 排列与组合排列与组合n例例 在在100100名选手之间进行淘汰赛名选手之间进行淘汰赛( (即一即一场的比赛结果，失败者退出比赛场的比赛结果，失败者退出比赛),),最后最后产生一名冠军，问要举行几场比赛？产生一名冠军，问要举行几场比赛？n解解 一种常见的思路是按轮计场，费事。一种常见的思路是按轮计场，费事。另一种思路是淘汰的选手
23、与比赛另一种思路是淘汰的选手与比赛( (按场计按场计) )集一一对应。集一一对应。9999场比赛。场比赛。第一章第一章 排列与组合排列与组合n n例例简单格路问题简单格路问题|(0,0)(m,n)| =( |(0,0)(m,n)| =( ).).从从 (0,0)(0,0)点出发沿点出发沿x x轴或轴或y y轴的正方轴的正方向每步走一个单位，最终走到向每步走一个单位，最终走到(m,n)(m,n)点，点，有多少条路径？有多少条路径？m+nmy(m,n).O.x第一章第一章 排列与组合排列与组合n无论怎样走法，在无论怎样走法，在x x方向上总共走方向上总共走m m步，步，在在y y方向上总共走方向上
24、总共走n n步。若用一个步。若用一个x x表示表示x x方向上的一步，一个字母方向上的一步，一个字母y y表示表示y y方向上方向上的一步。的一步。n则则(0,0)(m,n)(0,0)(m,n)的每一条路径可表示为的每一条路径可表示为m m 个个x x与与n n个个y y的一个有重排列。将每一的一个有重排列。将每一个有重排列的个有重排列的x x与与y y分别编号，可得分别编号，可得m!n!m!n!个个m+nm+n元的无重全排列。元的无重全排列。第一章第一章 排列与组合排列与组合n设所求方案数为设所求方案数为P(m+nP(m+n；m m，n)n)n则则P(m+nP(m+n；m m，n)n)m!m
25、!n!=(m+n)!n!=(m+n)!n故故P(m+n;m,n)= P(m+n;m,n)= = ( ) = ( ) =( )=C(m+n,m) =( )=C(m+n,m) (c,d)(a,b)(m+n)!(m+n)! m!n! m!n! m+nm+n n nm+nm+n m m( (c-a)+(d-b)c-a)+(d-b) c-a c-an设设ca,db,ca,db,则由则由(a,b)(a,b)到到(c,d)(c,d)的简单格路数的简单格路数为为|(a,b)(c,d)|=( )|(a,b)(c,d)|=( )第一章第一章 排列与组合排列与组合n例：在上例的基础上若设例：在上例的基础上若设mnm
26、n，求，求(0,1)(0,1)点到点到(m,n)(m,n)点不接触对角线点不接触对角线x=yx=y的格路的数目的格路的数目( (“接触接触”包括包括“穿过穿过”) )n从从(0,1)(0,1)点到点到(m,n)(m,n)点的格路，有的接触点的格路，有的接触x=yx=y，有，有的不接触。的不接触。n对每一条接触对每一条接触x=yx=y的格路，做的格路，做(0,1)(0,1)点到第一个点到第一个接触点部分关于接触点部分关于x=yx=y的对称格路，这样得到一条的对称格路，这样得到一条从从(1,0)(1,0)到到( (m,n)m,n)的格路。的格路。第一章第一章 排列与组合排列与组合n容易看出从容易看
27、出从(0,1)(0,1)到到(m,n)(m,n)接触接触x=yx=y的格路的格路与与 (1,0)(1,0)到到(m,n)(m,n)的格路的格路( (必穿过必穿过x=y)x=y)一一一一对应对应y y=x (m,n)O (1,0) x(0,1). .n故所求格路数为故所求格路数为( )( )( )( )。m+n-1m+n-1mm-1第一章第一章 排列与组合排列与组合n若条件改为可接触但不可穿过，则限制若条件改为可接触但不可穿过，则限制线要向下或向右移一格，得线要向下或向右移一格，得x xy=1y=1，(0,0)(0,0)关于关于x xy=1y=1的对称点为的对称点为(1,-1).(1,-1).格
28、路也是一种常用模型m+nm+nmm-1(m+n)!(m+n)!m!n!(m-1)!(n+1)!m+nmn+1-mn+1n所求格路数为所求格路数为 ( )( )( )( ) = = = = ( ) ( )y x-y=1 (m,n) x(0,0) (1,-1). . .第一章第一章 排列与组合排列与组合n例例CnH2n+2是碳氢化合物是碳氢化合物,随着随着n的不同的不同有下列不同的枝链：有下列不同的枝链：H|HCH|HH|HCH|HCH|HH|HCH|HCH|HCH|Hn=1甲烷甲烷n=2乙烷乙烷n=3丙烷丙烷第一章第一章 排列与组合排列与组合H|HCH|HCH|HCH|HCH|HH|HHCH|H
29、CCH|HCH|HHn=4丁烷丁烷n=4异丁烷异丁烷这说明对应CnH2n+2的枝链是有3n+2个顶点的一棵树，其中n个顶点与之关联的边数为4；其它2n+2个顶点是叶子。对于这样结构的每一棵树，就对应有一种特定的化合物。从而可以通过研究具有上述性质的树找到不同的碳氢化合物CnH2n+2.第一章第一章 排列与组合排列与组合n n1.41.4全排列的生成算法全排列的生成算法n 就是对于给定的字符集，用有效的就是对于给定的字符集，用有效的方法将所有可能的全排列方法将所有可能的全排列无重复无遗漏无重复无遗漏地枚举出来。地枚举出来。 n全排列的生成算法有许多种，我们仅全排列的生成算法有许多种，我们仅介绍其
30、中一种介绍其中一种-序数法序数法第一章第一章 排列与组合排列与组合n n1.4.11.4.1全排列的生成全排列的生成- -序数法序数法任一自然数任一自然数n都可以唯一确定一个都可以唯一确定一个p进制进制数数,反之也然。反之也然。类似地，有类似地，有第一章第一章 排列与组合排列与组合同理同理所以所以即即第一章第一章 排列与组合排列与组合不难证明，从不难证明，从0到到n!-1的任一个整数的任一个整数m都都可唯一地表示为：可唯一地表示为：所以从所以从0到到n!-1的的n!个整数与满足上式的序个整数与满足上式的序列列(an-1,an-2,a2,a1)一一对应。一一对应。然后我们再从然后我们再从(an-
31、1,an-2,a2,a1)建立与全排建立与全排列的一一对应关系。列的一一对应关系。第一章第一章 排列与组合排列与组合例例：m4000，即，即n14000第一章第一章 排列与组合排列与组合现从序列现从序列 (an-1,an-2,a2,a1)得到生成排列，为得到生成排列，为了方便起见了方便起见, ,不妨今不妨今n n个对象分别是个对象分别是1,2,1,2, n. n.建立起对应的规则如下：建立起对应的规则如下：设序列设序列(an-1,an-2,a2,a1)对应某个排列对应某个排列( (p p)=p)=p1 1 p p2 2, ,p,pn n，其中其中ai可以看作是排列可以看作是排列(p)中数中数i
32、+1所在位置后所在位置后面比面比i+1小的数的个数，小的数的个数，也就是排列也就是排列(p)中从数中从数i+1开始向右统计小于开始向右统计小于或等于或等于i的数的个数。的数的个数。第一章第一章 排列与组合排列与组合以排列以排列42134213为例，为例，4 4后面比它小的数的个数后面比它小的数的个数( (即即a a3 3) )为为3;3;3 3后面比它小的数的个数后面比它小的数的个数( (即即a a2 2) )等于等于0;0;2 2后面比它小的数的个数后面比它小的数的个数( (即即a a1 1) )为为1 1；排列中比排列中比1 1小的数是没有的小的数是没有的故得故得(p)=(4213) (a
33、(p)=(4213) (a3 3a a2 2a a1 1) )(301)(301)我们称我们称a a3 3a a2 2a a1 1为中介数。为中介数。第一章第一章 排列与组合排列与组合n n1.51.5组合的生成算法组合的生成算法组合的生成不如排列生成困难今以从1、2、3、4、5、6取3个的组合为例: (1)123， (2) 124， (3)125， (4)126， (5)134， (6)135， (7)136， (8)145， (9)146， (10)156， (11)234， (12) 235，(13)236， (14)245， (15)246， (16) 256，(17)345， (18
34、)346， (19) 356，(20)456第一章第一章 排列与组合排列与组合从中可得规律：从中可得规律：（1）最后一位数最大可达）最后一位数最大可达n，倒数第，倒数第2位最位最大可达大可达n-1，依此类推倒数第，依此类推倒数第k位位(kr)不得超过不得超过n-k+1若若r个元素的组合用个元素的组合用c1c2cr来表示，不妨假定来表示，不妨假定c1c21,有有C(n-1,r)种方案种方案共有共有C(n-1,r)+C(n-1,r-1)中方案，中方案，第一章第一章 排列与组合排列与组合n n3.()+()+()+()=()(1.6.3)nn+1n+2n+rn+r+1nnnnra1=2,a2an+1
35、取自取自3,n+r+1有有()种取法种取法n+r-1na1=r,a2an+1取自取自r+1,n+r+1有有()种取法种取法n+1n也可看做按含也可看做按含1不含不含1，含，含2不含不含2,含含r不含不含r的不断分类的不断分类1可从可从(6.2)推论，也可做一下组合证明推论，也可做一下组合证明从从1,n+r+1取取a1a2anan+1，设，设a1a2anan+1，可按，可按a1的取值分类：的取值分类：a1=1,2,3,r,r+1.a1=r+1,a2an+1取自取自r+2,n+r+1有有()种取法种取法nnn+rna1=1,a2an+1取自取自2,n+r+1有有()种取法种取法第一章第一章 排列与
36、组合排列与组合选政治局选政治局,再选常委再选常委,n个中央委员选出个中央委员选出l名政治局委员名政治局委员,再从其中选出再从其中选出r名常委名常委选常委选常委,再选非常委政治局委员再选非常委政治局委员两种选法都两种选法都无遗漏无遗漏,无重复无重复地给出可能的方地给出可能的方案，应该相等。案，应该相等。nlnn-rlrrl-rn4.()()=()()(1.6.4)第一章第一章 排列与组合排列与组合mkm-kmmkk=0证证1 1( (x+y)x+y) = =( ()x)x y , y , 令令x=y=1,x=y=1,得得(1.6.5)(1.6.5)n5.()+()+()=2,m0,(1.6.5)
37、mmmm01m组合证组合证 1,1,mm的所有方案的所有方案. .每一元素都可取每一元素都可取或不取两种状态，由乘法原理可知所有状或不取两种状态，由乘法原理可知所有状态数为态数为2 2m m. . 而这些可分解为从而这些可分解为从m m个元素中分别取个元素中分别取0 0个个,1,1个，个，2 2个，个，m m个组合的总和。个组合的总和。第一章第一章 排列与组合排列与组合n例例某保密装置须同时使用若干把不同的钥匙某保密装置须同时使用若干把不同的钥匙才能打开。现有人，每人持若干钥匙。须才能打开。现有人，每人持若干钥匙。须人到场，所备钥匙才能开锁。问人到场，所备钥匙才能开锁。问n至少有多少把不同的钥
38、匙？至少有多少把不同的钥匙？n每人至少持几把钥匙？每人至少持几把钥匙？n解解每人至少缺把钥匙，且每人所缺每人至少缺把钥匙，且每人所缺钥匙不同。故至少共有钥匙不同。故至少共有()=35把不同的钥匙。把不同的钥匙。7 73 3n任一人对于其他人中的每人，都至少有任一人对于其他人中的每人，都至少有把钥匙与之相配才能开锁。故每人至少持把钥匙与之相配才能开锁。故每人至少持()20把不同的钥匙。把不同的钥匙。一般地一般地某保密装置安装了一个电子锁某保密装置安装了一个电子锁.须同时使须同时使用若干把不同的钥匙才能打开。现有用若干把不同的钥匙才能打开。现有n人，每人，每人有一把钥匙。必须人有一把钥匙。必须m人
39、人(mn)到场，才能用到场，才能用钥匙开锁。问怎么分配锁的特征和每个的钥钥匙开锁。问怎么分配锁的特征和每个的钥匙上的特征匙上的特征?既然锁比任意既然锁比任意m-1把钥匙多一个特征，而任意两把钥匙多一个特征，而任意两个个m-1把钥匙组合缺少的特征不同，所以锁的特征至把钥匙组合缺少的特征不同，所以锁的特征至少为少为C(n,m-1)个。个。同样道理，对于同样道理，对于m把钥匙中的一把把钥匙中的一把a，加入任意，加入任意m-1把钥匙必能打开锁，也即剩下的把钥匙必能打开锁，也即剩下的n-1把钥匙中任把钥匙中任意意m-1把钥匙必然缺少把钥匙必然缺少a中的某项特征，所以每把钥中的某项特征，所以每把钥匙的特征
40、数至少为匙的特征数至少为C(n-1,m-1)个。个。每个锁的特征在钥每个锁的特征在钥匙中出现的次数匙中出现的次数锁的特征数锁的特征数上式实际说明了一个构造锁及磁卡的方法。上式实际说明了一个构造锁及磁卡的方法。钥匙特征满钥匙特征满足最低要求足最低要求以以n=5,m=3为为例，在为为例，在MATLAB输入以下指令：输入以下指令：n=5;m=3;v=nchoosek(1:5,n-m+1)v=111111222322233433443454554555#10#10#10#10#10#10#9#9#9#9#9#9#8#8#8#8#8#8#7#7#7#7#7#7#6#6#6#6#6#6#5#5#5#5#5
41、#5#4#4#4#4#4#4#3#3#3#3#3#3#2#2#2#2#2#2#1#1#1#1#1#1钥匙钥匙5 5钥匙钥匙4 4钥匙钥匙3 3钥匙钥匙2 2钥匙钥匙1 1#10#10#9#9#8#8#7#7#6#6#5#5#4#4#3#3#2#2#1#1特征特征钥匙钥匙123124125134135145235234245345第一章第一章 排列与组合排列与组合例例设设n位长能纠位长能纠r个错的码字的个数为个错的码字的个数为M，则，则n位长的位长的0-1字符串共有字符串共有2n个。但不能每个串都设个。但不能每个串都设为码字，否则失去纠错能力。为码字，否则失去纠错能力。第一章第一章 排列与组合排
42、列与组合Hamming距离距离:设设a=a1a2an，b=b1b2bn是是n位串。位串。则则a,b的的Hamming距离为距离为即对应位不同的位的个数。它有如下性质：即对应位不同的位的个数。它有如下性质：d(a,b)0(当且仅当当且仅当a=b时，等号成立时，等号成立)；d(a,b)=d(b,a);d(a,b)+d(b,c)d(a,c)第一章第一章 排列与组合排列与组合右图表示以右图表示以a为球心为球心,r位半径的球位半径的球体中的体中的串都作为串都作为a处理。若规定处理。若规定a是码字，收到是码字，收到a有有d(a,a)r即将即将a当作当作a发生最多发生最多r个错误。此时两个个错误。此时两个码字码字a,b应满足应满足d(a,b)2r+1。当作。当作a处理的串的个数为处理的串的个数为故故ara第一章第一章 排列与组合排列与组合另一方面任一串与最近的码字的距离不大于另一方面任一串与最近的码字的距离不大于2r，否则此串本身可作为一新的码字，即以，否则此串本身可作为一新的码字，即以2r位位半径的各码字为球心，应当使任一串落入某球半径的各码字为球心，应当使任一串落入某球内，故内，故故所以结论成立。故所以结论成立。
