预备知识.pptVIP

预备知识 ——集合论及排列组合的复习 2．组合 3．乘法原理与加法原理  * 一、有关集合论基本概念的知识： 1.集合：一个集合是指一堆事物的总体。通常用大写字母A，B，C等表示。 2.描述方法： （1）列举法： （2）描述法： 一般可将集合表示成如下的形式：A={ω｜ω具有性质P}， 组成集合A的那些个别事物叫做A的元素。当ω是A的一个元素时，写成ω∈A，而当ω不是A的元素时则写成ω?A。 通常我们把所考虑的所有事物组成的集合定义为全集，通常用U表示，把不含有任何元素的集合称为空集，用Φ表示。 例: 我们限于实数范围内考虑集合，则一切实数组成的集合就是一个全集，通常用R表示一切实数的集合，对于集合A={x|x2+1=0}，由于在实数范围内x2+1=0无解，那么A是空集。 3.分类： (1)有限集 (2)无限集：可列集，如：自然数集，不可列集， 如：实数集。 4.集合间的关系与集合的运算 （1）A、B为两集合，若ω∈A,则ω∈B，即A中的元素全在B中，我们称B包含A或称A为B的子集，记为B?A或A?B。若A?B且A?B，则称A与B相等，记为A=B。 （2）A、B为两集合，称集合{ω｜ω∈A或ω∈B}为集合A与B的并集，记为A∪B。 B A A B A∪B A （4）A为一集合，称集合{ω｜ω A且ω∈U}为集合A的补集，记为ā ，即ā是由所有不在A内的元素（但在全集U内）组成。 （5） A，B为两集合，称集合{ω｜ω∈A且ω B}为A与B的差集，记为A-B，即A-B是由所有属于A但不属于B的元素组成。 （3）A，B为两集合，称集合{ω｜ω∈A且ω∈B}为集合A与B的交集，记为AB或A∩B。 A ā A-B B A B A∩B 5．常用公式： 容易验证下列关系式 （1）AU=A A∪U=U （2）AΦ=Φ AU=A （3） =A , ??=U， ?U＝Φ （4）A－Φ＝A,Φ－A=Φ, U－A=?A, A－U=Φ 例如：按上述定义：A∪B∪C={ω｜ω∈A或ω∈B或ω∈C} 二、排列与组合的复习 1．排列 从包含有n个不同元素的总体中取出r个来进行排列，这时既要考虑取出的元素又要考虑其取出的顺序．这种排列可分为两类，第一种有放回的选取；另一种是不放回选取，r≤n。 （1）可重复排列： 在有放回选取中，从n个不同元素中取出r个元素进行排列，这种排列称为可重复的排列，其总数共有nr种．  例.从1，2，3，4四个数中，任取两个，问能组成多少个两位数？ 解：1）若不允许重复： （2）选排列：在不放回选取中，从n个不同元素中取出r个元素进行排列，称为选排列．其总数为 （3）全排列：特别当r=n时，称为全排列数,n个元素的全排列数为: 2）若允许重复：42=16。 （1）从n个不同元素中取出r个元素而不考虑其顺序， 称为组合，其总数为 ， 这里是二项展开式 的系数. （2）性质： ， ， ， ， 等。 总之,从n种不同的元素中取出r个元素有多少个 不同的结果？按是否可以重复及是否只管内容不管次序，有下列情况 **若r1＋r2＋…rk=n，把n个不同的元素分成k个部分，  第一部分r1个，第二部分r2个，…，第k部分rk个，  则不同的分法有 , 考虑次序：不重复 可重复 nr不考虑次序：不重复 可重复 乘法原理：若进行I过程有n1种方法，进行II过程有n2种方法，则进行I过程后再接着进行II过程共有n1×n2种方法 加法原理：若进行I过程有n1种方法，进行II过程有n2种方法，假定I过程与II过程是并行的，则进行过程I或过程II的方法共有n1＋n2种方法。 I II n1×n2 I II n1＋n2 例1. 袋中装有白球5个，黑球4个，问： 1)从中任取2个，有多少种取法？ 2)从中任取2个，一个白球一个黑球，有多少种取法？ 解：1)共有 种取法 2)共有 种取法  例2. 15个学生分为三组，每组5个人，有多少种分法？ 解：若考虑三组的区别：有 种分法.  若不考虑三组的区别：有 种分法