動機
許多計數問題都在問:從一個較大的集合中選取若干個對象,若選取次序不重要,有多少種選法?例如從一群人中選出委員會、選出二進制字串中放置 的位置,或在乘積中選出提供某個變量的因子。這些問題的數學形式相同:它們都在計算指定大小的子集數目。
本章直接把二項式係數定義為這類子集的數目。階乘公式因而是一個我們要證明的定理,而不是定義。這種選擇很重要,因為以下每個恆等式首先都是關於集合的陳述。每個證明都會展示一個雙射、把集合分成互不相交的情況,或用兩種方法計算同一個集合。代數運算只在由這些計數推得時才使用。
下文以 表示集合 ,並取 。對有限集 , 表示其元素個數。我們使用兩個基本計數原理:
- 加法原理。 若有限集是兩兩不相交的部分之並集,則其大小等於各部分大小之和。
- 乘法原理。 若一個選擇分階段作出,且每階段的選項數不依賴先前的選擇,則選擇總數等於各階段選項數的乘積。
定義
定義 2.5.1
(二項式係數)
令 , 為任意整數。固定一個滿足 的集合 。二項式係數 ,亦記作 ,是滿足 的子集 的數目。這樣的子集稱為 的 元子集。
以下兩點使這個定義更精確。
首先,這個數目與所選定的 元集合 無關。雙射 透過 把 的 元子集映至 的 元子集,而 給出其逆映射。因此我們總可以取 。
其次,定義容許 為任何整數。 元集合的子集大小既不能為負,也不能大於 。因此
這是超出範圍時取零的慣例。在這裏,它是定義的結果,而非額外規則。它讓我們可以對所有整數 求和而不必另列邊界情況,因為只有有限多項非零。
定義 2.5.2
(階乘與下降乘積)
對 , 是乘積 。當 時,這是空乘積,等於 ,所以 。對 ,下降乘積 恰有 個因子。當 時,它是空乘積,等於 。
定理 2.5.3
(階乘公式)
對整數 ,
證明
(計算有序選取)
令 為由 中互不相同的元素組成的有序 元組 的集合。我們用兩種方法計算 。
直接計算。 選擇 有 種方法。然後選擇 有 種方法,因為它必須與 不同。如此繼續,最後選擇 有 種方法。由乘法原理,
最後的等式成立,是因為 。
經由子集計算。 把每個元組映至其所有項組成的集合 。由於各項互不相同,這是一個 元子集。反過來,每個 元子集 恰好來自所有以某個次序列出 中元素的元組。由乘法原理,這些排列有 種。因此,元組分成 組互不相交的組別,每組大小為 。由加法原理,。
比較兩次計數得到 。除以正整數 即得公式。這個除法在有理數中進行,因此是合法的。
邊界情況。 若 ,集合 恰有一個元素,即空元組。它對應唯一的 元子集 。兩種計數均為 ,與 一致。若 ,則必有 ,而 ,因為 恰有一個子集,即其自身。以上論證無須修改,已涵蓋這兩種情況。
定理 2.5.4
(對稱性)
對 及每個整數 ,有 。
證明
(補集)
映射 把 元子集映至 元子集。連續應用兩次便得到原來的集合,所以它是 元子集與 元子集之間的雙射。若 或 ,則分別有 或 ,故兩邊均為 。此時雙射的說法仍然成立:它是兩個空族之間的雙射。
定理 2.5.5
(帕斯卡法則)
對 及每個整數 ,
證明
(指定元素)
計算 的 元子集 ,並把 指定為特別考慮的元素。每個這樣的 恰好屬於以下兩種情況之一。
- 。 此時 是 的 元子集。反過來, 的每個 元子集都是這樣的 。此情況貢獻 個子集。
- 。 移除 後得到 的 元子集 。逆映射是 。此情況貢獻 個子集。
兩種情況互不相交,因為一個元素不可能同時屬於及不屬於 ;它們亦涵蓋所有情況。加法原理給出此恆等式。
邊界值。 即使某個族為空,雙射仍然有效;但直接檢查極端情況亦有幫助。
- 若 ,三項均為 。
- 若 ,恆等式為 。唯一的 元子集不含 ,而大小為 的子集不存在。
- 若 ,恆等式為 。全集包含 。
- 若 ,各項均為 。
二項式定理
令 為具有單位元 的交換環。對 和非負整數 , 表示 ,共有 個加數,其中 。此外,,即空乘積。不需要除以 ,而這種除法一般亦未必可行: 可能沒有充當 的元素。
定理 2.5.6
(二項式定理)
對交換含幺環 中可交換的元素 及每個 ,
證明
(組合模型及歸納)
模型。 把 寫成 個因子的乘積。反覆使用分配律,可將其展開為 個字詞 的和,其中每個 均為 或 。令 為滿足 的位置所組成的集合。由於 與 可交換,可以重排字母,因此該字詞等於 。字詞與子集 一一對應。當中恰有 個滿足 ,把它們合併便得到係數。以下歸納證明同一結果,無須依賴關於「展開」的非形式推理。
基礎情況 。 左邊是空乘積 。右邊是 。
歸納步驟。 假設命題對 成立。把求和範圍保持為 ,使以下每個冪的指數均非負:
第一個和中的每項乘以 後得到 。代入 。第二個和中的每項乘以 後得到 ,此步使用了 。由分配律可知,整數倍與每個環元素可交換,因此係數不會造成困難。代換後,兩個和為
為了把兩個和都寫成相同的範圍 ,我們在第一個和加入 項,並在第二個和加入 項。兩個加入的項之係數都是 ,而所有涉及的指數均非負。合併兩個和,再應用帕斯卡法則,得到
這正是 的命題,完成歸納。
證明透視
交換性與零約定在哪裏進入
這個歸納只有一步真正不平凡,另有兩個假設在明確的位置使用。這一步是在第一個和式中作指標平移 等於 加一,使兩個和式對齊,帕斯卡法則才可以逐個係數地合併它們。交換性只用了一次:把 乘 的 次方改寫為 的 次方乘 ;其他地方因子的次序都無關緊要。範圍外為零的約定則用來把兩個和式延伸到共同範圍 0 至 加一而不改變其值,使帕斯卡法則在兩個端點也可使用。合併後的係數恰好就是 加一時的結論,基礎情形則是空積,論證因此閉合。下面的反例拿走交換性那一步,說明其他條件都不能代替它。
此證明依賴所選元素滿足 。沒有這個關係時,上述恆等式可能失效,如以下例子所示。
反例模式
不可交換的矩陣
在實數 矩陣環中,令
則
所以 。此外,,且 ,故 。另一方面,
正確的展開式是 。兩個混合乘積是不同的矩陣,不能合併為 。
從子集得到的恆等式
定理 2.5.7
(行和與奇偶性)
對 ,。對 ,
證明
(兩種計數及切換雙射)
行和。 我們用兩種方法計算 的子集。首先,由乘法原理,對 個元素各自獨立決定放入或不放入,可得到 個子集。其次,由加法原理,按大小分組得到 。當 時,兩種計數均為 ,因為 是唯一的子集。
奇偶性,。 固定元素 ;因為 ,此元素存在。定義切換映射 :若 則移除 ,否則加入 。於是 ,所以 是 的子集族到自身的雙射。它使 恰好改變 ,因此反轉奇偶性。故 限制為偶數大小子集到奇數大小子集的雙射。兩個族大小相等,合起來包含全部 個子集,所以各有 個元素。
的情況不同。 偶數項之和為 ,奇數項之和為 。沒有元素可供切換,因此該雙射不存在。從代數角度看,在二項式定理中代入 、 得 。當 時這是 ,但當 時它是空乘積 。
定理 2.5.8
(加權和)
對 ,。對 ,此和為 。
證明
(計算有序對)
令 為所有滿足 及 的有序對 所成的集合。可把 想成委員會, 想成其主席。
先選委員會。 一個 元子集 有 個可能的主席。按大小求和得到 。
先選主席。 選擇 有 種方法。委員會的其餘成員是剩下 個元素的任意子集 ,而 。因此 有 種選法,所以 。
兩種計數描述同一個有限集,所以相等。當 時,沒有任何這樣的有序對,和為 。在此情況下,表達式 不是對任何事物的計數,這就是我們另列 的原因。
定理 2.5.9
(范德蒙(Vandermonde)恆等式)
對 及每個整數 ,
證明
(拆分委員會)
令 與 為互不相交的集合,且 、。計算 元子集 ,其數目為 。
每個 決定數目 ,它屬於 。不同的 值給出互不相交的情況,合起來涵蓋每個 。
固定 。映射 是到以下有序對所成集合的雙射:第一項是 的 元子集,第二項是 的 元子集。其逆映射是 。由於 ,這個逆映射是單射:可從並集以 和 還原 和 。由乘法原理,此情況包含 個子集。再由加法原理得到恆等式。
若 或 ,該項為 ,正確地計算了不可能發生的情況。若 或 ,每一項均為零,右邊亦為零。
取 和 ,並利用對稱性 ,得到
在范德蒙恆等式的證明中,選出的 是單一的無序集合。拆分 記錄每個成員來自哪一個原有組別;它沒有施加次序,也沒有創造新對象。集合 和 是固定且有標記的,因此有序對 定義明確。
概念視角代數
把范德蒙恆等式看成多項式的乘積
同一恆等式也是係數比較。由多項式環 中的二項式定理,
左邊 的係數收集所有 的乘積,正是范德蒙恆等式中的和;右邊則是 。雙射證明中的拆分 ,在這裏變成第一個因子貢獻的指數。
例題
例題 2.5.10
(從 人中選出 人)
從 位數學家和 位物理學家中選出 人。按選出的數學家人數 分情況:
各項對應 ,即 。總數與 一致。
例題 2.5.11
(帶指定成員的三元子集)
以 6 為指定元素,帕斯卡法則給出 。 的 元子集中,十個不含 ,十個包含 。
現在計算滿足 、 的有序對 。先選委員會得到 。先選主席:選擇 有 種方法,再從其餘 個元素中選出 名成員有 種方法,得到 。兩種計數一致。
例題 2.5.12
( 的一行與奇偶性)
當 時, 的值是 ,其和為 。偶數 的項之和為 ,奇數 的項之和為 。兩者均等於 。
以固定元素 定義的切換映射說明了此雙射。例如,它把 ,並把 。
例題 2.5.13
( 時的平方和)
的值是 。其平方和為 ,而 。項 等於 。它計算一個 元集合的 元子集,其中恰有一個元素來自前半組、兩個來自後半組。
常見錯誤
反例模式
把重疊的情況相加
計算 中包含 或 的 元子集。包含 的有 個,包含 的也有 個,但答案不是 。子集 同時屬於兩種情況,因而被計算了兩次。
正確的列表是 ,共有 個元素。容斥原理給出相同結果:。用補集也一樣:,因為只有 同時不含這兩個元素。加法原理要求各情況互不相交。帕斯卡法則和范德蒙恆等式的證明之所以有效,是因為其情況由單一值決定:一個元素是否屬於集合,或數目 。
常見錯誤
(有標記與無標記)
計算從 人中選出「A 隊」的方法數,其餘人組成 B 隊。它並非把 人分成兩個無標記二人組的方法數。每種無標記分組對應兩種有標記的選擇,所以只有 種分組。
常見錯誤
(在 時使用奇偶性結論)
奇偶性恆等式需要一個可供切換的元素,因此不適用於 :此時偶數項之和為 ,奇數項之和為 。
常見錯誤
(在環中除以 )
在二項式定理中,係數以整數倍的方式作用於環元素。從不需要在 中除以 ,而且這可能不可行。
習題
快速檢查
(分別從定義和階乘公式計算 。)
數一數空集的子集。
解答 · 答案
空集恰有一個子集,即 本身,其大小為 。所以 。利用空乘積 ,公式給出 。
快速檢查
(求 ,並驗證 、 時的帕斯卡法則。)
利用範圍外為零的約定。
解答 · 答案
沒有子集有 個元素,所以 。帕斯卡法則此時為 ,即 。 唯一的 元子集是 ,它不含元素 。
快速檢查
(分別計算 和 時的偶數項及奇數項行和。)
檢查是否有可供切換的元素。
解答
當 時,偶數項之和為 ,奇數項之和為 。兩者不相等,因為沒有元素可供切換。
當 時,偶數項之和為 ,奇數項之和為 。兩者均等於 。切換映射交換 和 。
快速檢查
(直接計算 ,並與加權和公式比較。)
利用第四行 。
解答 · 答案
。公式給出 ,兩者一致。
快速檢查
(求 中 的係數。)
把 的指數與 對應。
解答 · 答案
在形式 中,我們需要 和 。係數為 。
快速檢查
(驗證 、、 時的范德蒙恆等式。)
對 求和。
解答 · 答案
,而 ,兩者一致。
快速檢查
(驗證 時的平方和恆等式。)
利用第二行 。
解答 · 答案
,而 ,兩者一致。
快速檢查
(對 和 ,證明 及 。)
逐個元素計算各個乘積。
解答
兩個乘積是
所以 。接著,,因此 。平方為 及 ,所以
兩者之差是 。這與正確的展開式 一致。