组合数学复习课.ppt
《组合数学复习课.ppt》由会员分享,可在线阅读,更多相关《组合数学复习课.ppt(35页珍藏版)》请在三一文库上搜索。
1、组合数学,http:/ Mathematics),Contents,例 在100名选手之间进行淘汰赛(即一场的比赛结果,失败者退出比赛),最后产生一名冠军,问要举行几场比赛? 解 一种常见的思路是按轮计场,费事。 各轮场数502512632199 剩余选手数目:25, 13, 7, 4, 2, 1 另一种思路是淘汰的选手与比赛(按场计)集一一对应。99场比赛。,全排列的生成算法 1序数法,由序数2,0,1 ,求十进制m13 m=23!02!11!13 由十进制m13,求序数2,0,1,序数 n!个,对应n元的n!个序列。 规则(序列序数):序列(p)= 是(p)中数字i+1后面比i+1小的数的
2、个数 如 (p)=(4213) 对应 =(301) n4 (p)=(3412) 对应 =(220) 规则(序数序列): 如其中的序列(220)所对应的排列: 先由 =2决定4的位置 x4xx 再由 =2决定3的位置 34xx 再由 =0决定2的位置 34x2 则 3412,2字典序法,例 设有排列(p) =2763541, 按照字典式排序, 它的下一个排列是谁? (q) =2764135. (1) 2763541 找最后一个正序35 (2) 2763541 找3后面比3大的最后一个数4 (3) 2764531 交换3,4的位置 (4) 2764135 把4后面的531反序排列为135 即得到最
3、后的排列(q),例 求839647521的下一个排列 找出比右边数字小的第一个数4 在后缀7521中找出比4大的最小数 5 4 ,5 对换成为 839657421 将此后缀7421翻转成为 1247 接上前缀83965得到839651247 即839647521的下一个。,3邻位对换法,活动数是箭头所指相邻数比自己小的数。 对换规则: 活动数中最大的数m,交换箭头所指相邻数。 同时,比m大的数,改变方向。,4 组合的生成,设1,2,3,4,5,6中取3个的组合,20个, 按照字典序排列。 123,124,125,126,134, 135,136,145,146,156, 234,235,236
4、,245,246, 256,345,346,356,456。 第1位1到4,第2位2到5,第3位3到6。,每个组合C1C2C3满足条件1C1 C2 C36. C3最大可以到6, C2最大可以到5, C1最大可以到4. 如果每个数都已经达到最大, 那就结束了. 如果没有, 就找最右边一个还没有达到最大值的数, 给这个数加1,(并依次写出后续各数),得到下一个组合. 重复这个过程就可以得到整个组合.,如256,345,346,356,456。 256中,5和6到最大。 2加1为3,后接4,5等。为345。 如156,234,235,236,245, 156中,5和6到最大。 1加1为2,后接3,4
5、等。为234。 236中,6到最大。 3加1为4,后接5等。为245。,组合意义的解释,例 选政治局,再选常委,n个中央委员选出l名政治局委员,再从其中选出r名常委 选常委,再选非常委政治局委员 两种选法都无遗漏,无重复地给出可能的方案,应该相等。,线性常系数齐次递推关系,(1)若特征多项式 有n个不同零点 则递推关系的解,其中 是待定系数,有初始条件 来确定。,(2)若特征多项式 有不同的复根,可依照(1)的办法处理。不过任意复数 可写为 形式,设 是 的一个零点,其共轭复根为,和 仍然是待定常数。即 有一对共轭复根 和 时,递推关系的解有对应的项,其中A,B是待定常数。,(3)若 k重根。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 组合 数学 复习
链接地址:https://www.31doc.com/p-2754108.html