王慧興(正高級(jí)教師 特級(jí)教師)

(清華大學(xué)附屬中學(xué))

1 內(nèi)容提要

表1

2 重點(diǎn)解析

2.1 容斥原理

有限集合X的元素個(gè)數(shù)記作|X|,則有限集合Ai(i＝1,2,…,n)的并集的元素個(gè)數(shù)算法如下:

所以并集中每個(gè)元素在等式左、右兩邊中被計(jì)入的次數(shù)都是1次,故等式成立.

2.2 集合劃分

集合S的一組非空子集A1,A2,…,Ak滿足Ai∩Aj＝?(?1≤i＜j≤k),并且A1∪A2∪…∪Ak＝S,則稱子集組A1,A2,…,Ak構(gòu)成集合S的一個(gè)k-劃分;在劃分情境下,容斥計(jì)數(shù)原理表現(xiàn)為分類加法計(jì)數(shù)原理:

劃分情境下的子集組A1,A2,…,Ak也稱為集合S的一個(gè)完備子集組,對(duì)任意A?S,都有

全概率公式推理論證與應(yīng)用都要依托于有一個(gè)完備事件組,這個(gè)完備事件組正是基本事件空間Ω的一個(gè)劃分.

2.3 Sperner定理

定理n元集合S＝{1,2,…,n}(n∈N*)的子集組A1,A2,…,Ak,其中任意兩個(gè)都沒有包含關(guān)系,則

2.4 二維表格方法

n元集合S＝{1,2,…,n}(n∈N*)的一組子集A1,A2,…,Ak,記每個(gè)元素i∈S恰好含于ai個(gè)Aj(1≤j≤k),稱ai為元素i關(guān)于該子集組的關(guān)聯(lián)度數(shù),所有關(guān)聯(lián)度數(shù)構(gòu)成一個(gè)度數(shù)序列A:a1,a2,…,an;子集Ai的元素個(gè)數(shù)記作|Ai|,稱為子集Ai的容量;作二維表格,當(dāng)且僅當(dāng)i∈Aj時(shí),在第i行第j列小方格填入1,其他位置不填數(shù)字(默認(rèn)為0).

分別按行、列統(tǒng)計(jì)表中1的個(gè)數(shù)(如表2),或?qū)ΧM(i,Aj)(i∈Aj)計(jì)數(shù),得

表2

2.5 構(gòu)建計(jì)數(shù)對(duì)象

在組合分析中,我們基于組合計(jì)數(shù)構(gòu)建推理論證路徑.為此,求解涉及計(jì)數(shù)對(duì)象問題時(shí),要確立計(jì)數(shù)對(duì)象,這種計(jì)數(shù)對(duì)象有些是問題表征明確的,但更多的是基于問題結(jié)構(gòu)以及數(shù)據(jù)關(guān)系,故要將對(duì)象重組,將構(gòu)建的元素組作為計(jì)數(shù)對(duì)象.重建計(jì)數(shù)對(duì)象既能避免重復(fù)計(jì)數(shù),也是算兩次構(gòu)建計(jì)數(shù)模型的基本策略.

2.6 一個(gè)常用引理

笛卡爾積集由兩個(gè)集合A,B建立有序二元組(a,b)的集合A×B＝{(a,b)|a∈A,b∈B},稱為A與B的笛卡爾積集.很多情境中也表現(xiàn)為如下“加集”與“積集”.一般地,A×B≠B×A,但

引理n元數(shù)集A＝{a1,a2,…,an}的“加集”與“積集”分別定義為

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

(2)當(dāng)A的n個(gè)元素都同號(hào),則|A×A|≥2n－3.

證明(1)不妨設(shè)a1＜a2＜…＜an,則可以列出加集A＋A中的如下互異元素為

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

(2)因?yàn)榘袮中全部元素替換為其相反數(shù),積集A×A不變,而A的元素都同號(hào),所以不妨設(shè)0＜a1＜a2＜…＜an,則可以列出積集A×A中的如下互異元素為

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

3 典例精析

3.1 元素組算兩次

元素組具有算兩次基本屬性,因此,重建元素組并對(duì)元素組計(jì)數(shù)是建立組合情境中數(shù)據(jù)關(guān)聯(lián)的基本策略、方法.

3.2 子集極值

探求滿足特定條件的已知集合的子集中元素個(gè)數(shù)最多或最少的問題.

例2已知集合A＝{1,2,3,…,20},求最小的正整數(shù)n,使得對(duì)于A的任一n元子集W,都存在互異元素u,v∈W,滿足u＋v＝2k,其中k∈N.

必要性:因?yàn)锳有12 元子集W＝{20,19,18,17,11,10,9,3,2,4,8,16},其中任意兩個(gè)元素之和都不是2的非負(fù)整數(shù)冪,所以n≥13.

充分性:下證n≥13都滿足題設(shè)條件,只需證明n＝13是充分的即可.

任取A的一個(gè)13元子集W,必有某個(gè)Ai(1≤i≤8)滿足|W∩Ai|＝2,否則對(duì)一切1≤i≤8,都有|W∩Ai|≤1,應(yīng)用上述A的劃分,得

這顯然不成立,故n＝13滿足題設(shè)條件.

綜上,所求最小正整數(shù)n＝13.

例3一個(gè)班上有26名學(xué)生,每張課桌都坐2名學(xué)生,經(jīng)過一次桌位調(diào)換,使得所有原本同桌的兩人均被分開.求最大的正整數(shù)K,使得學(xué)生無論如何選擇同桌,最后總存在一個(gè)由K名學(xué)生構(gòu)成的集合S,其中任意兩名學(xué)生都未同桌過.

解析

構(gòu)圖G(V,E):V＝{P1,P2,P3,…,P26},其中P1,P2,P3,…,P26表示26名學(xué)生,稱為頂點(diǎn);2名學(xué)生同桌代表這2名學(xué)生的點(diǎn)之間連一條線段,稱為邊,并且調(diào)換桌位前同桌就畫紅線,調(diào)換桌位后同桌就畫藍(lán)線,得到一個(gè)紅藍(lán)二色圖.

性質(zhì)1圖G中每個(gè)點(diǎn)引出2條邊,并且一條紅邊一條藍(lán)邊,我們稱每個(gè)點(diǎn)的度數(shù)為2,記作d(Pi)＝2(1≤i≤26).

性質(zhì)2圖G是一個(gè)圈或幾個(gè)圈,但沒有奇圈,否則圈上就有2條同色邊相鄰,即從一個(gè)點(diǎn)引出2條同色邊,這不可能.

性質(zhì)3頂點(diǎn)集V存在二劃分:V＝A∪B,使得|A|＝|B|＝13,并且A,B各自內(nèi)部的點(diǎn)之間都不連成邊,所有的邊(13條紅邊與13條藍(lán)邊)都在A,B之間相連.

目標(biāo)探究一方面,取S＝A或S＝B,則點(diǎn)集S內(nèi)無邊,因此相應(yīng)的13名學(xué)生中任意兩名都沒有同桌過,從而Nmax≥13.

另一方面,任取S?V,且|S|≥14,則S中的學(xué)生沒有同桌過,因此他們?cè)谌ι隙疾幌噜?

情形一,如果圖G是一個(gè)圈,則

這顯然不成立.

情形二,如果圖G不止一個(gè)圈,共計(jì)k個(gè)圈Ci(i＝1,2,…,k),點(diǎn)數(shù)記作|Ci|(i＝1,2,…,k),則由不同2個(gè)圈沒有公共頂點(diǎn),得

3.3 子集組極值問題

探求一個(gè)滿足某種條件的集合的子集組中子集的個(gè)數(shù)最多或最少的問題.

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

(1)求最大的正整數(shù)n,使得S存在子集組A1,A2,…,An,滿足對(duì)一切1≤i＜j＜k≤n,都不滿足Ai?Aj?Ak,也不滿足Ai?Aj?Ak;

(2)求最小的正整數(shù)m,使得S的任一子集組A1,A2,…,Am,都存在1≤i＜j＜k≤m,滿足Ai?Aj?Ak或Ai?Aj?Ak.

解析

第(1)問要求最大正整數(shù)nmax滿足一個(gè)存在性量詞命題,第(2)問要求最小正整數(shù)mmin滿足一個(gè)全稱量詞命題,并且mmin＝nmax＋1.

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

3.4 度數(shù)序列極值

表3

3.5 點(diǎn)列極值

3.6 積集與加集極值

4 實(shí)戰(zhàn)演練