動機
計數公式是否可靠,取決於其中的對象與所計數的選擇之間的對應是否恰當。有序選取、子集與函數回答的是不同的問題,即使同樣的整數出現在它們的公式中也是如此。基本的做法是:先釐清對象,再判斷各次選擇是否互相獨立、各種情況是否互不相交,或者被禁止的性質是否互相重疊。
定義
定義 2.1.1
(選取與被禁止的性質)
對於整數 與 ,二項式係數 計算 元集合的 元子集個數。不容許重複的有序選取共有 種可能。 的一個排列是該集合到自身的一個雙射;錯位排列是沒有不動點的排列。當每個目標元素至少有一個原像時,稱該函數為滿射。
每個 元子集有 種排列次序,所以 ,其中 。除以 的理據是各纖維大小一致,而不是僅僅因為出現了重複。如果各對象的編碼個數不同,除以單一的因子未必行得通。
定理/命題
定理 2.1.2
(容斥原理)
設 是有限全集 的子集,則不屬於任何 的元素個數為
其中 時的交集取為 。
定理 2.1.3
(錯位排列與滿射)
對於 ,錯位排列的個數為 。對於大小為 的定義域與有標號的、大小為 的目標集,滿射的個數為
其中在計算由空定義域出發的函數時,約定 。
證明思路
證明
(每個元素貢獻一或零)
固定一個元素 ,並設它恰好屬於 個被禁止的集合。當且僅當 是這 個指標的子集時, 屬於 ,所以它對容斥和的總貢獻為 。當 時這個值為 ,否則為 ,恰好計算了被容許的元素。對有限集 把這些貢獻相加即證明該定理,而無須假設被禁止的集合互不相交。
證明透視
交換求和次序完成了全部工作
唯一不明顯的一步,是不再逐個集合閱讀右邊,而是逐個元素閱讀:各指標集的交集大小之和,等於對每個元素數出包含它的交集有多少個。 有限,這個交換才成立。交換之後,多集合的公式就塌縮為單變量的二項式和。空指標集的交集按約定為 ,它提供了數值 1 的那一項;正因如此, 為零的被容許元素保持權重一。證明從未用到被禁止集合互不相交,所以各層次的重疊一次過得到修正。
證明
(由一般公式得到錯位排列與滿射)
對於錯位排列,取全集為 個排列,並令 表示位置 是不動點。固定指定的 個位置後,其餘位置上還有 個排列。這樣的位置集合有 個,於是容斥原理給出該公式。
對於滿射,全集為全部 個函數。令 表示目標 未被取到。漏掉指定的 個目標後剩下 個函數,因為每個定義域元素獨立地在其餘目標中選取一個。同樣把容斥各項按 分組。
若 ,滿射的計數為零:定義域元素較少的函數不可能取遍每個目標。這是對公式結構的檢驗,而不是額外的修正項。
例題詳解
例題 2.1.4
(區分子集與函數)
從七個人中選三名委員:不計次序,所以共有 個委員會。給不同的人分配主席、秘書與司庫:此時職位有標號,共有 種分配方式。如果一個人可以兼任多個職位,則每個職位獨立地從七人中選一人,答案變為 。
例題 2.1.5
(完整的錯位排列計算)
將四封有標號的信放入四個有標號的信封,
最後兩項分別對應三封信固定與四封信固定。三封信固定會迫使第四封也固定,但容斥原理有意保留這些互相重疊的事件;若將它們刪去,抵消就會被破壞。
概念視角分析
把錯位排列看成截斷的指數級數
把公式除以 ,得 ,即 級數的部分和。 之後的交錯尾項絕對值小於 ,所以
於是 是最接近 的整數: 時 ,四捨五入得 。錯位排列佔全部排列的比例趨於 。
例題 2.1.6
(放入有標號盒子的滿射分配)
把五個不同的物件放入三個有標號的非空盒子。一種放法就是從物件到盒子的一個滿射,所以個數為 。如果盒子沒有標號,則每個分成三個非空塊的劃分恰好對應 種標號方式,得到 。非空性使這個除法是均勻的。
以兩種方式計算同一個對象
雙重計數的證明從一個明確定義的有限集出發,再用兩種不同的分解方式計算它的大小。這種論證的力量來自兩次使用的是同樣的對象。如果兩邊計算的是不同種類的有標號或無標號對象,看似成立的恆等式反而可能隱藏著一個遺漏的因子。
例如,計算由一個固定大小的子集與該子集中一個指定元素構成的配對。先選子集,得到其二項式計數乘以它的大小。先選指定元素,則需要從其餘元素中選取一個較小的子集。使這兩個計數相等,就證明了聯繫相鄰二項式係數的那個熟悉的恆等式。指定的元素並非裝飾:它解釋了為甚麼會出現多出來的乘法因子。
另一種有用的雙重計數,是按所選子集中來自兩個不相交總體的元素個數對它進行劃分。從它們的並集中選取子集,給出一個二項式係數。對每一種可行的拆分,把兩個總體各自選取方式的乘積相加,得到相同的總數。這些情況互不相交,因為每個子集都有唯一確定的拆分大小。這證明了二項式卷積恆等式,同時說明了為甚麼只有在把不可能的選取所對應的二項式係數定義為零時,求和範圍才可以安全地包含這些選取。
重複選取與隔板法的對應
容許重複的選取與選取子集是不同的模型。設把一個非負整數總量分配到固定正數個有標號的盒子中。每一種分配是一個非負整數元組,其各分量之和等於該總量。
定理 2.1.7
(隔板法)
設 、 為整數。滿足 的非負整數元組 共有 個。若要求每個 ,當 時共有 個,當 時為零。
證明
(星號與棒號的串對每種分配恰好編碼一次)
用一行 個星號表示各個單位,用 個棒號分隔各盒的內容。相鄰的棒號表示一個空盒,位於兩端的棒號則容許第一個或最後一個盒子為空。這種排列共有 個位置,所以選取 個棒號的位置就計算了這些串。
這個對應是雙射:讀出棒號之前、之間與之後的星號個數,恰好恢復出一個計數元組;由元組構造排列,則恰好恢復出一個星號與棒號的串。這證明了第一條公式。
如果每個盒子必須至少得到一個單位,則先從每個盒子中取走一個單位。映射 是到總量為 的非負元組的雙射。若 為負,則不存在分配方式;否則以總量 應用第一條公式,得到 。
盒子由它們在排列中的次序來標號。去掉標號會把問題變為整數分拆,並使這個直接的公式失效。下界條件是通過一個可逆的平移來處理的,而不是對最終的計數作臨時的扣減。
舉一個具體的例子:把八個相同的單位分配到三個有標號的非空盒子。從每個盒子各取走一個後剩下五個單位,在七個位置中選取兩個棒號的位置,得到 種可能。若是不同的物件,則需要另一個模型:一個計數元組並不說明具體哪些物件進入了每個盒子。這一缺失的資訊正是滿射的例子計數大得多的原因。
為甚麼交錯的符號是必然的
容斥原理看起來像是一條需要記住交錯符號的規則。它的證明給出了更好的解釋。違反若干條件的對象一開始被重複計算過多;減去兩兩的交集可以修正這一點,但隨後會對更高階的重疊修正過度。二項式的抵消對每個單獨的對象同時檢驗了所有這些修正。符號之所以是必然的,是因為要求每個被禁止的對象的淨貢獻為零。
在定義被禁止的性質之前,還應當先確定全集。對於錯位排列,全集中只含有雙射,所以固定若干位置後,剩下的標號構成一個排列。對於滿射,全集包含全部函數,所以漏掉若干目標標號後,每個輸入都有獨立的選擇。混淆這兩種全集會把階乘換成冪,或者反過來,即使完全記住了符號,得到的公式也是錯誤的。
錯位排列的遞推觀點
還有第二種組織錯位排列的方式,與容斥原理互為補充。
命題 2.1.8
(錯位排列的遞推式)
取 、,則對 ,錯位排列數滿足 。
證明
(按第一個標號是否位於二循環分情況)
在 的錯位排列中,像 可以是其餘 個標號中的任何一個。固定 。此時有兩種情況:,構成一個二循環;或 。
在二循環的情況中,刪去標號 與 。其餘 個標號上的排列必須是錯位排列,而且在恢復二循環之後,每個這樣的錯位排列都能被唯一地重建。在另一種情況中,把 從它所在的循環中移走:原來指向 的前驅現在指向 。由於該前驅不是 ,不會產生不動點,於是得到 以外 個標號上的錯位排列。反過來,由這樣的錯位排列出發,把 插入其循環中 的緊前面。這個重建是唯一的,並且屬於第二種情況。
因此,對 的 種選擇中的每一種,這兩種情況共貢獻 。當 時,第一種情況用到 ,即空排列,第二種情況用到 。
這個遞推式可以與交錯和公式作數值上的核對,但雙射論證解釋了它為甚麼必然與之一致。這兩種方法揭示了同一批對象的不同結構。
何時可以用對稱性作除法
有標號盒子的例子之所以除以一個階乘,是因為每個分成固定個數非空塊的無標號劃分恰好對應這麼多種標號方式。每個塊可由它實際包含的元素區分,所以賦予不同的盒子標號會給出全部階乘個互不相同的有標號分配。空塊會破壞這種簡單的均勻描述:交換兩個空的有標號盒子,並不像交換兩個非空盒子的內容那樣改變一個分配。
旁註
追問每個編碼纖維的大小
在作除法之前,先定義那個忘記標號或次序的映射。然後證明每個目標對象都有相同個數的原像。如果纖維大小不一,單一的除數就無法成立。更高等的對稱性方法可以處理穩定子大小不同的情況,但在這裏修正初等的計數模型並不需要它們。
纖維的觀點也是檢驗答案的有用方式。一個被提出的公式在最小的可能輸入下應當合理,在要求不可能滿足時應當為零。這樣的邊界檢驗不能代替證明,但往往能在冗長的算術開始之前就發現錯誤的模型。
常見錯誤
常見錯誤
(把互相重疊的性質的計數直接相加)
相加計數要求各情況互不相交。把 相加,會使每個元素按其具有的性質個數被重複計算,這就是必須修正重疊的原因。反過來,相乘計數要求每一步的選擇個數對此前的每種選擇都是已知的。計數中的獨立性,說的是這些選擇個數的性質,而不一定是概率意義上的獨立性。
常見錯誤
(鴿巢原理證明存在性,而非計數)
鴿巢原理指出,把多於 個物件放入 個盒子,必有某個盒子至少含有 個物件:否則總數至多為 。它證明的是存在性,而不是分配方式的個數。當問題要求精確的總數時,不要用它來代替計數公式。
有標號盒子例子中的除法,是最容易丟掉假設的地方。
反例模式
盒子可以為空時除以標號方式數
斷言:把五個不同物件放入三個無標號盒子、容許空盒的方法數,等於有標號的計數除以 3 的階乘。有標號的計數為 3 的 5 次方,即 243,而 243 除以 6 等於 40.5,不是整數,所以斷言不成立。按非空塊的個數直接計算:分成一塊有 1 種,分成兩塊有 15 種,分成三塊有 25 種,共 41 種。分成一塊的劃分只有 3 種標號方式,分成兩塊或三塊的劃分各有 6 種,確實 3 + 90 + 150 = 243:纖維並不均勻。只有在要求每個盒子非空時,如例題所示,這個除法才成立。
總結
雙射與均勻的編碼計數為乘法和除法提供了理據。容斥原理通過抵消每個對象的多餘貢獻,來計算不具有任何被禁止性質的對象。錯位排列禁止不動點;滿射禁止漏掉目標。
練習
快速檢查
(計算由四個字母構成、長度為六、且每個字母都出現的字串個數。)
各位置不同,字母有標號。
解答 · 答案
一個字串就是從六個位置到四個字母的函數,而要求四個字母全部出現,恰好就是滿射性。個數為 。最後的 項為零。字母容許重複。
快速檢查
(證明任意六個整數中必有兩個,它們的差可被五整除。並解釋為甚麼這個結論沒有指定唯一的一對。)
用餘數類作為盒子。
解答 · 答案
把每個整數放入它模 的餘數類中。六個整數放入五個盒子,必有兩個落在同一類,它們的差可被 整除。可能有幾個盒子各含一對,也可能有一個盒子含有三個或更多個元素,所以這個存在性證明並不斷言唯一性。
快速檢查
(用遞推式計算 ,並以交錯和公式核對。)
遞推式需要 與 。
解答 · 答案
由 、,遞推式給出 、、。交錯和給出 ,兩者一致。