第2节组合学初步

《第2节组合学初步》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2节组合学初步广义的组合数学就是离散数学，离散数学是狭义的组合数学和图论、代数结构、数理逻辑等的总称。但这只是不同学者在叫法上的区别。总之，组合数学是一门研究离散对象的科学。狭义的组合数学主要研究满足一定条件的组态（也称组合模型）的存在、计数以及构造等方面的问题。组合数学的主要内容有组合计数、组合设计、组合矩阵、组合优化等。1第2节组合学初步主要内容：基本计数法则容斥原理抽屉原理2基本计数法则如果具有性质A的事件有m个，性质B的事件有n个，则具有性质A或B的事件有m+n个。加法法则：设A，B为两个不相交的有限集，则A∪B=A+B。集合描述：（A和B是性质无关的

2、两个事件）3基本计数法则通俗的语言描述：如果有p种方法能够从一堆物品中选择一个物品，而有q种方法也能够从另一堆物品中选择一个物品，那么从这两堆物品中选择一个物品的方法共有p+q种。4基本计数法则若具有性质A的事件有m个，具有性质B的事件有n个，则具有性质A及B的事件有mn个。乘法法则：设A，B为有限集，则AB=AB。集合描述：5基本计数法则通俗的语言描述：一项任务有p个结果，而不论第一项任务的结果如何，第二项任务都有q个结果，那么，这两项任务连续执行就有p×q个结果。一项任务要经过两个步骤，如果第一个步骤有p个结果，而不论第一步的结果如何，第二个步骤都有q个

3、结果，那么，这项任务就有p×q个结果。或者6基本计数法则例1：求小于10000的正整数中含有数字1的数的个数？例3：确定数3452117138的正整数因子的个数？例2：两位数字有多少两个位互异且非零的两位数？（答案：3439）（答案：72）（答案：1080）7问题：设A,B,C,D为有限集，则A∪B=?A∪B∪C=?A∪B∪B∪C=?SABA∪B容斥原理8定理1容斥原理(或逐步淘汰原理)形式之一设A1,A2,...,An为n个有限集，则容斥原理9例1：在1000名大学毕业生的调查中,有804人掌握了英语,205人掌握了日语,190人撑握了俄语,125人既掌

4、握了英语又掌握了日语,57人既掌握了日语又掌握俄语,85人既掌握英语又掌握俄语。试求这1000名大学生中，英语、日语、俄语全掌握的有多少？容斥原理10A∪B∪C=A+B+C-A∩B-A∩C-B∩C+A∩B∩C1000=804+205+190-125-85-57+A∩B∩CA∩B∩C=68英语、日语、俄语全掌握的有68人。则A=804，B=205，C=190，A∩B=125,A∩C=85,B∩C=57容斥原理解:设A为掌握了英语的人数，B为掌握了日语的人数，C为掌握了俄语的人数。11定理2容斥原理(或逐步淘汰原理

5、)形式之二设A1,A2,...,An都是有限集S的子集，则容斥原理12例2：1,2,3,4,5,6六个数的全排列中不出现135和46的排列有多少个？容斥原理例3：一个人写了十封集和十个信封，然后随机地将信装入信封，试求每封信都装错了的概率。13容斥原理解决的问题:广义容斥原理解决的问题:容斥原理14抽屉原理：简单形式如果n+1个物体被放进n个盒子中，那么至少有一个盒子包含两只或更多的物体。其它表述形式：如果n+1只鸽子被放进n个鸽巢中，那么至少有一个鸽巢包含两只或更多的鸽子。如果n+1个物体用n种颜色涂色，那么必然有两个物体被涂成相同的颜色。抽屉原理154个物体3个盒子存放

6、12345抽屉原理16例1：在13个人中存在两个人，他们的生日在同一个月份里。抽屉原理考虑12个盒子，每个盒子对应一个月份，将13个人放到12个盒子中，则至少有一个盒子包含两个或两个以上的人，即，这在13个人中存在两个人，他们的生日在同一个月份里。17应至少选择n+1个人。考虑n个盒子，每个盒子对应一对夫妇。如果我们选择n+1个人并把他们中的每一个人放到他们对偶所在的那个盒子中去，那么就有同一个盒子含有两个人，也就是说，我们选择了一对已婚夫妇。如果选择n个人，可以只选择所有丈夫或只选择所有的妻子。抽屉原理例2：设有n对已婚夫妇。为保证能够有一对夫妇被选出，至少要从这2n个人

7、中选出多少人？18例3：给定m个整数a1,a2,…,am,存在整数k和l，0≤k