1.4 有穷集的计数

数学学习 · 爱知数学讲义

18
本章目录 · 1 节

本章导读

文氏图用矩形表示全集 ,用圆或其他闭曲线内部表示集合,用阴影表示运算结果。两集合没有共同元素时,所代表的区域不重叠;包含关系用内外嵌套的区域表示。没有“不交”等额外条件时,画一般位置的相交圆可以保留各种可能的隶属组合。

图的边界只辅助区分区域,数值计算应依据集合条件。特别是相切的画法容易引起“接触点是否算共同元素”的歧义,表示不交时下面使用严格分离的区域。文氏图不是按集合元素个数绘制的统计面积图,圆的面积大小不代表集合基数。

EAB
两个集合不交,交集为空。
EBA
是 的真子集, 中还保留不属于 的区域。
EAB
阴影为 。
EAB
阴影为 ,共同区域只计一次。
EAB
阴影为 。
EA
阴影为全集内、 外的区域 。
EAB
阴影为 ,共同区域不着色。
EABC
阴影为 ,从两集合交集中排除第三集合的部分。

有限集合的元素个数记为 。求计数题时,可把每种性质对应为一个集合,再把全集划分成两两不交的隶属区域。在三集合情形,应区分“属于 的总人数”和“只属于 而不属于 的人数”。前者包含三重交,后者需要减去三重交。

【例1.4.1】24名科研人员至少会英语、日语、德语和法语中的一种,会这四种语言的人数依次为13、5、10、9。会英语和日语的有2人;英语、德语、法语中任意两种都兼会的有4人;会日语者既不会法语也不会德语。求只会一种语言的人数及兼会三种语言的人数。

解:令 分别表示会英语、法语、德语、日语者。 与 均不交,,所以只会日语者有 人。设兼会英语、法语、德语者为 人,那么这三集合的每个“恰好两种”区域均为 。设只会英语、法语、德语者分别为 ,有

在三个集合的并中排除了只会日语的3人和英日兼会的2人,因此 ,而只会英语区中的 未包括英日区,需要保留该2人。等价的分区方程是

解得 。只会一种语言的四类人数为英语4、法语2、德语3、日语3;兼会三种语言者1人。全部分区相加为 ,并可分别核对每种语言总人数。

EABCD423333312|A| = 13 |B| = 9 |C| = 10 |D| = 5
各数值表示两两不交区域的人数。日语只与英语相交,与法语、德语不交;中央1人同时会英语、法语和德语。

【例1.4.2】求1至1000中既不能被5整除、也不能被6或8整除的整数个数。

解:令 分别为能被5、6、8整除的数。它们的大小为200、166、125。两两同时整除等价于被相应最小公倍数整除,因此 、、,三重交大小为 。先从三重交向外填数,得到只属于 的区域分别为150、100、67,只属于两集合的区域分别为25、17、33。故并集有400个元素,所求为 。

EABC150100251733867600
圈内八个隶属区域按整除条件填数,圈外600个数同时不被5、6、8整除。

包含排斥原理把上述分区计算写成一般公式。设有限全集 中的 表示具有性质 的对象,则没有任何一种性质的对象个数为

至少有一种性质的对象个数为

解释其系数时,固定一个恰好属于 个集合的元素:右侧把它计算 次,因为 。不属于任何集合的元素在并集公式中计算0次,因此公式对每个元素均给出正确次数。所有集合必须是有穷集,不能对任意无穷基数直接进行这种带减号的整数计数。

【例1.4.3】 个人各有一顶帽子,随机发还,每人领一顶。求没有人领到自己帽子的分配方式数。

解:把全部分配对应为 个对象的排列,共 种。令 表示第 人恰好领到自己帽子的排列。固定任意 个人领对后,其余 人任意排列,共 种;选择这 个人有 种。包含排斥原理给出错位排列数

规定 。例如 。随 增大,比例 趋于 ,这个比例是极限而不是每个有限 的精确概率。空排列可另约定 ,便于递推和公式统一。