第5讲 集合(PPT)
- 格式:pptx
- 大小:528.30 KB
- 文档页数:37
第5讲 集合的基本划分[知识点金]集合的划分反映了集合与子集之间的关系,这既是一类数学问题,也是数学中的解题策略——分类思想的基础,在近几年来的数学竞赛中经常出现,日益受到重视,本讲主要介绍有关的概念、结论以及处理集合、子集与划分问题的方法. 覆盖 若把一个集合A 分成若干个叫做分块的非空子集,使得A 中的每个元素至少属于一个分块,这些分块的全体叫做A 的一个覆盖,即是:设A 为非空集合,S={},其中A,(i=1,2,...,m)且=A则集合S 称作集合A 的覆盖.划分 给定集合A 的一个覆盖S ,若A 中的每一个元素属于且仅属于S 的一个分块,那么S 称作是A 的一个划分.即是:若S 是集合A 的覆盖,且满足=,这里(i j)则称S 是A 的划分.抽屉原则抽屉原则的常见形式一、把n+k (k ≥1)个物体以任意方式全部放入n 个抽屉中,一定存在一个抽屉中至少有两个物体.二、把mn+k (k ≥1)个物体以任意方式全部放入n 个抽屉中,一定存在一个抽屉中至少有m+1个物体.三、m 1+m 2+…+m n +k (k ≥1)个物体以任意方式全部放入n 个抽屉中,那么后在一个抽屉里至少放入了m 1+1个物体,或在第二个抽屉里至少放入了m 2+1个物体,……,或在第n 个抽屉里至少放入了m n +1个物体.四、把m 个物体以任意方式全部放入n 个抽屉中,有两种情况:①当n|m时(n|m 表示n 整除m ),一定存在一个抽屉中至少放入了nm个物体;②当n 不能整除m 时,一定存在一个抽屉中至少放入了[nm]+1个物体([x]表示不超过x的最大整数).五、把无穷多个元素分成有限类,则至少有一类包含无穷多个元素. 容斥原理基本形式()n n nk j i k jini j i jii n A A A A AA AA A A A A ⋂⋂-+-⋂⋂+⋂-=⋃⋃+<<≤=≤<≤∑∑∑211111211||其中|A|表示集合A 中元素的个数。