《组合学初步》PPT课件

集合与图论,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第 2 节 组合学初步,广义的组合数学就是离散数学，离散数学是狭义的组合数学和图论、代数结构、数理逻辑等的总称。但这只是不同学者在叫法上的区别。总之，组合数学是一门研究离散对象的科学。,狭义的组合数学主要研究满足一定条件的组态（也称组合模型）的存在、计数以及构造等方面的问题。,组合数学的主要内容有组合计数、组合设计、组合矩阵、组合优化等。,1,第 2 节 组合学初步,主要内容：,基本计数法则,容斥原理,抽屉原理,2,1 基本计数法则,如果具有性质A的事件有m个，性质B的事件有n个，则具有性质A或B的事件有m+n个。,加法法则：,设A，B为两个不相交的有限集，则,AB,=,A,+,B,。,集合描述：,（A和B是性质无关的两个事件）,3,基本计数法则,通俗的语言描述：,如果有p种方法能够从一堆物品中选择一个物品，而有q种方法也能够从另一堆物品中选择一个物品，那么从这两堆物品中选择一个物品的方法共有p+q种。,4,基本计数法则,若具有性质A的事件有m个，具有性质B的事件有n个，则具有性质A及B的事件有mn个。,乘法法则：,设A，B为有限集，则,A,B,=,A,B,。,集合描述：,5,基本计数法则,通俗的语言描述：,一项任务有p个结果，而不论第一项任务的结果如何，第二项任务都有q个结果，那么，这两项任务连续执行就有pq个结果。,一项任务要经过两个步骤，如果第一个步骤有p个结果，而不论第一步的结果如何，第二个步骤都有q个结果，那么，这项任务就有pq个结果。,或者,6,基本计数法则,例1：,求小于10000的正整数中含有数字1的数的个数？,例3：,确定数3,4,5,2,11,7,13,8,的正整数因子的个数？,例2：,两位数字有多少两个位互异且非零的两位数？,（答案：3439）,（答案：72）,（答案：1080）,7,问题：,设A,B,C,D为有限集，则,AB=?,ABC=?,ABBC=?,S,A,B,AB,2 容斥原理,8,定理1,容斥原理(或逐步淘汰原理)形式之一,设A,1,A,2,.,A,n,为n个有限集，则,容斥原理,9,例1：,在1000名大学毕业生的调查中,有804人掌握了英语,205人掌握了日语,190人撑握了俄语,125人既掌握了英语又掌握了日语,57人既掌握了日语又掌握俄语,85人既掌握英语又掌握俄语。,试求这1000名大学生中，英语、日语、俄语全掌握的有多少？,容斥原理,10,ABC,=,A,+B+C-,AB,-,AC,-,BC,+,ABC,1000=,804+205+190-125-85-57,+,ABC,ABC,=68,英语、日语、俄语全掌握的有68人。,则,A,=804，B=205，C=190，,AB,=125,AC,=85,BC,=57,容斥原理,解:,设A为掌握了英语的人数，,B为掌握了日语的人数，,C为掌握了俄语的人数。,11,定理2,容斥原理(或逐步淘汰原理)形式之二,设A,1,A,2,.,A,n,都是有限集S的子集，则,容斥原理,12,例2：,1,2,3,4,5,6六个数的全排列中不出现135和46的排列有多少个？,容斥原理,例3：,一个人写了十封集和十个信封，然后随机,地将信装入信封，试求每封信都装错了的概率。,13,容斥原理解决的问题:,广义容斥原理解决的问题:,容斥原理,14,抽屉原理：简单形式,如果n+1个物体被放进n个盒子中，那么至少有一个盒子包含两只或更多的物体。,其它表述形式：,如果,n+1,只鸽子被放进,n,个鸽巢中，那么至少有一个鸽巢包含两只或更多的鸽子。,如果,n+1,个物体用,n,种颜色涂色，那么必然有两个物体被涂成相同的颜色。,3 抽屉原理,15,4个物体,3个盒子,存放,1,2,3,4,5,抽屉原理,16,例1：,在13个人中存在两个人，他们的生日在同一个月 份里。,抽屉原理,考虑12个盒子，每个盒子对应一个月份，将13,个人放到12个盒子中，则至少有一个盒子包含两个或,两个以上的人，即，这在13个人中存在两个人，他们,的生日在同一个月份里。,17,应至少选择n+1个人。,考虑n个盒子，每个盒子对应一对夫妇。如果我们选择n+1个人并把他们中的每一个人放到他们对偶所在的那个盒子中去，那么就有同一个盒子含有两个人，也就是说，我们选择了一对已婚夫妇。,如果选择n个人，可以只选择所有丈夫或只选择所有的妻子。,抽屉原理,例2：,设有n对已婚夫妇。为保证能够有一对夫妇被选出，至少要从这2n个人中选出多少人？,18,例3：,给定m个整数a,1,a,2,a,m,存在整数k和l，0klm，使得a,k+1,+a,k+2,+a,l,能够被m整除。,抽屉原理,例4：,一位国际象棋大师有11周的时间备战一场锦标赛，他决定每天至少下一盘棋，但是为了使自己不过分疲劳他还决定在每周不能下棋超过12盘。证明存在连续若干天，期间这位大师恰好下了21盘棋。,例5：,从整数1,2,3,200中我们选择101个整数。证明，在所选择的这些整数之间存在两个这样的整数，其中一个可以被另一个整除。,整数分解知识：任何一个整数都可以写成2,k,a的形式，其中，k0，a为奇数。,19,抽屉原理：加强形式,令q,1,q,2,q,n,为n个正整数。如果将q,1,+q,2,+q,n,-n+1个物体放入n个盒子内，那么，或者第一个盒子至少含有q,1,个物体，或者第二个盒子至少含有q,2,个物体,或者第n个盒子至少含有q,n,个物体。,抽屉原理,抽屉,原理的简单形式是其加强形式通过,q,1,=q,2,=q,n,=2,来实现的。这时，,q,1,+q,2,+q,n,-n+1=2n-n+1=n+1,。,20,证明：采用反证法，设将q,1,+q,2,+q,n,-n+1个物体放入到n个盒子中，如果对于每个i=1,2,n，第i个盒子含有少于q,i,个物体，那么所有盒子中的物体总数不超过,(q,1,-1)+(q,2,-1)+(q,n,-1)=q,1,+q,2,+q,n,-n,这与物体的总数为q,1,+q,2,+q,n,-n+1相矛盾，所以或者第一个盒子至少含有q,1,个物体，或者第二个盒子至少含有q,2,个物体,或者第n个盒子至少含有q,n,个物体。,抽屉原理,21,推论1.,m个物体，n个盒子，则至少有一个盒子里有不少于(m-1)/n+1个物体。,证明：采用反证法，设所有盒子了最多有(m-1)/n个物体，则n个盒子中的物体数最多为n(m-1)/n m-1，与假设矛盾。,推论2：,若取n(m-1)+1个物体放入n个盒子中，则至少有1个盒子有m个物体。,这个推论相当于q,1,=q,2,=q,n,=m时的特殊情况。,抽屉原理,22,则,m,1,m,2,m,n,中至少有1个数不小于,r,。,推论3：,若,m,1,m,2,m,n,是,n,个正整数，而且,抽屉原理,例6：,证明每个由n,2,+1个实数构成的序列a,1,a,2,a,n,2,+1,或者含有长度为n+1的递增子序列，或者含有长度为n+1的递减子序列。,23,