数学冬令营——组合计数.doc
《数学冬令营——组合计数.doc》由会员分享,可在线阅读,更多相关《数学冬令营——组合计数.doc(19页珍藏版)》请在咨信网上搜索。
1、组合计数一、基本知识1. 加法原理与乘法原理如果完成一件事情的方法可分成n个互不相交的类,且第一类中有种方法,第二类中有种方法,第n类中有种方法,那么完成这件事情一共有+种方法.这就是加法原理,简称为分类相加.如果完成一件事情要分n步,且第一步有种方法,第二步有种方法,第n步有种方法,那么完成这件事情一共有种方法.这就是乘法原理,简称为分步相乘.2. 无重复的排列与组合2.1 无重复的排列从n个不同的元素中,任取m(n)个不同元素,按照一定的顺序排成一列(或者从n个不同的元素中,有序地任取m(n)个不同元素),叫做从n个不同的元素中取出m个不同元素的一个排列.从n个不同的元素中取出m(n)个不
2、同元素的排列的个数,叫做从n个不同的元素中取出m个不同元素的排列数,用符号或表示.由乘法原理得=2.2无重复的组合从n个不同的元素中,任取m(n)个不同元素并成一组(或者从n个不同的元素中,无序地任取m(n)个不同元素),叫做从n个不同的元素中任取m个不同元素的组合.从n个不同的元素中取m(n)个不同元素的所有组合的个数,叫做从n个不同的元素中取m个不同元素的组合数,用符号表示,其计算公式为=事实上,对于每一个从n个不同的元素中任取m个不同元素的组合,将其元素作全排列可产生个不同的排列.显然不同的组合产生的排列互不相同,且每个排列都可以分2步得到.由乘法原理可得=,于是=.3. 可重复的排列与
3、组合3.1. 可重复的排列从n个不同的元素中,任取(允许重复)m(1)个元素,按照一定的顺序排成一列,叫做从n个不同的元素中取出m个元素的可重复排列.由乘法原理可得,从n个不同的元素中,取m(1)个元素的所有可重复排列个数为(选第1位元素有n种方法,选第2位元素也有n种方法,最后,选第m位元素也有n种方法).3.2. 有限个重复元素的全排列设n个元素由k个不同的元素,组成,其中有个,有个,有个(+=n),那么这n个元素的全排列称为有限个重复元素的全排列,其排列数为.事实上,若n个元素互不相同,则全排列为,但其中有个,它们之间任意交换顺序(共有种交换顺序的方法),得到的是同一排列(=1,2,k)
4、.故不同的排列个数为.3.3. 可重复的组合从个不同的元素中,任意可重复地选取(1)个元素,叫做从个不同的元素中取出个元素的可重复的组合,其不同组合的个数为.事实上,不妨设个元素为1,2,设取出的个元素为(1)(),显然(1)+0()将(,)与(+0,)建立一一对应,后者为从个不同元素1,2,中取个不同元素的组合,且不同的(,)对应的(+0,)是不同的反过来,从1,2,中任取个不同的数的组合(1)(1)也恰好对应于一个从个元素1,2,中取个可重复元素的组合(1)011()因此,上面所说的对应是一一对应,故所求组合数等于从1个不同的元素1,2,1中取个不同元素的组合数,即4圆排列与项链数从个不同
5、的元素中,取个不同元素排在一个圆周上,叫做从个不同的元素中取出个不同元素的圆周排列,其排列数为=.事实上,对每一个固定的个元素的圆排列,在任意两个元素之间将圆周剪开,沿顺时针方向拉直恰产生个直线排列,且不同的圆排列所产生的直线排列互不相同.又易见从个不同的元素取个不同元素的排列都可以这样从圆排列中得到,所以,所求圆排列数的倍恰好是从个不同的元素中取个不同元素的排列数,由此得出上述结论.将个不同的元素排成一个圆周的圆排列数为=.将粒不同的珍珠,用线串成一根项链的不同发数记为,则=(3),=1(=1或2).5容斥原理对于有限集合,我们用表示中元素的个数,若是的子集,则=表示在中的补集.定理1(容斥
6、原理)设是有限集合,是的子集,则|.()证明只要对任意,证明()式两边计算的次数是相同的即可.若不属于,中任何集合,则在()式左边计算了次,在()式右边第项中计算了次,而在()式右边其余各个和式项中计算的次数为,故在()式右边计算的总次数也为.若恰属于,中个集合,这里,则在()式左边计算的次数为,而在右边的第项,第项,第项,最后一项中计算的次数分别为,.在()式右边计算的总次数为综合上面的讨论,我们知道对任意,()式两边计算的次数(即对等式两边所作的贡献)相等.故()式成立.定理2(容斥原理的对偶形式)对任意有限集合,我们有=-+.二、基本方法与策略1. 枚举法所谓枚举法,就是把要计数的集合中
7、的元素逐一列举出来,不重复不遗漏,从而计算出中的元素的个数.在枚举的过程中,常常要适当地分类和分步枚举,这就要用到加法原理与乘法原理以及记数的基本公式.例1-1 方程+=3的非负整数解共有 组 (1985年全国高中联赛题)解 03且为非负整数,=0或1,下面分两种情形.(1)若=1,则必有某=1(210),其余=0(1,),这样的解有=9组.(2)若=0,则又分为三种情形.(i)有某一个=3(210),其余=0(1,),这样的解有=9组.(ii)有某一个=2(210),则必还有一个=1(1,),其余=0(1,),这样的解有=72组.(iii)所有2或3(210),则,中必有3个等于1,其余6个
8、等于0,这样的解有=84组.于是,原方程共有9+9+72+84=174组.例1-2 将一个四棱锥的每一个顶点染上一种颜色,并使同一棱的两端点异色,如果只有5种颜色可供使用,那么不同的染色方法总数是 . (1995年全国高中联赛题)解 依题意,四棱锥的顶点,互不同色,题目有=60种染色方法.当,的颜色染好后,不妨设其颜色分别为1色,2色,3色,则只可染2,4,5色中的一色.(1)若染2色,则可染3,4,5色中的一色,有=3种方法.(2)若染4色,则可染3,5色中的一色,有=2种方法.(3)若染5色,则可染2,4色中的一色,有=2种方法.故总的染色方法为60(3+2+2)=420种.2映射方法定义
9、 设是从集合到集合的映射.若对任意,当时有()(),则称为到的单射;若对任意的,存在,使得()=,则称为到的满射;若既是单射又是满射,则称为到的双射,又称为与之间的一一映射.定理1 对于两个有限集合与,若存在从到的单射,则|;若存在从到的满射,则|;若存在从到的双射,则|=|.当计算有限集合中的元素个数比较困难时,我们设法建立到另一个有限集合上的双射,如果中的元素个数|容易算出,于是由|=|,得出中的元素个数,这种计数方法称为映射方法,或者称为配对法.例2-1 设凸边形的任意3条对角线不相交于形内一点,求它的对角线在形内的交点总数.解 依题意,一个交点由两条对角线与相交而得,反之,两条相交的对
10、角线与,确定一个交点,而与(,)可建立一一对应.又因两条相交的对角线与分别由凸边形中两对顶点,和,连接而成,故(,)又可与4顶点组(,)建立一一对应,即有(,)(,)因此,形内对角线的交点总数=凸边形的4顶点组的组数=.例2-2 将三角形每边等分,过分点作其余两边的平行线,在已知三角形内所形成的平行四边形的个数记为,求的表达式.解 延长到使,延长到使.设将等分的分点(包括,共个)依次记为0,1,2,于是平行四边形每边所在直线恰与交与4点,(0)反之,从上的个等分点中任意取4个等分点,(0),过,作的平行线,过,作的平行线,便可得到一个平行四边形,这种对应是一一对应,所以图中边不平行与的平行四边
11、形有个,从而平行四边形的总个数=3个.3递推法例3-1 将圆分成(2)个扇形,.现用种颜色给这些扇形染色,每个扇形恰染一种颜色且要求相邻的扇形的颜色互不相同.问有多少种不同的染色方法?解 设染色方法数为.(1)求初始值.=2时,给染色有种方法,继而给染色有(-1)种方法,所以,=(-1).(2)求递推关系.因有种染色方法,有(-1)种染色方法,有(-1)种染色方法,有(-1)种染色方法,仍有(-1)种染色方法(不保证与不同色).这样共有种染色方法,但这种染色方法可分为两类:一类是与不同色,此时的染色方法有种;另一类是与同色,则将与合并为一个扇形,并注意到此时与不同色,故这时的的染色方法有种,由
12、加法原理得+=(2)(3)求.令=,由+=,有1=(),即1为首项为1,公比为的等比数列的第项.1()(),即,例3-2 将周长为24的圆周等分为24段,从24个分点中选取8个点,使得其中任何两点所夹的弧长都不等于3和8.问满足要求的8点组的不同取法有多少种? (2001年CMO题)解: 设24个分点依次为1,2,24,将24个数列成下表:147101316192291215182124361720232581114表中每行相邻两数所代表的点所夹弧长为3,每列相邻两数所代表的点所夹弧长为8,故每列至多取一个数,8列至多取8个数,但一共要取8个数,故每列恰取一个数且相邻两列所取的数不同行.若将每
13、列看作一个扇形,每列中第一、而、三行看作三种颜色,则由上面例题知,=258种.例3-3 如图在1个正六边形的6个区域栽种观赏植物,要求同1区域中种同一种植物,相邻的2区域中种不同的植物.现有4种不同的植物可供选择,则有 种栽种方案. (2001年全国高中联赛题)解: 在上述命题中,取=6,=4,即得=732种.例3-4 用红、黄、蓝、绿四种颜色给图中的A、B、C、D四个小方格涂色(允许只用其中几种),使邻区(有公共边的小格)不同色,则不同的涂色方式种数为( ). 、; 、; 、; 、.解:选两色有种,一色选择对角有种选法,共计种;选三色有种,其中一色重复有种选法,该色选择对角有种选法,另两色选
14、位有种,共计种;四色全用有种(因为固定位置),合计种.DBCA变例:(2008全国一)如图,一环形花坛分成四块,现有4种不同的花供选种,要求在每块里种1种花,且相邻的2块种不同的花,则不同的种法总数为( B )A96B84C60D48例3-5 有人要上楼,此人每步能向上走1阶或2阶,如果一层楼有18阶,他上一层楼有多少种不同的走法?解法1: 此人上楼最多走18步,最少走9步.这里用分别表示此人上楼走18步,17步,16步,9步时走法(对于任意前后两者的步数,因后者少走2步1阶,而多走1步2阶,计后者少走1步)的计数结果.考虑步子中的每步2阶情形,易得,.综上,他上一层楼共有种不同的走法.解法2
15、: 设表示上n阶的走法的计数结果.显然,(2步1阶;1步2阶)对于起步只有两种不同走法:上1阶或上2阶.因此对于,第1步上1阶的情形,还剩阶,计种不同的走法;对于第1步上2阶的情形,还剩阶,计种不同的走法.总计.同理,.4容斥原理例4-1 由数字1,2,3组成n位数,且在这个n位数中,1,2,3的每一个至少出现一次,问这样的n位数有多少个?解 设U是由1,2,3组成的n位数的集合,是U中不含数字1的n位数的集合,是U中不含数字2的n位数的集合,是U中不含数字3的n位数的集合,则;因此即符合题意的n位数的个数为例4-2 参加大型团体表演的学生共240名,他们面对教练站成一行,自左至右按1,2,3
16、,4,5,依次报数教练要求全体学生牢记各自所报的数,并做下列动作:先让报的数是3的倍数的全体同学向后转;接着让报的数是5的倍数的全体同学向后转;最后让报的数是7的倍数的全体同学向后转问:(1)此时还有多少名同学面对教练?(2)面对教练的同学中,自左至右第66位同学所报的数是几?解(1)设,表示由U中所有i的倍数组成的集合则;,;,;从而此时有名同学面对教练如果我们借助维恩图进行分析,利用上面所得数据分别填入图1,注意按从内到外的顺序填如图1,此时面对教练的同学一目了然,应有109+14+4+9=136名(2)用上面类似的方法可算得自左至右第1号至第105号同学中面对教练的有60名考虑所报的数不
17、是3,5,7的倍数的同学没有转动,他们面对教练;所报的数是3,5,7中的两个数的倍数的同学经过两次转动,他们仍面对教练;其余同学转动了一次或三次,都背对教练从106开始,考虑是3、5、7的倍数:3的倍数(由105依次加3):108,111,114,117,120,5的倍数(由105依次加5):110,115,120,7的倍数(由105依次加7):112,119,因此,从106号开始,自左至右,面对教练的同学所报的数依次是:106,107,109,113,116,118,120,由此可知面对教练的第66位同学所报的数是118例4-3 将与105互素的正整数从小到大排成数列,求出这个数列的第100
18、0项. (1994年全国高中联赛题)解 首先,求出=1,2,105内与105=345互素的正整数的个数,令=|且被整除(=3,5,7).于是中与105互素的正整数的个数为|=|-|-|-|+|+|+|-|=105+=105-35-21-15+7+5+3-1=48其次,设所有正整数中与105互素的正整数从小到大排成数列为,于是有,=1,=2,=4,=101,=103,=104,并记=,.一方面,数列中每一项可表示成为=(,为非负整数,0104),于是由(,105)=(,105)=(,105)=1,知,即数列中每一项可表示成为=(为非负整数,)的形式.另一方面,对任意非负整数及任意,由(,105)
19、=(,105)=1,知数列中必有某一项=.可见,数列有且仅有形如(为非负整数,)的数组成,因对每一个固定的,取遍中的数时,形如的数有48个,得到数列中的48个项,因为1000=+40,所以,=+.而=104,=103,=101,=97,=94,=92,=89,=88,=86,所以=+86=2186.例4-4 五人站成一列,重新站队时,各人都不站在原来的位置上,有多少种站法?解:设原来站在第i个位置的人是(i=1,2,3,4,5).重新站队时,站在第2个位置的站法有种,其中不符合要求的有:站第3位的种,站第4位的种,但有的站法在考虑的情形时已经减去了,故只应再算()种,同理,站第5位的应再算种.
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数学 冬令营 组合 计数
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【天****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【天****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。