收藏 分销(赏)

组合数学复习课.ppt

上传人:精**** 文档编号:14501625 上传时间:2026-10-01 格式:PPT 页数:36 大小:704.04KB 下载积分:10 金币
下载 相关
组合数学复习课.ppt_第1页
第1页 / 共36页
组合数学复习课.ppt_第2页
第2页 / 共36页


点击查看更多>>
资源描述
,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,Click to edit Master title style,*,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,Click to edit Master title style,*,上一页,下一页,返 回,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,上一页,下一页,返 回,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,组合数学,iask.sina/u/1048683155/ish,(Combinatorial Mathematics),Contents,第一章 排列与组合,1,第二章 递推关系与母函数,2,第三章 容斥原理与鸽巢原理,3,复习课,4,例 在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小的数的个数,如(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,即得到最后的排列(q),规则(序数序列):,因此小于n且与n互素的正整数的个数为:,其中 是待定系数,有初始条件,但如果加上条件 呢?,(x1+6)+x2+x3=15,其中b(n)是n的p次多项式,r是特征方程,关于线性常系数非齐次递推关系,如(p)=(4213)对应 =(301)n4,(1)若有某个ri=0,则命题已成立。,2加1为3,后接4,5等。,(3)2764531 交换3,4的位置,1加1为2,后接3,4等。,同时修数学、化学的20人;,例 求839647521的下一个排列,如果每个数都已经达到最大,那就结束了.,令A、B、C分别为修数学、物理、化学的学生集合。,|A3|=C(7+3-1,8)=C(9,2)。,令Ai(i=1,2,k)分别表示1到n这n个整数中pi的倍数组成的集合。,例 求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,,,145,146,156,,234,235,236,245,246,,256,345,346,356,456。,第1位1到4,第2位2到5,第3位3到6。,每个组合C1C2C3满足条件1C1 C25的整数解,A2为其中x26的整数解,A3为其中x37的整数解。,那么|U|=C(17,2)。A1相当于求线性方程,(x1+6)+x2+x3=15,类似有:|A2|=C(8+3-1,8)=C(10,2),,但如果加上条件 呢?,的非负整数解,其个数为|A1|=C(9+3-1,9)=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)。,因此方程满足条件 的非负整数解数目为:,的非负整数解,|A1A2|=C(2+3-1,2)=C(4,2)。,A1A2A3相当于求线性方程,(x1+6)+(x2+7)+(x3+8)=15,的非负整数解,|A1A2A3|=0。,例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的因数分解为:,其中p1,pk是互不相同的素数。,其他的都可以依此类推。,因此小于n且与n互素的正整数的个数为:,例如60=2235,所以,即比60小且与60互素的数有16个:1,7,11,13,17,19,23,29,31,37,41,43,47,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,,故命题成立。,Thank You!,iask.sina/u/1048683155/ish,谢谢观看,
展开阅读全文

开通  VIP、SVIP  下载更划算
下载10份以上建议开通 VIP 会员
下载20份以上建议开通SVIP会员


开通VIP      成为共赢上传

当前位置:首页 > 教育专区 > 其他

移动网页_全站_页脚广告1

关于我们      便捷服务       自信AI       AI导航        关注我们

©2010-2026 宁波自信网络信息技术有限公司  版权所有

客服电话:0574-28810668  投诉电话:18658249818

gongan.png浙公网安备33021202000488号   

icp.png浙ICP备2021020529号-1  |  浙B2-20240490  

关注我们 :微信公众号    抖音    微博    LOFTER 

客服