1、12 这一讲主要介绍有限集的阶，有限集上的映这一讲主要介绍有限集的阶，有限集上的映射及其性质，这些在与计数有关的数学竞赛问题中射及其性质，这些在与计数有关的数学竞赛问题中应用极广，是参赛者必不可少的知识应用极广，是参赛者必不可少的知识 .有限集元素的数目 1有限集的阶 有限集A的元素数目叫做这个集合的阶，记作|A|或n(A).card(A) 2集族的阶 若M为由一些给定的集合构成的集合，则称集合M为集族. 设A为有限集，由A的若干个子集构成的集合称为集合A的一个子集族，求满足一定条件的集族的阶是一类常见的问题. 显然，若|A|=n，则由A的所有子集构成的子集族的阶为2n.3 .映射，映射法定义
2、定义1 设设X和和Y是两个集合（二者可以相同）是两个集合（二者可以相同）.如果对于每个如果对于每个 ，都，都有惟一确定的有惟一确定的 与之对应，则称这个对应关系为与之对应，则称这个对应关系为X到到Y的映射的映射.记为记为这时这时,称为的象称为的象,而而x称为称为y的原象的原象,特别当特别当X和和Y都是数集时，映射都是数集时，映射f称为函称为函数数.定义定义2 设设f为从为从X到到Y的一个映射的一个映射.(1)如果对于任何如果对于任何x1、（2）如果对于任何）如果对于任何 ，都有，都有 ，使得，使得f(x)=y，则称，则称f为满射为满射;（3）如果映射）如果映射f既为单射又为满射，则称既为单射又
3、为满射，则称f为双射（一一映射）；为双射（一一映射）；（4）如果）如果f为满射且对任何为满射且对任何 ，恰有，恰有X中的中的m个元素个元素x1、x2、xm，使得使得 定理定理1 设设X和和Y都是有限集，都是有限集，f为从为从X到到Y的一个映射的一个映射, （1）如果）如果f为单射，则为单射，则|X|Y| （2）如果）如果f为满射，则为满射，则|X|Y| （3）如果）如果f为双射，则为双射，则|X|=|Y| （4）如果）如果f为倍数为为倍数为m的倍数映射，则的倍数映射，则|X|=m|Y|. 这个定理的结果是显然的这个定理的结果是显然的.XxYy.),()(,21212为单射则称都有fxfxfxx
4、XxYy.)(, 2 , 1,)(倍数映射的倍数为为则称mfmiyxfiYyXx4差集：ABx|xA且xB(部分资料上用“AB”表示)52.容斥原理容斥原理:设表示集合所含元素的个数设表示集合所含元素的个数 我们用我们用|A|表示有限集合表示有限集合A的元素个数的元素个数(新教材中用新教材中用 表表示有限集合示有限集合A的元素个数的元素个数)。 原理一：给定两个集合原理一：给定两个集合A和和B，要计算，要计算AB中元素的个数，中元素的个数，可以分成两步进行：可以分成两步进行： 第一步：先求出第一步：先求出 A + B （或者说把（或者说把A，B的一切元的一切元素都素都“包含包含”进来，加在一起
5、）；进来，加在一起）； 第二步：减去第二步：减去 AB （即（即“排除排除”加了两次的元素）加了两次的元素） 总结为公式：总结为公式：|AB|= A + B - AB 。 原理二：给定三个集合原理二：给定三个集合A，B，C。要计算。要计算ABC中元中元素的个数，可以分三步进行：素的个数，可以分三步进行： 第一步第一步 求求|A|+|B|+|C|； 第二步第二步 减去减去|AB|，|AC|，|BC|； 第三步第三步 加上加上|ABC|。CardA64.覆盖与划分覆盖与划分：如果集合SS1S2Sn，则S1、S2、Sn叫做集合S的一个覆盖；如果同时又有SiSj(ij),则S1、S2、Sn叫做集合S的
6、一个划分.nikjijinkjijiiniiAAAAAAA111.) 1(11niinA推广推广7加法原理加法原理：做一件事有n类办法，第一类办法中有n1种不同的方法，第二类办法中有n2种不同的方法，第n类办法中有nn种不同的方法，那么完成这件事一共有n1+n2+nn种不同的方法。乘法原理乘法原理：做一件事分n个步骤，第一步有种n1不同的方法，第二步有n2种不同的方法，第n步有nn种不同的方法，那么完成这件事一共有n1.n2.nn种不同的方法。8练习练习910练习练习1112练习练习131设函数2( ) ( ,)f xxaxba bR，集合),(|RxxfxxA， ),(|RxxffxxB。 （1） 证明：BA ； （2） 当3 , 1A时，求B。 2.设S为集合1，2，3，50的一个子集，且S中任意两个元素之和不能被7整除，则S中元素最多有多少个？142详细答案详细答案15
