若一個對象可以同時違反多個條件,分別減去每個壞集合時,它便會被減去多次。容斥原理透過追蹤單個對象的貢獻來修正,而不依賴只有特定區域數目的圖。
計算用盡所有標籤的分配
定義 1.1.1
(滿射分配)
從任務集合到標籤集合的函數,若每個標籤都至少被一個任務使用,便稱為滿射。
例題 1.1.2
(四個任務與三個標籤)
四個互異任務各分配三個互異標籤之一,有多少種分配用盡三個標籤?不加限制共有 種。令 為完全沒有使用第 個標籤的分配,。答案是 的補集大小。
每個 有 個元素;任意兩集合的交集只有一種分配,即所有任務使用剩下的標籤。三者交集為空:四個任務不可能在沒有任何可用標籤時完成分配。因此
這裏 ,無須約定 。任務與標籤均可區分:改變哪個任務取得某標籤,或交換兩個標籤,均得到不同分配。
一般公式與邊界情況
定理 1.1.3
(滿射數目的交替和)
對 個互異任務及 個互異標籤,從任務集合到標籤集合的滿射數目是
若 ,此數為零。
證明
(每個函數貢獻一次或零次)
對標籤集合 ,令 為完全不使用 中任何標籤的函數集合。若 ,每個任務可取其餘 個標籤之一,故 。對全部 個大小為 的 求和,便得到第 項 ,整個式子就是 。
現在固定一個函數,設它沒有使用的標籤共有 個。它屬於 ,恰好當 包含於這 個未使用的標籤之中;大小為 的這類 共有 個。若 ,只有 符合,該函數恰貢獻 。若 ,它的總貢獻為
因此,這個和對每個滿射恰好計一次,對其他函數計零次,即使多個壞集合互相重疊亦然。若 ,答案為零有直接的理由:每個任務最多提供一個標籤,不可能出現全部 個標籤。即使公式中的個別項不為零,其總和仍須與這個論證一致。
證明透視
為何修正不能止於兩兩交集
這個證明把計數由集合改為逐一檢視對象:不去量度交集的大小,而是問同一個函數被計算了多少次,答案由二項式定理給出 。交替和的每一項都在修正前面各項。過早停止一般是錯的:恰好缺少三個標籤的函數,在兩兩交集項之後的貢獻為 ,即它雖然不是滿射仍會被計算。在四個任務、三個標籤的例子中,沒有函數缺少三個標籤,所以最後一項為零;有四個或更多標籤時,這一項不能省略。
例題 1.1.4
(任務少於標籤)
取 個任務及 個標籤。和為 。大部分項並不為零,但總和與直接論證一致:兩個任務不可能用盡三個標籤。
例題 1.1.5
(五個任務與四個標籤)
和為 。直接驗算:恰有一個標籤被使用兩次,故先選出共用同一標籤的兩個任務,有 種;再把四個標籤一一分配給所得的四組任務,有 種;。
常見錯誤
(不可只減去單一標籤缺失)
太小。只使用標籤 1 的分配同時缺少標籤 2 和 3,因此被減去兩次。三個兩兩交集各補回一個分配,得到 。若把整個修正項的正負號反轉,或把標籤視為不可區分,便是在計算另一個問題。
練習
快速檢查
(由 構成的長度三字串中,有多少個使用全部三種符號?)
解答 · 答案
每個符號恰出現一次,故有 個;容斥亦給出 。
快速檢查
(從兩元素集合到三元素集合有多少個滿射?不用交替和解釋。)
解答 · 答案
零個:兩個輸入無法產生三個不同輸出。
快速檢查
(四個互異任務分配兩個互異標籤,有多少種分配使用兩個標籤?)
解答 · 答案
共有 種;排除兩種常值分配,餘 種。