组合数学之排列组合生成算法幻灯片.ppt

《组合数学之排列组合生成算法幻灯片.ppt》由会员分享，可在线阅读，更多相关《组合数学之排列组合生成算法幻灯片.ppt（58页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、组合数学之排列组合生成算法第1页，共58页，编辑于2022年，星期一2第二讲第二讲:排列组合的生成算法排列组合的生成算法(1)存在存在:满足一定条件配置的存在性满足一定条件配置的存在性.(2)计数：计数：计算出满足条件配置的数目计算出满足条件配置的数目.(3)算法：算法：构造所有配置的算法构造所有配置的算法.(4)优化：优化：优化算法优化算法.组合数学的主要问题组合数学的主要问题:第2页，共58页，编辑于2022年，星期一3一一.排列生成算法排列生成算法l排列生成有几种典型算法排列生成有几种典型算法,这些算法这些算法 都很有成效都很有成效.它们在实际中具有广泛它们在实际中具有广泛 应用价值应用

2、价值.1.序数法序数法2.字典序法字典序法3.邻位互换法邻位互换法(Johnson-Trotter)4.轮转法轮转法 第3页，共58页，编辑于2022年，星期一41.序数法序数法 l序数法基于一一对应概念序数法基于一一对应概念.l先先在在排排列列和和一一种种特特殊殊的的序序列列之之间间建建立立 一一种种一一一一对对应应关关系系,然然后后再再给给出出由由序序列列产产生生排列的方法排列的方法l l因因为为序序列列的的产产生生非非常常方方便便,这这样样我我们们就就可可以以得到一种得到一种利用序列来生成排列的方法利用序列来生成排列的方法.l l如何建立这种一一对应如何建立这种一一对应?第4页，共58页

3、，编辑于2022年，星期一5l思路类似数的思路类似数的10进制、进制、2进制和进制和p进制表进制表示示.第5页，共58页，编辑于2022年，星期一6l这相当于自然数与某种序列之间建立了这相当于自然数与某种序列之间建立了一一对应关系一一对应关系.l l可以利用置换来表示整数可以利用置换来表示整数:n!=n(n-1)!=(n-1+1)(n-1)!=(n-1)(n-1)!+(n-1)!(n-1)!=(n-2)(n-2)!+(n-2)!n!=(n-1)(n-1)!+(n-2)(n-2)!+(n-3)(n-3)!+22!+11!+1第6页，共58页，编辑于2022年，星期一7ln!-1=(n-1)(n-

4、1)!+(n-2)(n-2)!+(n-3)(n-3)!+2 2!+11!l l可以证明可以证明,从从0到到n!-1之间的任何整数之间的任何整数m 都可唯一地表示为都可唯一地表示为:m=an-1(n-1)!+an-2(n-2)!+a2 2!+a1 1!其中其中0 ai i,i=1,2,n-1.l lm与序列与序列(an-1,an-2,a2,a1)一一对应一一对应l l书中有确定这些系数的方法书中有确定这些系数的方法.l l 例如：例如：101 3!2 2!0 1!第7页，共58页，编辑于2022年，星期一8l因为满足条件因为满足条件 0 ai i,1 i n-1 （2.1）的序列的序列 (an-

5、1,an-2,a2,a1)共有共有n!个个,这恰好与这恰好与0到到n!-1的的n!个整数一个整数一一对应一对应.l需要建立满足条件需要建立满足条件(2.1)的的n!个序列个序列 (an-1,an-2,a2,a1)和和n元集合元集合S的的 全部排列之间的一一对应关系全部排列之间的一一对应关系.第8页，共58页，编辑于2022年，星期一9l还需要给出一种办法还需要给出一种办法,由每个满足条件由每个满足条件(2.1)的序列的序列(an-1,an-2,a2,a1)可生成唯一可生成唯一的一个排列的一个排列.l这样我们就可以产生出所有的排列这样我们就可以产生出所有的排列.l怎么样由一个满足条件怎么样由一个

6、满足条件(2.1)的序列产生的序列产生一个一个n阶排列阶排列?l l如何把如何把1,2,n的一个排列与一个满足条件的一个排列与一个满足条件(2.1)的序列建立起直接的关系的序列建立起直接的关系?第9页，共58页，编辑于2022年，星期一10l l行列式定义中有行列式定义中有逆序数逆序数的概念的概念,就是一个就是一个排列中违反自然顺序的数对排列中违反自然顺序的数对:比如比如12354的逆序数为的逆序数为1,而而43215的逆序数为的逆序数为6.l l设设p1p2pn是任意一个是任意一个n元排列元排列,则则i+1后后面比面比i+1小的数字的个数小的数字的个数ai总不超过总不超过i,即即ai i,i

7、=1,2,n-1.l这样自然由一个排列得到一个序列这样自然由一个排列得到一个序列 (an-1,an-2,a2,a1),而且满足条件而且满足条件(2.1).第10页，共58页，编辑于2022年，星期一11l l我们可以如下建立序列与排列的对应我们可以如下建立序列与排列的对应:l设设序序列列(an-1,an-2,a2,a1)满满足足条条件件(2.1).则则它它所所对对应应的的排排列列为为(p)=p1p2pn,其其中中ai可可以以看看作作是是排排列列(p)中中数数i+1所所在在位位置置后后面面比比i+1小的数的个数小的数的个数.l要要说说明明这这种种对对应应的的合合理理性性,必必须须清清楚楚.如如何

8、由序列产生出它所对应的排列何由序列产生出它所对应的排列.l我们通过一个具体的例题说明思想方法我们通过一个具体的例题说明思想方法.第11页，共58页，编辑于2022年，星期一12例例2.1(1)4213(301)4后面比后面比4小的数的个数小的数的个数a3=3;3后面比后面比3小小的数的个数的数的个数a2=0;2后面比后面比2小的数的个数小的数的个数a1=1.(2)(301)4213 由由a3=3知知1,2,3都在都在4的后面的后面;由由a2=0知知1,2都在都在3前面前面;由由a1=1知知1在在2后面后面.(3)(4213)(a3a2a1)=(301).第12页，共58页，编辑于2022年，星

9、期一13l l利用序列得到相应排列是关键利用序列得到相应排列是关键,可以设想为可以设想为给给n个格子中填写个格子中填写1,2,n.如上面的例题如上面的例题:例例2.2 设集合设集合S=1,2,3,4,用序数法生成用序数法生成S的全部排列的全部排列.解解 用序数法用序数法,由各个序列对应生成的排列由各个序列对应生成的排列,如表如表2.1所示所示.4213第13页，共58页，编辑于2022年，星期一14N Na a3 3a a2 2a a1 1p p1 1p p2 2p p3 3p p4 4N Na a3 3a a2 2a a1 1p p1 1p p2 2p p3 3p p4 40 01 12 2

10、3 34 45 56 67 78 89 9101011110000000010010100100110110200200210211001001011011101101111111201201211211234123421342134132413242314231431243124321432141243124321432143134213422341234131423142324132411212131314141515161617171818191920202121222223232002002012012102102112112202202212213003003013013103103

11、11311320320321321142314232413241314321432243124313412341234213421412341234213421341324132423142314312431243214321第14页，共58页，编辑于2022年，星期一15l比如其中的序列比如其中的序列(221)所对应的排列所对应的排列:先由先由a3=2决定决定4的位置的位置l l满足条件满足条件(2.1)的的n!个序列很容易产生的个序列很容易产生的,利用这些序列就可以得到全体利用这些序列就可以得到全体n阶排列阶排列.l l这种利用序列产生排列的方法就是所谓这种利用序列产生排列的方法就是所谓的

12、的序数法序数法.4再由再由a2=2决定决定3的位置的位置321再由再由a1=1决定决定2的位置的位置第15页，共58页，编辑于2022年，星期一16 例例 字符集字符集1,2,3,1,2,3,较小的数字较先较小的数字较先,这样按字典序生成的全排列是这样按字典序生成的全排列是:123,132,213,231,312,321123,132,213,231,312,321。2.字典序法字典序法 对给定的字符集中的字符规定了对给定的字符集中的字符规定了一个先后关系，在此基础上规定两一个先后关系，在此基础上规定两个全排列的先后是从左到右逐个比个全排列的先后是从左到右逐个比较对应的字符的先后。较对应的字符

13、的先后。第16页，共58页，编辑于2022年，星期一172.字典序法字典序法l l字典序法就是按照字典排序的思想逐一产字典序法就是按照字典排序的思想逐一产生所有排列生所有排列.l l设想要得到由设想要得到由1,2,3,4以各种可能次序产生出以各种可能次序产生出4!个个“单词单词”.肯定先排肯定先排1234,再排再排1243,下下来是来是1324,1342,.,4321.l分析这种过程分析这种过程,看如何由一个排列得到看如何由一个排列得到下一个排列下一个排列,并给出严格的数学描述并给出严格的数学描述.第17页，共58页，编辑于2022年，星期一18例例2.3 设有排列设有排列(p)=276354

14、1,按照字典式排按照字典式排序序,它的下一个排列是谁它的下一个排列是谁?(q)=2764135.(1)2763541 找最后一个找最后一个正序正序35(2)2763541 找找3后面比后面比3大的最后一个数大的最后一个数(3)2764531 交换交换3,4的位置的位置(4)2764135 把把4后面的后面的531反序排列为反序排列为 135即得到最后的排列即得到最后的排列(q)第18页，共58页，编辑于2022年，星期一19l求求(p)=p1pi-1pipn的下一个排列的下一个排列(q):(1)求求 i=max j pj-1 pj (找找最后一个正序最后一个正序)(2)求求 j=max k p

15、i-1 pk(找找最后大于最后大于pi-1者者)(3)互换互换pi-1与与pj得得 p1pi-2 pj pipi+1pj-1 pi-1 pj+1pn(4)反排反排pj后面的数得到后面的数得到(q):p1pi-2 pj pnpj+1pi-1pj-1.pi+1 pi第19页，共58页，编辑于2022年，星期一20例例2.4 设设S=1,2,3,4,用字典序法求出用字典序法求出S的全的全部排列部排列.解解 1234,1243,1324,1342,1423,1432,2134,2143,2314,2341,2413,2431,3124,3142,3214,3241,3412,3421,4123,413

16、2,4213,4231,4312,4321.思考题思考题:是否可定义一种序列是否可定义一种序列,并定义序列之间的并定义序列之间的一种序关系一种序关系,使得可按照序列产生出字典式序排使得可按照序列产生出字典式序排列所有列所有n阶排列阶排列.第20页，共58页，编辑于2022年，星期一213.邻位互换法邻位互换法l l邻位互换生成算法的思想是很自然的一种邻位互换生成算法的思想是很自然的一种想法想法,其中蕴涵递归的思想其中蕴涵递归的思想.l l是由是由Johnson-Trotter首先提出的首先提出的.l通过把通过把n插入到插入到n-1阶排列的不同位置得到阶排列的不同位置得到n阶排列阶排列:n=1:

17、1 n=2:12,21.n=3:123,132,312;321,231,213.第21页，共58页，编辑于2022年，星期一22n=4:1234,1243,1423,4123 4132,1432,1342,1324 3124,3142,3412,4312 4321,3421,3241,3214 2314,2341,2431,4231 4213,2413,2143,2134第22页，共58页，编辑于2022年，星期一23l l用这种方法可以产生出任意用这种方法可以产生出任意n阶排列阶排列.l为了产生为了产生n阶排列阶排列,我们必须知道所有我们必须知道所有n-1阶排列阶排列.l如果考虑算法如果考虑

18、算法,必须存储所有必须存储所有n-1阶排列阶排列,然后才能产生出所有然后才能产生出所有n阶排列阶排列.这是一个很这是一个很大的缺点大的缺点.l分析过程分析过程,找到规律找到规律,直接找到通过邻位直接找到通过邻位交换来产生的下一个排列方式交换来产生的下一个排列方式.第23页，共58页，编辑于2022年，星期一24l从初始排列从初始排列1234开始开始,在每个数上方加在每个数上方加一个箭头一个箭头“”,如如 l当一个数上方箭头所指的一侧当一个数上方箭头所指的一侧,相邻的数相邻的数比这个数小的时候比这个数小的时候,称这个数处于活动状称这个数处于活动状态态.在在 中数中数2,3,4都处于活动都处于活动

19、状态状态.第24页，共58页，编辑于2022年，星期一25中中6 6、3 3、5 5都是处于活动状态都是处于活动状态.显然显然1 1永永远不是活动的，远不是活动的，n除了以下两种情形外，除了以下两种情形外，它都是它都是处于活动状态处于活动状态的的:(1):(1)n是第一个是第一个数，且其方向指向左侧；数，且其方向指向左侧；(2)(2)n是最后一个数，且其方向指向右是最后一个数，且其方向指向右侧。侧。l l利用这个概念可以把上面的生成利用这个概念可以把上面的生成排列的方法叙述的比较清楚排列的方法叙述的比较清楚.第25页，共58页，编辑于2022年，星期一26l l 设有排列设有排列(p)=p1p

20、2pn.Step 1.若排列若排列(p)=p1p2pn中没有处于活中没有处于活动状态的数动状态的数,则停止则停止.Step2.若排列若排列(p)=p1p2pn中有处于活动状中有处于活动状态的数态的数,则设则设m是处于活动状态数中的最大是处于活动状态数中的最大者者.把把m与它箭头方向所指的相邻数互换与它箭头方向所指的相邻数互换位置位置.Step 3.改变所有比改变所有比m大的数上方的箭头大的数上方的箭头;然然后转向后转向Step 1.第26页，共58页，编辑于2022年，星期一27 1 2 3 1 2 3 1 2 3 1 2 3 1 3 2 1 3 2 1 3 2 1 3 2 3 1 2 3 1

21、 2 3 1 2 3 1 2 3 2 1 3 2 1 3 2 1 3 2 1 2 3 1 2 3 1 2 3 1 2 3 1 2 1 3 2 1 3 2 1 3 2 1 3444444444444444444444444第27页，共58页，编辑于2022年，星期一284.轮转法轮转法l l轮转法是我国数学家于轮转法是我国数学家于1996年提出的年提出的.该该算法的求解过程如下：算法的求解过程如下：l给定给定n个不同元素个不同元素N1,N2,Nn-1,Nn,将将N1N2Nn-1Nn叫做叫做基准排列基准排列.(1)(1)先逐步生成以先逐步生成以N1打头的所有排列打头的所有排列(a)先生成以先生成以

22、N1N2Nn-2 打头的所有排列打头的所有排列 N1N2Nn-2 Nn-1Nn,N1N2Nn-2Nn Nn-1第28页，共58页，编辑于2022年，星期一29(b)再生成以再生成以N1N2Nn-3打头的排列打头的排列.在在(a)中生成的两个排列均在其内中生成的两个排列均在其内,并对并对它们中的每一排列它们中的每一排列,使使N1N2Nn-3不动不动,对其后继元素从左向右按顺时针方向对其后继元素从左向右按顺时针方向轮转两次轮转两次,每轮转一次便生成一个新排每轮转一次便生成一个新排列列,由此共生成四个新排列由此共生成四个新排列,连同连同(a)中中的两个排列共六个排列的两个排列共六个排列:第29页，共

23、58页，编辑于2022年，星期一30N1N2Nn-3 Nn-2Nn-1NnN1N2Nn-3 Nn-1NnNn-2N1N2Nn-3 NnNn-2Nn-1N1N2 Nn-3 Nn-2Nn Nn-1N1N2 Nn-3 Nn Nn-1Nn-2N1N2 Nn-3 Nn-1Nn-2 Nn第30页，共58页，编辑于2022年，星期一31(c)生成以生成以N1N2 Nn-4打头的所有排列：打头的所有排列：在在(b)中中生生成成的的排排列列均均在在其其内内,并并对对其其中中每每一一排排列列,保保持持N1N2 Nn-4不不动动,使使其其后后继继元元素素从从左左向向右右按按顺顺时时针针方方向向轮轮转转n-(n-3)

24、=3次次,每每轮轮转转一一次次便便生生成成一一个个新新排排列列,共共生生成成18个个新新排排列列,连连同同(b)中中的的6个个排排列列共共24个排列个排列.省略省略第31页，共58页，编辑于2022年，星期一32 (d)按照上述方法按照上述方法,依次分别生成以依次分别生成以 N1N2 N5,N1N2 N4,N1N2,N1 打头的所有排列为止打头的所有排列为止.(2)生成以生成以N2打头的所有排列打头的所有排列 (a)先将先将基准排列基准排列N1N2Nn-1Nn从左向从左向 右依顺时针方向轮转一次右依顺时针方向轮转一次,生成排列生成排列 N2Nn-1Nn N1 (b)然后按然后按(1)的方法和步

25、骤生成以的方法和步骤生成以N2打打 头的所有排列头的所有排列.第32页，共58页，编辑于2022年，星期一33(3)生成以生成以N3打头的所有排列打头的所有排列(a)先将基准排列先将基准排列基准排列基准排列N1N2Nn-1Nn从左从左向右依顺时针方向轮转两次向右依顺时针方向轮转两次,生成以下排列生成以下排列N3Nn-1Nn N1 N2(b)然后按然后按(1)的方法和步骤生成以的方法和步骤生成以N3打头的所打头的所有排列有排列.(4)依次类推依次类推,按同样方法依次生成以按同样方法依次生成以N4,N5,Nn-1,Nn打头的所有排列打头的所有排列.到此整个算法结束到此整个算法结束.第33页，共58

26、页，编辑于2022年，星期一34二二.组合生成算法组合生成算法l l组合的生成要比排列容易组合的生成要比排列容易.我们将给出组我们将给出组合生成的标准算法合生成的标准算法.l先观察从先观察从1,2,6中任意取中任意取3个数的组合个数的组合.0101123123 0202124124 0303125125 0404126126 05051341340606135135 0707136136 0808145145 0909146146 10101561561111234234 1212235235 1313236236 1414245245 15152462461616256256 1717345

27、345 1818346346 1919356356 2020456456第34页，共58页，编辑于2022年，星期一35l上述的组合等于按照字典序排列好了上述的组合等于按照字典序排列好了.l l 每个组合每个组合c1c2c3满足条件满足条件1 c1 c2 c3 6.l c3最最大大可可以以到到6,c2最最大大可可以以到到5,c1最最大大可可以到以到4.l如如果果每每个个数数都都已已经经达达到到最最大大,那那就就结结束束了了.如如果果没没有有,就就找找最最右右面面一一个个还还没没有有达达到到最最大大值值的的数数,给给这这个个数数依依次次分分别别加加1,2,r-j+1得得到到下下一一个个组组合合.

28、重重复复这这个个过过程就可以得到整个组合程就可以得到整个组合.第35页，共58页，编辑于2022年，星期一36l l设要按字典序决定集合设要按字典序决定集合S=1,2,n 的全的全体体r组合组合.设设S的一个的一个r组合为组合为a1,a2,ar,且且1 a1 a2 ar n.若若a1,a2,ar等于等于n-r+1,n-r+2,n,则则它已经是最后一个组合它已经是最后一个组合.若若a1,a2,ar不等于不等于n-r+1,n-r+2,n,设设i是使是使ajn-r+j的最大整数的最大整数.则按字典序紧跟则按字典序紧跟a1,a2,ar的的r组合是组合是 a1,ai-1,ai+1,ai+2,ai+(r-

29、i+1)第36页，共58页，编辑于2022年，星期一37l由这个原理由这个原理,从一个组合从一个组合a1,a2,ar到下到下一个组合的算法可以描述如下一个组合的算法可以描述如下:S1.求使求使ajn-r+j的最大下标的最大下标i.即即 i=maxj|ajn-r+j S2.ai ai+1 S3.aj aj-1+1,j=i+1,i+2,r.第37页，共58页，编辑于2022年，星期一38例例2.6 试生成试生成S=1,2,3,4,5,6,7 的的5组合组合.解解 可以利用上面的算法来生成可以利用上面的算法来生成:12345,12346,12347,12356,12357,12367,12456,1

30、2457,12467,12567,13456,13457,13467,13567,14567,23456,23457,23467,23567,24567,34567 其组合数其组合数C=(7,5)=21.第38页，共58页，编辑于2022年，星期一39允许重复的排列允许重复的排列-多重集的排列多重集的排列多重集多重集元素可以多次出现的集合，即元元素可以多次出现的集合，即元素可以重复。我们把某个元素素可以重复。我们把某个元素ai出现的次数出现的次数ni(ni=0,1,2,=0,1,2,)叫做该元素的重复数，叫做该元素的重复数，通常把含有通常把含有k种不同元素的多重集种不同元素的多重集S S记作记

31、作第39页，共58页，编辑于2022年，星期一40 可重排列可重排列定义定义 从一个多重集从一个多重集中有序选取的中有序选取的r个元素叫做个元素叫做S S的一个的一个r r-(可重可重)排列。当排列。当时也叫做时也叫做S S的一个排列的一个排列.第40页，共58页，编辑于2022年，星期一41定理 设多重集则的r-(可重)排列数是rk第41页，共58页，编辑于2022年，星期一42例例 求4位数的二进制数的个数解：所求的标志数是多重集2红旗，3黄旗的排列数，故N=5!/(2!*3!)=10例例 用两面红旗，三面黄旗依次悬挂在一根旗杆上，问可以组成多少种不同的标志？第42页，共58页，编辑于20

32、22年，星期一43允许重复的组合允许重复的组合-可重组合可重组合允许重复允许重复(可重可重)的组合是指从的组合是指从 中取中取r个元素个元素 ,允许重复，即允许允许重复，即允许 的数同时出现的数同时出现于一个组合中的组合于一个组合中的组合,其全体记为其全体记为C(n,r),其其个数记为个数记为C(n,r)定理定理1.2 1.2 从从 中取中取r个作可个作可重的组合，其个数为重的组合，其个数为C(n+r-1,r)第43页，共58页，编辑于2022年，星期一44定理定理1.2证明证明C(n,r)的计数问题相当于的计数问题相当于r相同的球放入相同的球放入n个互异的盒子，每个盒子中球数不加限个互异的盒

33、子，每个盒子中球数不加限制的方案的计数。而后一问题又可转换制的方案的计数。而后一问题又可转换为为r个相同的球与个相同的球与n-1个相同的盒壁的排个相同的盒壁的排列的问题。列的问题。易知所求计数为易知所求计数为 =C(n+r-1,r)(n-1+r)!r!(n-1)!r个相同的球 /001001100 /n-1个相同的盒壁第44页，共58页，编辑于2022年，星期一45 设设a1 1a2 2ar rC(n,r)1 a1 1 a2 2 ai i ar r n,与下面的数列对应相加与下面的数列对应相加012i-1r-1 即即bi i=ai i+i-1,i=1,2,r.则则b1 1b2 2br r满足满

34、足1 b1 1b2 2br rn+r-1n+r-1 b1 1b2 2br rC(n+r-1,r)f：a1 1a2 2ar rb1 1b2 2br r显然显然f是双射是双射所以所以 C(n,r)=C(n+r-1,r)-1定理定理1.2证明证明第45页，共58页，编辑于2022年，星期一461.8.2不相邻的组合不相邻的组合 不不相邻的组合是指从序列相邻的组合是指从序列1,2,1,2,n 中取中取r个，不允许重复且不存在个，不允许重复且不存在i,i+1+1两个相邻的两个相邻的数同时出现于一个组合中的组合数同时出现于一个组合中的组合定理定理1.41.4 从从A=1,2,=1,2,n 中取中取r个作不

35、相邻的个作不相邻的组合，其个数为组合，其个数为C(n-r+1,r)第46页，共58页，编辑于2022年，星期一47任给任给任给任给a a1 1a a2 2a ar rC(n,r),C(n,r),a a1 1 a a2 2 a ar r n n且且且且 a ai i+1+1-a ai i2,2,i i=1,2,=1,2,r r-1-1 与下面的数列对应相减与下面的数列对应相减与下面的数列对应相减与下面的数列对应相减 012i-1r-1012i-1r-1 得得得得1 1 b b1 1 b b2 2 b br r n n-r r+1+1，其中，其中，其中，其中 b bi i=a ai i-i i+1

36、,+1,i i=1,2,=1,2,r br bi i+1+1-b bi i11.b b1 1b b2 2b br rC(n-r+1,r)C(n-r+1,r)令令令令f f：a a1 1a a2 2a ar rb b1 1b b2 2b br rC(n,r)=C(n-r+1,r)C(n,r)=C(n-r+1,r)定理定理1.4的证明的证明第47页，共58页，编辑于2022年，星期一48组合恒等式组合恒等式 如图，求从如图，求从(0,0)点到点到(m,n)点、沿格子线走点、沿格子线走的最短路径数的最短路径数N。一条到达点一条到达点(m,n)的路径对应的路径对应一个由一个由m个个x，n个个y组成的排

37、列组成的排列x x x y y x y x x y y x x y y x x x y第48页，共58页，编辑于2022年，星期一49四四.若干组合等式若干组合等式(1)C(n,r)=C(n,n-r)(2)C(n,k)=C(n-1,k)+C(n-1,k-1)证明证明1：从从1,2,n中取中取k个组合的全体可个组合的全体可以分为两组：以分为两组：A1组：含有元素组：含有元素n，|A1|=C(n-1,k-1)A2组：不含元素组：不含元素n，|A2|=C(n-1,k)第49页，共58页，编辑于2022年，星期一50(2)C(n,k)=C(n-1,k)+C(n-1,k-1)证明证明2：考虑如图棋盘：考

38、虑如图棋盘从从(0,0)到到(k,n-k)的最短的最短路条数为路条数为C(n,k)，其中，其中经过经过P1点的有点的有C(n-1,k),经过经过P2点的有点的有C(n-1,k-1)。第50页，共58页，编辑于2022年，星期一51四四.若干组合等式若干组合等式(2)C(n,r)=C(n-1,r)+C(n-1,r-1)(3)C(n+r+1,r)=C(n+r,r)+C(n+r-1,r-1)+C(n+r-2,r-2)+C(n+1,1)+C(n,0).证明证明1：由（：由（2）可得。）可得。第51页，共58页，编辑于2022年，星期一52(3)(3)C(n+r+1,r)=C(n+r,r)+C(n+r-

39、1,r-1)+C(n+r+1,r)=C(n+r,r)+C(n+r-1,r-1)+C(n+r-2,r-2)+C(n+1,1)+C(n,0).C(n+r-2,r-2)+C(n+1,1)+C(n,0).证明证明证明证明2 2：从：从：从：从1,2,1,2,n+r+n+r+11中取中取中取中取r r个组合的全体可以分为个组合的全体可以分为个组合的全体可以分为个组合的全体可以分为r r+1+1组：组：组：组：A A1 1：不含：不含：不含：不含1 1，|A|A1 1|=C(|=C(n n+r r,r r)A A2 2：含：含：含：含1 1但不含但不含但不含但不含2 2，|A|A2 2|=C(|=C(n

40、n+r r-2,-2,r r-1)-1)A A3 3：含：含：含：含1,21,2，但不含，但不含，但不含，但不含3 3，|A|A3 3|=C(|=C(n n+r r-3,-3,r r-2)-2)A Ar r：含：含：含：含1,2,1,2,r r-1-1，但不含，但不含，但不含，但不含r r，|A|Ar r|=C(n+1,1)|=C(n+1,1)A Ar r+1+1：由：由：由：由1212r r组成的组合，组成的组合，组成的组合，组成的组合，|A|Ar r+1+1|=C(|=C(n n,0),0)第52页，共58页，编辑于2022年，星期一53(4)(4)C(n,k)C(k,r)=C(n,r)C

41、(n-r,k-r),(k C(n,k)C(k,r)=C(n,r)C(n-r,k-r),(k r).r).证明：考虑如下问题，把证明：考虑如下问题，把证明：考虑如下问题，把证明：考虑如下问题，把N Nn n=1,2,=1,2,n n 分为甲、乙、丙三分为甲、乙、丙三分为甲、乙、丙三分为甲、乙、丙三组，使得甲组恰有组，使得甲组恰有组，使得甲组恰有组，使得甲组恰有r r个，乙组恰有个，乙组恰有个，乙组恰有个，乙组恰有k k-r r个，丙组恰有个，丙组恰有个，丙组恰有个，丙组恰有n n-k k个，其分法种数可以用两种方法计算。个，其分法种数可以用两种方法计算。个，其分法种数可以用两种方法计算。个，其分

42、法种数可以用两种方法计算。方法方法方法方法1 1：从：从：从：从N Nn n中取中取中取中取k k个，余下的个，余下的个，余下的个，余下的n n-k k个放在丙组；再从取出个放在丙组；再从取出个放在丙组；再从取出个放在丙组；再从取出的的的的k k个中拨出个中拨出个中拨出个中拨出r r个分在甲组，余下的个分在甲组，余下的个分在甲组，余下的个分在甲组，余下的k k-r r个分在乙组，分个分在乙组，分个分在乙组，分个分在乙组，分法种数有法种数有法种数有法种数有C(n,k)C(k,r)C(n,k)C(k,r)。方法方法方法方法2 2：从：从：从：从N Nn n中取中取中取中取r r个分在甲组，再从余下

43、的个分在甲组，再从余下的个分在甲组，再从余下的个分在甲组，再从余下的n n-r r个中取出个中取出个中取出个中取出k k-r r个分在乙组，最后剩下的个分在乙组，最后剩下的个分在乙组，最后剩下的个分在乙组，最后剩下的n n-k k个分在丙组，分法种数个分在丙组，分法种数个分在丙组，分法种数个分在丙组，分法种数有有有有C(n,r)C(n-r,k-r)C(n,r)C(n-r,k-r)。第53页，共58页，编辑于2022年，星期一54(5)C(m,0)+C(m,1)+C(m,m)=2m.(x+y)m=xm+C(m,1)xm-1y+C(m,2)xm-2y2+ym(6)C(n,0)-C(n,1)+C(n

44、,2)-C(n,n)=0.(7)C(m+n,r)=C(m,0)C(n,r)+C(m,1)C(n,r-1)+C(m,r)C(n,0),r min(m,n).(8)C(m+n,m)=C(m,0)C(n,0)+C(m,1)C(n,1)+C(m,m)C(n,m),m n.第54页，共58页，编辑于2022年，星期一55扑克问题扑克问题 每张扑克牌都有两种标志，一种是花色每张扑克牌都有两种标志，一种是花色 ，另一种标志是数值，另一种标志是数值 2,3,4,5,6,7,8,9,10,J,Q,K,A共共52张。张。(1)从从52张扑克牌中取出张扑克牌中取出5张，使其中两张的值张，使其中两张的值相同，另外相同

45、，另外3张的值也相同，有多少种方案张的值也相同，有多少种方案？(2)取出取出5张扑克牌，出现两对同值的方案数张扑克牌，出现两对同值的方案数是多少？是多少？第55页，共58页，编辑于2022年，星期一56五五.Stirling近似公式近似公式l l在组合数学中经常遇到在组合数学中经常遇到n!计算计算,随着随着n的增的增大大,结果增长迅速结果增长迅速.Stirling公式给出一个公式给出一个求求n!的近似公式的近似公式,它对从事计算和理论分它对从事计算和理论分析都是有意义的析都是有意义的.l Stirling公式公式:第56页，共58页，编辑于2022年，星期一57l l 绝对误差：绝对误差：l 相对误差：相对误差：第57页，共58页，编辑于2022年，星期一58六六.课后学习任务课后学习任务l完成第一章的学习完成第一章的学习l l预习第二章预习第二章1-3l作业作业2版版:8,12,26,28l l3版：版：16，36，48，50l练习题练习题:19,20（III:41，42).第58页，共58页，编辑于2022年，星期一