如果这三个集符合 一{x!z∈B且x∈C}, 则说集A是集B,C的交,记为 d=B∩C 如果这三个集符合 ∈B且xkC 则说集A是集B对C的差,记为 A一B\C. 并与交的定义和记号容易推广到多个乃至无穷多个集的情形,它 们分别是 A:∪A={xx∈A(某i∈)} A:=∩A:{x|x∈A(切i∈1)} 这里I为指标集 如果按照某一确定的规则φ,集A的每一元a都对应于集B 的唯一一个确定的元4,则称这个对应规则为映射或对应,并说a 是a在映射q之下的像,记为 d=:φ(a)或 这里,符号“=:”表示由左节来定义右节的定义式,如果 B={(a)a∈A}, 则说映射甲是A到B内的映射,并说集A为P的定义域,集B为q 的值域如果 B-{q(a)|a∈A}, 则说甲是A到B上的映射.如果是A到B内的映射,且合条件 g(a2),若 (1.12) 则说甲是A到B内的(1-1)映射.如果是A到B上的映射且合 条件(11.2),则说是A到B上的(1-1)映射,简称为(I-1) 映射。此时又说,集A与B是(1-1)对应的,如果集A与B之间
有一个(1-1)映射存在就说集A与B等势,记为 N B 付于等势的集,又说匕们具有相同的势.势就是等势诸集的公共 性质 用Z表示全体整数所组成的集,用N表示全体自然数所组成 的集,且记N=N∪{0}.称集 x1m≤x≤n,x∈ 为z的m至n截段,记为 【m,a] 也记 m,∞):一{x|m≤x<∞,x∈公}, ≤m,x∈Z}, (m,n]:冖Lm,n]{m}, (m,∞):冖1m,∞){m}, ( 如果集A与[1,n]等势,就说是一个n元集其中恰有n个元 空集和n元集(nEN)统称为有限集.不是有限集的集叫做无限 集。易知,当A,B是有限集时,A~B的充要条件是A,B各有同 样多的元,故此时d的势就是A的元的个数,简称为元数.对于无 限集,势的作用类似于有限集的元数的作用。无论A是有限集还 是无限集,其势均以」A|记之 下面介绍有关计数问题的两个基本法则 定理111(和则).岩有限樂A,B符合A∩B〓则 AUB|=|4|+|B (1.1.3) 证明当A,B中有一个是空集时,结论(11.3)是平凡的 今设卡中,B卡中,记 b 因为 午h(1≤1≤n;1≤1≤m)
故映射 (I≤i≤n) 十j(1 是A∪B到[!,m+n】上的(1-1)映射,故有(113).证毕 和则还可叙述为:如果某物C1有m种方法(这些方法所组成 的集记为A)选出,另一物O2有另外#种方法(这些方法所组成 的集记为B)选出,则定理1.2.1断言,选出物②1或C2有m+ 种方法 设A,B是任惫二集,则称集 (a,b)!a∈A,b∈B} 为集A与B的 Descartes积,记为A×B,同样可以定义任意多 (有限或无限)个集的 Descartes积.须注意,d×B中二元相等, 即(ab)=(41,如1)的充要条件是 且b〓b A×B中的元(a,b)称为A中元4与B中元b的有序对.易知, A×φ冖中×!冖巾,令 D(A,{B}n){(4,b)a∈A,b∈B,且|Bn}, 这里{Ba}a∈A表示由随a而定的集B所组成的集族,如果对任意 的a∈A都有B=B,则记 D(A, B: n):=D(A,B.lae4i n) 易知,当|B}=”时,有 D(A,B;n)一A×B 定理112(积则)如果|Ai一m,JBa叫n(a∈A) m∈N,n∈N,则 ID(A,iBed n) 证明。若m=0或n〓0,则(1.14)的两节同时为零设 0,且记 B〓{bnb }(1≤≤m)
则映射 q:(a,b;)→(i-)m+(!≤i≤m;1≤j≤n) 是集D(A,{Ba}∈4;n)到l1,mn]上的个(1-1)映射,故 (114)成立.证毕 积则还可叙述为:如果某物1有m种方法(这些方法所组成 的集记为A)选出,由中任一种方法a选出O1之后,都有m种方 法(这些方法所组成的集记为B选出另一物巴2,则定理122断 言依次选出物O1和的2有mn种方法 上述两个定理均可推广到有限多个集的情形 定理11.3设诸集A(1≤i≤n)合于 A1∩A;如中(1≤ij≤n), 则 UA,=∑1A (1.1.5) 定理114.已给集A和n1…n∈N.若诸集A,(1≤i k)逐次确定为 A1:当1 A:=D(A1-1,{(B4}A-;n)(2≤j≤饣), 其中集(B;)依A-:中的元a而定,且设|A1|=n1,|(B;) n(a∈A1-1,2≤1≤k),那末, 上述两个定理的证明可由数学归纳法得出 §1.2排列与组合 为了便于引用和比较,首先给出各种常见的排列、组合的定 义 定义121.集A的一个排列是A中元的一个有序选出.若 R是对排列的限制条件,则这样的排列叫做R-排列;如果R的叙 述较长,又写为“排列2具有性质R”特别地,如果性质R是“排列
中元的个数是”,这种R排列就简称为r-排列,又说r是该排列 的长.如果性质R是“在排列中不允许任何元重复出现”,则这种 R-排列简称为无重排列;如果牲质R是“在排列中允许元重复出 现”,则这种R-排列简称为可重排列.全部R-排列的个数叫做 R-排列数。若!4|为有限数,则称A的无重|A|-排列为A的全 排列 定义1.22集d的一个组合是A中元的一个无序选出.若 Q是对组合的限制条件,则这样的组合叫Q组合;如果Q的叙述 较长,又写为“组合,具有性质Q”,特别地,如果性质Q是“组合中 元的个数为r”,则这种Q组合简称为r-组合.如果性质9是“在 组合中不允许任何元重复出现”,则这种Q组合简称为无重组合; 如果性质Q是“在组合中允许元重复出现”,则这种Q组合简称为 可重组合.全部Q组合的个数叫做Q-组合数 例如,设集 那么,d的2-可重排列共有九个: aa,40,4c 3 g 3 2 2-无重排列共有六个: ba. bc.cat 2可重组合共有六个: b CC3 403 4c. c 2一无重组合共有三个: ab, ac, bc 若|A!=n,那末,在讨论排列数和组合数时,不失一般,可 设A为[1,n1.今后常用下列符号: P:集A的r-无重排列全体所组成的集, Pre Pri C":集A的r无重组合全体所组成的集 Cr ae iCr; UP;集A的r-可重排列全体所组成的集, 7