第2节有限合的计数.ppt

基本计数法则 容斥原理 抽屉原理* 集合与图论 * 主要内容： 第 2 节 有限集合的计数 1 基本计数法则 加法法则： 设A，B为两个不相交的有限集，则 ?A∪B?=?A?+?B?。 集合描述： 通俗的语言描述： 如果有p种方法能够从一堆物品中选择一个物品，而有q种方法也能够从另一堆物品中选择一个物品，那么从这两堆物品中选择一个物品的方法共有p+q种。 基本计数法则 乘法法则： 设A，B为有限集，则?A?B?=?A???B?。 集合描述： 通俗的语言描述： 一项任务要经过两个步骤，如果第一个步骤有p个结果，而不论第一步的结果如何，第二个步骤都有q个结果，那么，这项任务就有p×q个结果。 基本计数法则 例2：求小于10000的正整数中含有数字1的数的个数？ 例4：确定数34?52 ?117?138的正整数因子的个数？ 例3：两位数字有多少两个位互异且非零的两位数？ （答案：3439） （答案：72） （答案：1080） 例1：集合S为有限集合，|S|=n，则|P(S)|=? 问题： 设A, B, C, D为有限集，则 ?A∪B?=? ?A∪B∪C?=? ?A∪B∪B∪C?=? S A B A∪B 2 容斥原理 定理1 容斥原理(或逐步淘汰原理)形式之一 设A1, A2 ,... , An为n个有限集，则 容斥原理 例1：在1000名大学毕业生的调查中, 有804人掌握了英语, 205人掌握了日语, 190人撑握了俄语, 125人既掌握了英语又掌握了日语, 57人既掌握了日语又掌握俄语, 85人既掌握英语又掌握俄语。 试求这1000名大学生中，英语、日语、俄语全掌握的有多少？ 容斥原理 ?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为掌握了俄语的人数。 定理2 容斥原理(或逐步淘汰原理)形式之二 设A1,A2,...,An都是有限集S的子集，则 容斥原理 例2：1,2,3,4,5,6六个数的全排列中不出现135和46的排列有多少个？ 容斥原理 例3：求不超过120素数的个数。 （答案：582） （答案：30） 容斥原理解决的问题: 广义容斥原理解决的问题: 容斥原理 抽屉原理：简单形式 如果n+1个物体被放进n个盒子中，那么至少有一个盒子包含两只或更多的物体。 其它表述形式： 如果n+1只鸽子被放进n个鸽巢中，那么至少有一个鸽巢包含两只或更多的鸽子。 如果n+1个物体用n种颜色涂色，那么必然有两个物体被涂成相同的颜色。 3 抽屉原理 4个物体 3个盒子 存放 1 2 3 4 5 抽屉原理 例1：在13个人中存在两个人，他们的生日在同一个月 份里。 抽屉原理 考虑12个盒子，每个盒子对应一个月份，将13 个人放到12个盒子中，则至少有一个盒子包含两个或 两个以上的人，即，这在13个人中存在两个人，他们 的生日在同一个月份里。 应至少选择n+1个人。 考虑n个盒子，每个盒子对应一对夫妇。如果我们选择n+1个人并把他们中的每一个人放到他们对偶所在的那个盒子中去，那么就有同一个盒子含有两个人，也就是说，我们选择了一对已婚夫妇。 如果选择n个人，可以只选择所有丈夫或只选择所有的妻子。 抽屉原理 例2：设有n对已婚夫妇。为保证能够有一对夫妇被选出，至少要从这2n个人中选出多少人？ 例3：给定m个整数a1, a2, …, am, 存在整数k和l，0≤kl≤m， 使得ak+1+ak+2+…+al能够被m整除。 抽屉原理 例4：一位国际象棋大师有11周的时间备战一场锦标赛，他决定每天至少下一盘棋，但是为了使自己不过分疲劳他还决定在每周不能下棋超过12盘。证明存在连续若干天，期间这位大师恰好下了21盘棋。 例5：从整数1,2,3,…,200中我们选择101个整数。证明，在所选择的这些整数之间存在两个这样的整数，其中一个可以被另一个整除。 整数分解知识：任何一个整数都可以写成2k?a的形