為甚麼計數法則需要模型
題目裏有幾個數字,並不足以證明應該把它們相乘。計數前要先說明一個答案究竟是甚麼,以及一串選擇怎樣確定它。每個合法答案都能產生嗎?不同的選擇過程會產生同一個答案嗎?只有解決這些問題後,計數法則才能回答原題。
分類與纖維
定義 2.4.1
(互不相交分類與纖維)
集合 的子集族 稱為 的一個互不相交覆蓋,如果它們兩兩互不相交且並集是 ;這裏允許成員為空集。對函數 , 上的纖維是 。纖維可以是空集。
定理 2.4.2
(加法法則與纖維法則)
若有限集 有由有限多個集合 組成的互不相交覆蓋,則 。若 是有限集之間的函數,則
特別地,如果每個纖維都有 個元素,那麼 。
證明
(為甚麼沒有遺漏或重複計數)
在加法法則中,各部分覆蓋 ,所以每個元素至少屬於一部分;各部分互不相交,所以每個元素至多屬於一部分。把各部分分別計數並相加,恰好把每個元素數一次。對於纖維法則,每個 恰好屬於以 為標記的纖維。因此所有纖維構成 的互不相交覆蓋,其中允許空纖維。若纖維大小均為 ,相加便有 個相同的項。 時公式仍成立:這時 也必須為空。
映射的方向很重要。從描述到對象的編碼映射可能把多個描述送入同一個纖維。如果每個對象恰有 個描述,就可以把描述總數除以 得到對象數。滿射只保證纖維非空,並不保證纖維同樣大。
例題 2.4.3
(大小不一的纖維不能統一相除)
設描述是 ,函數 把 送到 ,把 送到 。共有五個描述和兩個對象,纖維大小分別為 和 。將五除以 或 都得不到對象數;正確的關係是 。必須先證明共同的纖維大小,才有理由用它作除數。
乘法與依賴先前結果的選擇
定理 2.4.4
(有條件選擇的乘法法則)
假設有限構造有 個階段。第一階段有 種選擇;對每個長度為 的合法前綴,第 階段都恰有 種選擇,其中 。則完整合法選擇序列共有 個。當 時,只有一個序列,即空序列,因此空積為 。
可選內容可以依賴先前選擇;每一階段只要求可選項的數目恆定。
證明
(對前綴歸納)
令 為長度為 的合法前綴集, 只含空前綴。刪去最後一步給出從 到 的映射。每個前綴恰有 種延伸,故均勻纖維法則給出 。反覆使用即得乘積。若某個因子為零,就沒有完整序列;如果已經沒有前綴能到達後續階段,關於這些前綴的延伸條件便是真空成立的。
證明透視
均勻延伸數在哪裏用到
證明沿著前綴集 逐步歸納,而假設只在一處進入:截斷映射 的每個纖維都必須恰有 個元素。選擇本身可以隨前綴而改變,纖維法則只看它們的數目。若某個前綴有 種延伸,另一個卻有不同的數目,則 只能寫成對 中各前綴的延伸數求和,即下一段的分支樹計數,而不是乘積。
兩個退化情形不需額外處理便能完成論證。 只有空前綴一個元素,這正是空積等於 的原因。若某個 ,則 ,其後各階段的纖維條件都真空成立,公式正確地給出 。歸納從未用到不同選擇序列給出不同對象;那是另一個問題,由下一節的纖維法則處理。
若後續選擇的數目不恆定,應對前綴求和。設第一步選 之後有 種完成方式,則兩階段序列總數為 。更長的構造也可以看成分支樹:把每個第一分支之下的完整序列數相加。乘法是有關纖維大小相等時的特殊情形。
例題 2.4.5
(限制條件改變分支數)
從 中選不同的數,組成有序對 ,要求 為偶數。若 為奇數, 必須是另一個奇數;若 為偶數, 必須是另一個偶數。四種 各有一種延伸,所以共有 對:。
若改為要求 為奇數且 ,則 時的延伸數分別是 。相加得 ;此時分支數不相等,不能未經證明就用某個分支數乘以 。
例題 2.4.6
(各位不同且個位為偶數的三位整數)
有多少個三位整數的各位數字互不相同,且個位為偶數?首位不能是零。按個位是否為零分類,因為零與非零數字在首位的角色不同。
若個位是 ,百位有 種選擇,十位有餘下的 種選擇,本類共有 個。若個位是 之一,則個位有 種選擇。百位既不能是零,也不能與個位相同,所以有 種選擇;十位可取餘下的任意 個數字,包括零。本類共有 個。
兩類互不相交且覆蓋所有情況,因此總數為 。每類內部的分支數都恆定,但兩類之間不同。先選個位很方便;若把 乘上一個統一的後續選擇數,就會忽略這個分別。
常見錯誤
(以錯誤次序選擇位置)
若先選百位(九種),再選十位(九種),個位餘下可用的偶數個數是五減去前兩位已用的偶數個數,可能是 、 或 ,視先前的選擇而定。最後一個階段寫不出單一因子,所以按這個次序不能用乘法法則;要麼按情況求和,要麼像上例一樣先選受限制的位置。
從序列到對象
例題 2.4.7
(委員會與有序職位)
從六人中選三人組成委員會。先數三個不同人的有序名單:共有 個。把次序忘掉,就得到一個委員會。每個委員會恰有 種排列,因此纖維法則給出 ,委員會數為 。相反,如果三個職位分別是主席、秘書和財務,交換次序會改變任命, 個序列就是不同答案,不應再相除。
反例模式
不能自動假設纖維均勻
兩名不同的人各選三個無標記盒子中的一個,允許空盒。無標記的分配只有兩種:兩人在一起,或者分開。若先給盒子標記,則有 種分配。忘掉標記後,在一起的情況有三個描述,分開的情況有六個。把 除以 得 ,並非 。
應固定一個對象,數清它實際有多少個描述。本例中,兩人在一起時交換兩個空盒的標記不會改變分配。相反,對於非空且彼此不同的塊,每種標記方式都產生不同分配。非空條件解釋了為甚麼相鄰的滿射計數討論中可以除以階乘。
從兩邊計算同一個關聯集合
前面我們把集合分成大小已知的纖維來計數。現在考慮相關的情形:同一個有限有序對集合,可以按第一座標分組,也可以按第二座標分組。兩種劃分都給出正確的計數。把它們並列便得到一個等式,有時不用逐一搜尋各種配置,就能借這個等式排除某些可能性。
假設一群學生報名參加工作坊。我們可以詢問每位學生參加了多少場,然後把答案相加;也可以詢問每場有多少位學生參加,再把答案相加。每次報名在兩種方法中都恰好計算一次,所以總數必須相等,即使兩張清單中的各個數字可能很不一樣。
設定
設 是有限學生集合, 是有限場次集合。關聯集合是任意子集 。我們把 讀作「學生 參加場次 」。每個有序對要麼屬於 ,要麼不屬於,因此同一學生參加同一場次不會被記錄兩次。對 和 定義
稱 為 的左度數, 為 的右度數。二者都可以是 。
命題 2.4.8
(雙重計數)
對有限集合 及任意 ,
推論 2.4.9
(兩邊度數均勻時)
若每個 都滿足 ,則 。若另外每個 都滿足 ,則 。當 時,由此得到 ;當 時,等式只說明 ,不能除以 。
證明
(為甚麼兩個和計算的是同一集合)
令 把 映到 。 上方的纖維是 。由於第一座標固定,映射 給出從 到 的雙射,所以 。
纖維 兩兩不交,因為一個有序對只有一個第一座標。它們的並集是 ,因為每個有序對的第一座標都屬於 。因此纖維計數法則給出 。
對 應用同樣的論證,得到 。
邊界情形無需另作處理:
- 若 ,則 ,所以 。兩個和都等於 :一個是空和,另一個是若干個零之和(若 也為空,則它也是空和)。
- 沒有參加任何場次的學生對應空纖維,貢獻 。
對於推論,常數之和為 。令 的兩個表達式相等,便得 。
概念視角代數
雙重計數就是矩陣求和的兩種方式
把 記為關聯矩陣 :行以 標記,列以 標記,當且僅當 時元素為 。於是 是所有元素之和。各行之和是左度數,;各列之和是右度數,。命題正是結合律 :先加各行總數或先加各列總數,得到的總和相同。
常見錯誤
(兩個和不是兩個階段)
這兩種劃分是切分同一個集合 的不同方式,不是選擇過程中的兩個獨立階段,所以不能把兩個和相乘。我們相加的是各纖維的大小,而這些大小可以隨纖維而改變。
例題 2.4.10
(四位學生,三個場次)
令 ,,並設
左度數。
- Ada 參加 和 ,所以 。
- Bo 參加 ,所以 。
- Cy 參加 和 ,所以 。
- Di 參加 ,所以 。
和為 。
右度數。
- 有 Ada 和 Cy,所以 。
- 有 Ada 和 Bo,所以 。
- 有 Cy 和 Di,所以 。
和為 ,與 一致。
平均數。 右度數的平均值是 ,而在此例中,每個場次確實都有度數 。這是我們從數據中核實的事實,不能僅由平均值推出。左度數的平均值是 ,但沒有學生參加了 場。每個 都是整數,實際取值是 和 。平均數描述的是總數平分後的結果,並不描述任何特定頂點。
反例模式
應該相加時誤用乘法
人們可能會說:「四位學生,三個場次,所以共有 次參加。」但 計算的是所有可能的有序對。其中包括 ,而 Bo 並不參加 。事實上,十二對中有六對不存在。只有當 時,乘積 才等於 。
第二種錯誤朝相反方向發生。假設報名表在 之下把 Ada 列了兩次。數表格的行會得到 ,但關聯集合仍只有 個元素,因為 是同一個有序對。雙重計數說的是集合 ,而不是可能含重複項目的清單。
習題
快速檢查
(四位學生每人恰好參加兩個場次,共有五個場次。證明不可能每個場次都有相同的正整數 位學生。然後給出一個具體安排,使每位學生仍參加兩個場次。)
解答 · 答案
按學生計數得到 。如果每場都有 位學生,按場次計數便得到 ,因此 。由於 ,不存在合適的正整數 ,所以這樣的配置不可能存在。
場次人數不等的安排則可以存在。取學生 和場次 ,使
- 參加 ,
- 參加 ,
- 參加 ,
- 參加 。
每個左度數都是 。右度數分別為 、、、、。它們的和為 ,符合命題。
快速檢查
(設 ,,。計算所有度數,驗證兩個和,並求兩邊的平均度數。說明為甚麼給定的兩個座標纖維劃分都不是等大小纖維。)
解答 · 答案
左度數是 、、、;右度數是 、、。兩個和都等於 。
左邊平均值為 。即使如此, 參加了兩場,而 一場也沒參加。
右邊平均值為 ;能這樣計算是因為 。若 ,右邊便沒有平均值,寫 沒有意義。
兩邊都不均勻:左度數取值 、、,右度數取值 、、。不存在每個場次共有的度數 ,所以本例不能使用等大小纖維法則;不能把平均值當作每個度數。
練習
快速檢查
(有多少個三位十進制數字串的各位互不相同且末位為偶數?允許首位為零。)
先選末位,再檢查前兩位各剩下多少選擇。
解答 · 答案
末位有五種選擇,然後首位有九種,中間一位有八種。每個數字串恰由一個這樣的過程確定,因此總數為 。首位允許為零對九種選擇至關重要;三位整數有不同的限制。
快速檢查
(集合 有 個元素,一個從 到三元素集的函數的纖維大小為 、、。求 ;此函數的纖維大小能相同嗎?)
使用纖維求和,而不是乘法法則。
解答 · 答案
纖維法則給出 ,所以 。已有兩個纖維大小不同,故不可能全都一樣;另外, 也不能被 整除。
快速檢查
(求滿足 且 的整數有序對數目。為甚麼不能把第一步的三個選擇乘以第二步的三個選擇?)
分別數每個 對應的 值。
解答 · 答案
當 時, 分別有 個可能值,故總數為 。 所得的九個有序對會包括 等違反 的對;第二階段的選擇數並不恆為三。
快速檢查
(從空集到三元素集有多少個函數?三個纖維的大小是多少?這個函數是滿射嗎?)
函數須為每個輸入指定一個值;想想沒有輸入時這要求甚麼。
解答 · 答案
恰有一個函數:它是圖像為空集的空函數。它的三個纖維都是空集,纖維大小之和 等於定義域大小。它不是到非空目標集的滿射。這個函數對應一個空的選擇序列;不要把它誤認為空定義域中的一個元素。