王慧兴(正高级教师 特级教师)

(清华大学附属中学)

1 内容提要

表1

2 重点解析

2.1 容斥原理

有限集合X的元素个数记作|X|,则有限集合Ai(i＝1,2,…,n)的并集的元素个数算法如下:

所以并集中每个元素在等式左、右两边中被计入的次数都是1次,故等式成立.

2.2 集合划分

集合S的一组非空子集A1,A2,…,Ak满足Ai∩Aj＝∅(∀1≤i＜j≤k),并且A1∪A2∪…∪Ak＝S,则称子集组A1,A2,…,Ak构成集合S的一个k-划分;在划分情境下,容斥计数原理表现为分类加法计数原理:

划分情境下的子集组A1,A2,…,Ak也称为集合S的一个完备子集组,对任意A⊆S,都有

全概率公式推理论证与应用都要依托于有一个完备事件组,这个完备事件组正是基本事件空间Ω的一个划分.

2.3 Sperner定理

定理n元集合S＝{1,2,…,n}(n∈N*)的子集组A1,A2,…,Ak,其中任意两个都没有包含关系,则

2.4 二维表格方法

n元集合S＝{1,2,…,n}(n∈N*)的一组子集A1,A2,…,Ak,记每个元素i∈S恰好含于ai个Aj(1≤j≤k),称ai为元素i关于该子集组的关联度数,所有关联度数构成一个度数序列A:a1,a2,…,an;子集Ai的元素个数记作|Ai|,称为子集Ai的容量;作二维表格,当且仅当i∈Aj时,在第i行第j列小方格填入1,其他位置不填数字(默认为0).

分别按行、列统计表中1的个数(如表2),或对二元组(i,Aj)(i∈Aj)计数,得

表2

2.5 构建计数对象

在组合分析中,我们基于组合计数构建推理论证路径.为此,求解涉及计数对象问题时,要确立计数对象,这种计数对象有些是问题表征明确的,但更多的是基于问题结构以及数据关系,故要将对象重组,将构建的元素组作为计数对象.重建计数对象既能避免重复计数,也是算两次构建计数模型的基本策略.

2.6 一个常用引理

笛卡尔积集由两个集合A,B建立有序二元组(a,b)的集合A×B＝{(a,b)|a∈A,b∈B},称为A与B的笛卡尔积集.很多情境中也表现为如下“加集”与“积集”.一般地,A×B≠B×A,但

引理n元数集A＝{a1,a2,…,an}的“加集”与“积集”分别定义为

(1)|A＋A|≥2n－3;

(2)当A的n个元素都同号,则|A×A|≥2n－3.

证明(1)不妨设a1＜a2＜…＜an,则可以列出加集A＋A中的如下互异元素为

所以|A＋A|≥2n－3.

(2)因为把A中全部元素替换为其相反数,积集A×A不变,而A的元素都同号,所以不妨设0＜a1＜a2＜…＜an,则可以列出积集A×A中的如下互异元素为

所以|A×A|≥2n－3.

3 典例精析

3.1 元素组算两次

元素组具有算两次基本属性,因此,重建元素组并对元素组计数是建立组合情境中数据关联的基本策略、方法.

3.2 子集极值

探求满足特定条件的已知集合的子集中元素个数最多或最少的问题.

例2已知集合A＝{1,2,3,…,20},求最小的正整数n,使得对于A的任一n元子集W,都存在互异元素u,v∈W,满足u＋v＝2k,其中k∈N.

必要性:因为A有12 元子集W＝{20,19,18,17,11,10,9,3,2,4,8,16},其中任意两个元素之和都不是2的非负整数幂,所以n≥13.

充分性:下证n≥13都满足题设条件,只需证明n＝13是充分的即可.

任取A的一个13元子集W,必有某个Ai(1≤i≤8)满足|W∩Ai|＝2,否则对一切1≤i≤8,都有|W∩Ai|≤1,应用上述A的划分,得

这显然不成立,故n＝13满足题设条件.

综上,所求最小正整数n＝13.

例3一个班上有26名学生,每张课桌都坐2名学生,经过一次桌位调换,使得所有原本同桌的两人均被分开.求最大的正整数K,使得学生无论如何选择同桌,最后总存在一个由K名学生构成的集合S,其中任意两名学生都未同桌过.

解析

构图G(V,E):V＝{P1,P2,P3,…,P26},其中P1,P2,P3,…,P26表示26名学生,称为顶点;2名学生同桌代表这2名学生的点之间连一条线段,称为边,并且调换桌位前同桌就画红线,调换桌位后同桌就画蓝线,得到一个红蓝二色图.

性质1图G中每个点引出2条边,并且一条红边一条蓝边,我们称每个点的度数为2,记作d(Pi)＝2(1≤i≤26).

性质2图G是一个圈或几个圈,但没有奇圈,否则圈上就有2条同色边相邻,即从一个点引出2条同色边,这不可能.

性质3顶点集V存在二划分:V＝A∪B,使得|A|＝|B|＝13,并且A,B各自内部的点之间都不连成边,所有的边(13条红边与13条蓝边)都在A,B之间相连.

目标探究一方面,取S＝A或S＝B,则点集S内无边,因此相应的13名学生中任意两名都没有同桌过,从而Nmax≥13.

另一方面,任取S⊆V,且|S|≥14,则S中的学生没有同桌过,因此他们在圈上都不相邻.

情形一,如果图G是一个圈,则

这显然不成立.

情形二,如果图G不止一个圈,共计k个圈Ci(i＝1,2,…,k),点数记作|Ci|(i＝1,2,…,k),则由不同2个圈没有公共顶点,得

3.3 子集组极值问题

探求一个满足某种条件的集合的子集组中子集的个数最多或最少的问题.

例4给定集合S＝{1,2,3,…,100}.

(1)求最大的正整数n,使得S存在子集组A1,A2,…,An,满足对一切1≤i＜j＜k≤n,都不满足Ai⊆Aj⊆Ak,也不满足Ai⊇Aj⊇Ak;

(2)求最小的正整数m,使得S的任一子集组A1,A2,…,Am,都存在1≤i＜j＜k≤m,满足Ai⊆Aj⊆Ak或Ai⊇Aj⊇Ak.

解析

第(1)问要求最大正整数nmax满足一个存在性量词命题,第(2)问要求最小正整数mmin满足一个全称量词命题,并且mmin＝nmax＋1.

(1)一方面,取S的所有50元子集、49 元子集、51元子集、50元子集排成如下一个子集列:

3.4 度数序列极值

表3

3.5 点列极值

3.6 积集与加集极值

4 实战演练