1、庄伯金 ,1,概率论与随机过程,第0章 预备知识,庄伯金 ,2,主要内容,集合论计数方法,庄伯金 ,3,集合的基本概念,集合论是数学公理体系的基础。集合的描述：是一些可确定的可分辨的事物构成的整体。集合不能被精确定义，只能被描述；集合通常用大写字母来表示；属于集合中的事物称为集合的元素，通常用小写字母来表示。集合的表示方法列举法：列出集合的所有元素；描述法：通常用谓词来概括集合中元素的属性。,集合的基本概念,集合的分类有限集无限集可数集/可列集：自然数集、有理数集不可数集/不可列集：无理数集、实数集集合的关系子集：A、B为集合，如果B中的每个元素都是A中的元素，则称B为A的子集。亦称为B包含于
2、A，或A包含B，记作BA或AB。即有BAx(xB xA)相等：设A、B为集合，如果AB且BA，则称A与B相等，记作AB。即有：ABABBA集合相等,庄伯金 ,4,集合的基本概念,空集：不含任何元素的集合叫做空集，记作。定理：空集是任意集合的子集。幂集：设A为集合，把A的全体子集构成的集合叫做A的幂集，记作P(A)。若A中有n个元素，则P(A)有2n个元素。全集：在一个具体问题中，如果所涉及的集合都是某个集合的子集，则称这个集合为全集，记作E。,庄伯金 ,5,集合的基本概念,集合的运算并运算：设A、B是任意两个集合，所有属于A或者属于B的元素组成的集合，称为A与B的并集，记作AB。ABx|xAx
3、B。交运算：设A、B是任意两个集合，由A与B的公共元素组成的集合，称为A与B的交集，记为AB。ABx|xAxB。相对补集（差集）：设A、B是任意两集合，属于A而不属于B的元素组成的集合，称为B对于A的补集，也叫B对于A的相对补集，记作A-B。A-B=x|xAxB。,庄伯金 ,6,集合的基本概念,集合的运算绝对补集：设A是集合，A对于全集E的相对补集，称为A的绝对补集，记作A。A = E-A = x|xExA = x|xA。对称差集：设A、B是任意两集合，所有属于A或属于B，但又不同时属于A和B的元素组成的集合称为A与B的对称差集合，记作AB。AB= x|(xAxB)xABAB=(AB)-(AB
4、)= (A-B)(B-A),庄伯金 ,7,集合的基本概念,集合运算规律幂等律AA=AAA=A交换律AB=BAAB=BA结合律(AB)C=A(BC)(AB)C=A(BC),庄伯金 ,8,集合的基本概念,集合运算规律同一律A=AAE=A零律AE=EA=分配律A(BC)=(AB)(AC)A(BC)= (AB)(AC),庄伯金 ,9,集合的基本概念,集合运算规律吸收律A(AB)=AA(AB)=A双重否定律(B)=B排中律A(A)=E矛盾律A(A)=,庄伯金 ,10,集合的基本概念,集合运算规律德.摩根律(AB)=(A)(B)(AB)=(A)(B)A-(BC)=(A-B)(A-C)A-(BC)=(A-B
5、)(A-C)差分运算律A-B=A(B)=A-(AB)(A-B)B=A(B-C)=(AB)-(AC),庄伯金 ,11,计数方法,乘法原理和加法原理排列与组合容斥原理,庄伯金 ,12,乘法原理与加法原理,乘法原理：做一件事需要通过n个步骤依次完成，其中完成每个步骤分别有ti种方法，则完成这件事总共有t1 t2 tn种方法。加法原理：做一件事分别有n类方法完成，其中每类方法分别有ti种方法，则完成这件事总共有t1 +t2 +tn种方法。,庄伯金 ,13,排列,从包含有n个不同元素的总体中取出r个来进行排列，这时既要考虑取出的元素又要考虑其取出的顺序。可重复排列：在有放回选取中，从n个不同元素中取出r
6、个元素进行排列，这种排列称为可重复的排列，其总数共有nr种。选排列：在不放回选取中，从n个不同元素中取出r个元素进行排列，称为选排列。其总数为 ：全排列：当r=n时，称为全排列数，n个元素的全排列数为：,庄伯金 ,14,组合,从n个不同元素中取出r个元素而不考虑其顺序，称为组合，其总数为：性质：可重复组合：从n个不同元素中有放回地取出r个元素而不考虑其顺序，其总数为：,庄伯金 ,15,容斥原理,定理：设有穷集合A、B，基数分别为|A|和|B|，则有|AB|=|A|+|B|-|AB|。定理：设A1,A2,.,An为n个有穷集合，其中，集合Ai的基数为|Ai|，则有：,庄伯金 ,16,庄伯金 ,17,容斥原理,设S为有穷集合，P1,P2,.,Pn是n条性质，令Ai表示S中具有性质Pi的元素构成的集合，则S中不具有性质P1,P2,.,Pn的元素个数是：,练习,一副牌共52张，四张A连在一起的顺序共有几种？6个男生和4个女生排成一排，要求女生不能相邻，总共有多少种排队顺序？掷6枚骰子，得到3对，总共有多少种情况？某班有32人，其中爱好打篮球的有20人，爱好踢足球的有25人，既爱打篮球又爱踢足球的有18人，问爱打篮球或踢足球的有多少人？n对夫妇参加舞会，其中每对舞伴都不是每对夫妇。问，共有多少种舞伴组合的方式？,庄伯金 ,18,
