组合数学复习课.ppt

《组合数学复习课.ppt》由会员分享，可在线阅读，更多相关《组合数学复习课.ppt（35页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、组合数学复习课 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life, there is hope。有生命必有希望。有生命必有希望Contents第一章第一章 排列与组合排列与组合1第二章第二章 递推关系与母函数递推关系与母函数2第三章第三章 容斥原理与鸽巢原理容斥原理与鸽巢原理3复习课复习课4上一页上一页下一页下一页返返 回回z例例 在100名选手之间进行淘汰赛(即一场的比赛结果，失败者退出比赛),最后产生一名冠军，问要举行几场比赛？z解解 一种常见的思路是按轮计场，费事。z各轮场数502512632199z剩余选手数目:25

2、, 13, 7, 4, 2, 1z另一种思路是淘汰的选手与比赛(按场计)集一一对应。99场比赛。上一页上一页下一页下一页返返 回回全排列的生成算法1序数法, 110, 200, 32023013! 11! 20! 32201! 11! 22! 331! 499990105101100108801510910910910911015092120202110012121212112123012301234012301234aaa如新进制如十进制如二进制上一页上一页下一页下一页返返 回回由序数2，0，1 ，求十进制m13 m=23！02！11！13由十进制m13，求序数2，0，1) 1 , 0 ,

3、2(),(2, 0424340,! 3! 32363231,! 2! 2! 2! 36213212),(! 1! 2! 3131123323123123123aaaannaannaaannaaaaaan序数余数余数余数序数上一页上一页下一页下一页返返 回回序数 n!个，对应n元的n!个序列。规则(序列序数)：序列(p)= 是(p)中数字i+1后面比i+1小的数的个数 如 (p)=(4213) 对应 =(301) n4 (p)=(3412) 对应 =(220)规则(序数序列)： 如其中的序列(220)所对应的排列: 先由 =2决定4的位置 x4xx 再由 =2决定3的位置 34xx 再由 =0决

4、定2的位置 34x2 则 3412),(21nppp),(121aaan),(123aaa),(123aaa1aia3a2a上一页上一页下一页下一页返返 回回2字典序法3544 3135上一页上一页下一页下一页返返 回回例 求839647521的下一个排列找出比右边数字小的第一个数4在后缀7521中找出比4大的最小数 54 ,5 对换成为 839657421将此后缀7421翻转成为 1247接上前缀83965得到839651247 即839647521的下一个。上一页上一页下一页下一页返返 回回3邻位对换法活动数是箭头所指相邻数比自己小的数。对换规则：活动数中最大的数m，交换箭头所指相邻数。同

5、时，比m大的数，改变方向。42312431234123143214324134214321mmmmmmmm上一页上一页下一页下一页返返 回回4 组合的生成z设1,2,3,4,5,6中取3个的组合，20个，z按照字典序排列。z123，124，125，126，134，z135，136，145，146，156，z234，235，236，245，246，z256，345，346，356，456。z 第1位1到4，第2位2到5，第3位3到6。上一页上一页下一页下一页返返 回回上一页上一页下一页下一页返返 回回z如256，345，346，356，456。z 256中，5和6到最大。z 2加1为3，后接4，

6、5等。为345。z如156，234，235，236，245，z 156中，5和6到最大。z 1加1为2，后接3，4等。为234。z 236中，6到最大。z 3加1为4，后接5等。为245。上一页上一页下一页下一页返返 回回组合意义的解释z例 z选政治局,再选常委,n个中央委员选出l名政治局委员,再从其中选出r名常委z选常委,再选非常委政治局委员z两种选法都无遗漏,无重复地给出可能的方案，应该相等。rlrnrnrlln上一页上一页下一页下一页返返 回回线性常系数齐次递推关系线性常系数齐次递推关系 (1)若特征多项式 有n个不同零点 则递推关系的解)(xC,11naaaknnkkkalalala2

7、211其中 是待定系数，有初始条件来确定。,11nlll上一页上一页下一页下一页返返 回回 (2)若特征多项式 有不同的复根，可依照(1)的办法处理。不过任意复数 可写为 形式，设 是 的一个零点，其共轭复根为)sin(cos1iei)(xCbia ie)(xC)sin(cos2iei上一页上一页下一页下一页返返 回回kllikllkiklkiklllkkkkkksin)(cos)( )sin(cos )sin(cos2121212211 和 仍然是待定常数。即 有一对共轭复根 和 时，递推关系的解有对应的项21ll )(21lli0)(xCie1ie2kBkAkksincos其中A，B是待定

8、常数。上一页上一页下一页下一页返返 回回 (3)若 k重根。不妨设 是k的重根。则递推关系(2-5-1)的解对应于的项为 其中 是k个待定常数。nkknAnAA11110)()(xC1110,kAAA上一页上一页下一页下一页返返 回回上一页上一页下一页下一页返返 回回关于线性常系数非齐次递推关系关于线性常系数非齐次递推关系 线性常系数齐次递推关系解决得比较彻底，而非齐次的只限于某些特殊情况：1122,nnnnkn knac ac ac ab s 其中s是一参数，对应的齐次递推关系为 (1)假定所讨论的非齐次递推关系为11220,nnnkn kac ac ac a 若序列011,nn 0和是非齐

9、次递推关系的解，则序列00111,nnnaaa0是齐次递推关系的解。上一页上一页下一页下一页返返 回回上一页上一页下一页下一页返返 回回例3120165 4 ,5,3.nnnnaaaaa4nnc 以代入非齐次递推关系12446 45 4 ,nnnnccc 222, (446)5 4 ,4040,4 .33nnncc 有所以上一页上一页下一页下一页返返 回回令 则,nnnna 满足齐次递推关系1260,nnn特征方程212126(3)(2)0,3( 2)403( 2)43nnnnnnnxxxxkkakk上一页上一页下一页下一页返返 回回由初始条件011211225,3,4067535160763

10、233156776403( 2)45153nnnnaakkkkkka 上一页上一页下一页下一页返返 回回关于线性常系数非齐次递推关系关于线性常系数非齐次递推关系1122( ),nnnnkn kac ac ac ar b n 其中b(n)是n的p次多项式，r是特征方程 (2)若非齐次递推关系11( )0,kkkC xxc xc 的m重根,则特解的形式有101nmmmpprk nk nk n其中是待定常数，由非齐次递推关系确定。01,pk kk若r不是C(x)=0的根，则令m=0。上一页上一页下一页下一页返返 回回上一页上一页下一页下一页返返 回回例例 一个学校只有三门课程：数学、物理、化学。一个

11、学校只有三门课程：数学、物理、化学。已知修这三门课的学生分别有已知修这三门课的学生分别有170、130、120人；人；同时修数学、物理的学生同时修数学、物理的学生45人；同时修数学、化学人；同时修数学、化学的的20人；同时修物理、化学的人；同时修物理、化学的22人；同时修三门的人；同时修三门的3人。假设每个学生至少修一门课，问这学校共有人。假设每个学生至少修一门课，问这学校共有多少学生？多少学生？令令A、B、C分别为修数学、物理、化学的学生集合。分别为修数学、物理、化学的学生集合。 ABCABCABBCCAABC . 1701301204522203336即学校共有即学校共有336名学生。名学

12、生。上一页上一页下一页下一页返返 回回容斥原理的推广容斥原理的推广例例 一个学校只有三门课程：数学、物理、化学。一个学校只有三门课程：数学、物理、化学。已知修这三门课的学生分别有已知修这三门课的学生分别有170、130、120人；人；同时修数学、物理的学生同时修数学、物理的学生45人；同时修数学、化学人；同时修数学、化学的的20人；同时修物理、化学的人；同时修物理、化学的22人；同时修三门的人；同时修三门的3人。假设每个学生至少修一门课，问这学校共有人。假设每个学生至少修一门课，问这学校共有多少学生？多少学生？若把问题改为若把问题改为“单修一门数学的学生有多少？单修一门数学的学生有多少？” “

13、只修一门课的学生有多少？只修一门课的学生有多少？”“”“只修两门课的学只修两门课的学生有多少？生有多少？”呢？呢？仍然用仍然用A、B、C分别表示修数学、物理、化学的学分别表示修数学、物理、化学的学生的集合。生的集合。上一页上一页下一页下一页返返 回回单修一门数学的用单修一门数学的用ABC来表示，则有来表示，则有 ABCAABACABC类似有类似有 ABCBBABCABC ABCCCACBABC .ABCABCABCABCABACBCABC 23因此因此上一页上一页下一页下一页返返 回回例例 求方程求方程x1+x2+x3=15的非负整数解的数目。的非负整数解的数目。这个问题相当于这个问题相当于1

14、5个相同的球放入个相同的球放入3个不同的盒子的个不同的盒子的不同方案数，为不同方案数，为C(15+3-1,15)=C(17,2)。令令U为全体非负整数解，为全体非负整数解，A1为其中为其中x15的整数解，的整数解，A2为其中为其中x26的整数解，的整数解，A3为其中为其中x37的整数解。的整数解。则则|U|=C(17,2)。A1相当于求线性方程相当于求线性方程(x1+6)+x2+x3=15类似有：类似有：|A2|=C(8+3-1,8)=C(10,2)，但如果加上条件但如果加上条件 呢？呢？,xxx12305 06 07的非负整数解，其个数为的非负整数解，其个数为|A1|=C(9+3-1,9)=

15、C(11,2)。 |A3|=C(7+3-1,8)=C(9,2)。上一页上一页下一页下一页返返 回回A1A2相当于求线性方程相当于求线性方程(x1+6)+(x2+7)+x3=15类似有：类似有：|A1A3|=C(3,2)， |A2A3|=C(2,2)。因此方程满足条件因此方程满足条件 的的非负整数解数目为：非负整数解数目为：,xxx12305 06 07的非负整数解，的非负整数解，| A1A2 |=C(2+3-1,2)=C(4,2)。A1A2A3相当于求线性方程相当于求线性方程(x1+6)+(x2+7)+(x3+8)=15的非负整数解，的非负整数解，|A1A2A3 |=0。AAA123 CCCC

16、CCC (17,2)(11,2)(10,2)(9,2)(4,2)(3,2)(2,2)010.上一页上一页下一页下一页返返 回回例例1 欧拉函数欧拉函数 (n)，是指小于，是指小于n且与且与n互素的正整数的互素的正整数的个数个数。令令Ai (i=1,2,k)分别表示分别表示1到到n这这n个整数中个整数中pi的倍数的倍数组成的集合。组成的集合。则显然有则显然有|U|=n，|Ai|=n/pi。注意到所有的素数互不相同，所以注意到所有的素数互不相同，所以|AiAj|=n/(pi pj)。类似有：类似有：|AiAjAk|=n/(pi pj pk)。设设n的因数分解为：的因数分解为：,kaaaknppp

17、1212其中其中p1,pk是互不相同的素数。是互不相同的素数。其他的都可以依此类推。其他的都可以依此类推。上一页上一页下一页下一页返返 回回因此小于因此小于n且与且与n互素的正整数的个数为：互素的正整数的个数为：knAAA 12. ( ( ) )= =.knnnnppp 12.knppp 12111111()knnknnnp ppppp 12111例如例如60=2235，所以，所以n 60(11/ 2)(11/ 3)(11/ 5)16,( ( ) )= =即比即比60小且与小且与60互素的数有互素的数有16个：个： 1，7，11，13，17, 19, 23，29，31，37，41，43，47，

18、49，53，59。上一页上一页下一页下一页返返 回回例例4 在边长为在边长为1的等边三角形内任意取的等边三角形内任意取5个点，则至个点，则至少存在两个点，其距离不超过少存在两个点，其距离不超过1/2。等边三角形三边的中点把等边等边三角形三边的中点把等边三角形分成四个边长为三角形分成四个边长为1/2的等的等边三角形。边三角形。每个小等边三角形内的点之间每个小等边三角形内的点之间的距离不超过的距离不超过1/2。由鸽巢原理，任取由鸽巢原理，任取5个点中至少个点中至少有两个落入同一个小等边三角有两个落入同一个小等边三角形内，它们的距离不超过形内，它们的距离不超过1/2。上一页上一页下一页下一页返返 回回例例5 设设a1,a2,am是正整数序列，则至少存在是正整数序列，则至少存在一个一个k和和l，1kk，则，则Sl -Sk是是m的倍数。的倍数。根据根据Si的定义，的定义，但是共有但是共有m个个ri，根据鸽巢原理，至少有，根据鸽巢原理，至少有2个相同。个相同。Sl -Sk= ak+1+al，故命题成立。故命题成立。http:/