動機
把五筆互不相同的記錄分成三個非空組,可以有不同含義。如果三組分別叫訓練集、驗證集和測試集,那麼交換組名會改變分配。如果它們只是三個聚類,那麼只需保留各組包含哪些記錄,交換列出的順序並不產生新分組。還有第三種問題:把五枚相同的籌碼放進三個有名稱的盒子。這三種問題都提到「五個對象、三個組」,卻在數不同的東西。
程式通常為每筆記錄儲存一個聚類標籤。把所有標籤一致地重新命名,會改變儲存表示,卻不會改變實際分組。我們先直接數分組,再確定每種分組有多少種帶標籤的表示。由此得到的遞推也展示了動態規劃的一個基本原則:數學上如何分解對象,決定程式該按甚麼順序更新狀態。
定義與邊界情形
定義 1.4.1
(集合劃分與塊)
對整數 ,記 ,並約定 。 的一個集合劃分是一族非空、兩兩不交且聯集為 的子集。這些子集稱為塊。塊沒有名稱,也沒有規定的排列順序。例如, 與 是同一個劃分。
定義 1.4.2
(第二類斯特林數)
用 表示把 恰好劃分成 塊的方法數,稱為第二類斯特林(Stirling)數。即使兩塊大小相同,其中的元素也仍然互不相同。規定
空的子集族是空集的唯一劃分;非空集合不能劃分成零塊。為方便書寫,對負的 也令 ,這並不是在定義具有負數個元素的集合。
定義 1.4.3
(滿射)
滿射 必須使用全部 個輸出標籤。記這種函數的數量為 。當 時,若 ,有一個滿射;若 ,則沒有。當 時,非空纖維 就是標著 的組。忘掉這些標籤,便得到一個集合劃分。
移去最後一個元素,得到遞推
定理 1.4.4
(斯特林遞推)
對 和 ,
結合邊界值,這個遞推唯一確定所有 。
證明
(按最後元素所在的塊分類)
考察指定元素 所在的塊。如果該塊就是單元素集 ,刪除它後剩下的是 的一個 塊劃分。反過來,添加這個單元素塊能唯一恢復原劃分,因此此類貢獻 。
否則,只從該塊中移去 ,保留其中其他元素。剩下一個具有 個非空塊的劃分,同時還記住了 來自哪一塊。反過來,先選 的一個 塊劃分,再選其中一塊,把 放入即可。每個劃分恰有 個可選塊。塊雖然無標籤,但它們是不同的元素子集,因此仍是不同的選擇。此類貢獻 。
兩類互不重疊,因為 所在塊不可能既是單元素塊又不是單元素塊。它們又包含所有劃分,所以相加得到遞推。右邊各項的第一個下標都減小,而初始行已經確定,因此對 歸納就證明了唯一性。
證明透視
遞推證明需要可逆的分類
「把下一個元素放到某處」還不是完整的計數證明。我們分清兩種插入,並說明如何從結果恢復較小劃分以及插入時的選擇。能夠恢復原來的選擇,保證同一類內部沒有重複計數;是否形成單元素塊的區別,則保證兩類之間沒有重疊。
前幾行如下;沒有顯示出來的越界項均為零。
| 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 | 0 | 0 |
| 2 | 0 | 1 | 1 | 0 | 0 | 0 |
| 3 | 0 | 1 | 3 | 1 | 0 | 0 |
| 4 | 0 | 1 | 7 | 6 | 1 | 0 |
| 5 | 0 | 1 | 15 | 25 | 10 | 1 |
例如,。這個等式不僅給出總數,還說明其中七個劃分以 為一塊,另十八個把 放在較大的塊裏。
用標籤連接劃分與函數
定理 1.4.5
(滿射就是給劃分的塊加標籤)
對非負整數 ,
更一般地,對 ,
這裏的 表示從空集到自身的函數數量,不是實數冪的極限。
證明
(帶標籤的塊與像的大小)
給定一個有 塊的劃分,選取從塊集到 的一個雙射,共有 種。把每個元素映到所在塊的標籤,便得到滿射。該滿射的纖維能恢復原劃分及塊的標籤,因此這構成帶標籤劃分與滿射之間的雙射,證明第一個等式。 時,兩邊構造都為空,但仍然唯一。
對第二個等式,按照像的大小 對全部函數 分類。先用 種方式選擇像集,再用 種方式選取到這些標籤的滿射。像集不同,或劃分不同,都會得到不同函數。每個函數又有唯一的像集,所以分類完整。按照前面的約定,等式也包含空定義域和空陪域。
因此, 數的是向 個有名稱的盒子分配元素的所有方式,允許盒子不用。斯特林數則數無標籤且必須非空的塊。二者之間的轉換需要追蹤實際用了哪些標籤,不能直接把總數除以 。
概念視角代數
斯特林數作為基的變換
恆等式 對每個整數 都成立,而 在 時自動為零。兩個次數至多為 的多項式若在無限多個點上相等,它們便相等,所以
當 時即為 。數 就是 在下降階乘基下的座標。
用容斥原理數滿射
定理 1.4.6
(排除缺少輸出標籤的函數)
對所有非負 ,
這裏同樣採用空函數約定 。把這個整數除以 ,便得到 。
證明
(每個函數貢獻一次或零次)
對一個子集 ,避開 中所有標籤的函數共有 個。對所有 把該數量乘以符號 後相加。為了證明這個帶符號的和究竟數甚麼,固定一個函數,令 為它漏掉的標籤集。該函數對總和的貢獻是
若 非空,固定其中一個元素,把不含它的子集與添加它後得到的子集配對,兩者符號相反,故全部抵消。於是恰好每個滿射貢獻一。再按 的大小合併項,就得到定理中的公式。定義域為空時,同樣的貢獻論證仍適用於唯一的空函數;它漏掉全部陪域標籤。
例題 1.4.7
(五筆不同記錄分成三組)
遞推給出 個無標籤分組。給三組指定名稱後有 種分配。容斥原理也給出
相反,五枚相同籌碼放入三個有名稱的非空盒子,只有 個正整數佔用向量。這個數只記錄三組的大小,沒有記錄五筆不同記錄分別屬於哪一組。
反例模式
把所有分配除以階乘可能出錯
對四個元素和兩個標籤,,但 。兩個常值函數都只用一個標籤,表示的是單塊劃分。先去掉它們,才得到 。在滿射上除以 是正確的,因為每個兩塊劃分恰有兩種標籤分配;但除法不會把有空盒子的分配變成兩塊劃分。
更一般地,對 ,一個固定的 塊劃分若用 中的標籤表示,共有 種表示。它依賴於 ,所以對全部函數忘掉標籤時,不同塊數對應的纖維大小並不相同。
指定塊大小時,需要兩種對稱因子
有時要求各組的大小,但組仍然無標籤。用 表示大小為 的塊必須有多少個,其中非負整數 滿足
定理 1.4.8
(具有指定大小分布的劃分)
對於這樣的大小分布,劃分數量為
當 時,空的大小分布計數為一,並規定空乘積等於一。
證明
(分槽與對稱因子)
把 個不同元素排成一行,再按固定順序切成若干位置:先放 個長度一的位置,再放 個長度二的位置,依此類推。原始排列共有 個。忘掉每個位置內部的順序,以及大小相同的位置之間的順序,便得到符合要求的劃分。
固定一個最終劃分。它的 個大小為 的塊可以用 種方式安排到對應位置中;每塊內部的元素還能用總共 種方式排列。這些選擇對不同大小獨立,並且恰好恢復所有產生該劃分的原始排列。因此每個纖維都有相同的分母大小,公式得證。大小不同的塊已經對應不同類型的位置,再額外除以 就會重複消去本來合法的區別。
例題 1.4.9
(分成兩塊為何有七種)
對四個不同元素,兩塊的大小只能是 或 。第一類貢獻 ,也就是選擇哪個元素獨自成塊。第二類貢獻 ,其中兩對元素沒有先後順序。因此 。
同理,六個不同元素分成三個無標籤的二元素塊,共有 種。如果再給三對指定三個名稱,則乘以 ,得到 種。
例題 1.4.10
(按像的大小分類全部分配)
將四筆不同記錄分配給三個可用標籤,允許部分標籤不用。像的大小為一、二、三時,分別貢獻
總和為 。像大小為二的那項不僅選擇分組及其標籤,還要選擇究竟用了哪兩個標籤。漏掉 ,就只數了使用某一對指定標籤的分配。
精確的動態規劃
計算單個 時,如果 ,直接返回零。 或 的邊界也可以直接處理。對 且 ,遞推只依賴上一行,因此只存 個整數單元即可。
def stirling(n, k):
if n < 0 or k < 0:
raise ValueError("n and k must be nonnegative integers")
if k > n:
return 0
if n == 0:
return 1 # Here k is necessarily zero.
if k == 0:
return 0
d = [0] * (k + 1)
d[0] = 1
for i in range(1, n + 1):
for j in range(min(i, k), 0, -1):
d[j] = j * d[j] + d[j - 1]
d[0] = 0
return d[k]
函數假設參數是整數。開始計算第 行時,單元中存著 對應的 。按 遞減更新,便保證讀取 和 時兩者都是舊值。更新寫入的正是 的斯特林遞推。 的單元保持零,最後把 置零,符合非空行的邊界。對 歸納便證明算法正確;第一行的單元素塊正是由初始的 產生的。
算法執行 次整數加法及乘以不超過 的整數的運算,儲存 個整數單元。這是算術運算次數。若要估計位元代價,注意對 有 :按每塊最小元素的遞增次序給塊標號,就把每個劃分單射地編碼為函數 。因此,儲存的計數及更新中的非負項最多需要
個位元。使用基本加法以及乘以 的方法,可得足夠的上界: 次位元運算,整數陣列佔 位元。迴圈下標和輸入本身另有儲存代價。這個較寬鬆的上界沒有假設任意大的整數都能單位時間運算。
執行時間依賴 的數值,而不僅是它的二進制長度。事實上,對 ,精確答案 本身就有 個二進制位。因此,一般不能要求精確輸出算法只用關於 的多項式時間。
常見誤解與適用範圍
常見錯誤
(把塊當作有標籤,或容許空塊)
元素有標號,塊沒有標籤。大小相同的塊仍然是不同子集,但交換它們的列出順序不產生新劃分。定義排除了空塊;若允許任意添加空塊,又不增加額外約定,塊數本身就不再有明確意義。
上的等價關係由其等價類唯一確定,反過來,每個劃分都可透過「屬於同一塊」定義等價關係。因此,等價關係的總數為 ,稱為貝爾(Bell)數。四個元素時為 。這是全部等價關係的計數,並不意味著均勻隨機分配標籤就能均勻抽取等價關係。
常見錯誤
(把精確計數當作數值或抽樣結果)
帶符號公式、固定大小分布公式和動態規劃,透過不同分解來數同一類對象。證明建立的是精確整數等式,沒有證明用浮點數計算很大的交錯和具有數值穩定性,也沒有給出均勻隨機抽取劃分的方法。
練習
快速檢查
(對 ,證明 。解釋為何 必須單獨處理。)
解答 · 答案
當 時,到兩個標籤的函數共有 個。恰有兩個常值函數,其餘全部是滿射。每個兩塊劃分有 種標籤分配,所以 。 時正確地得到零。但 時只有一個空函數,並不是兩個不同的常值函數;又沒有兩塊劃分,所以應單獨規定 。
快速檢查
(對 ,透過描述可能的塊大小,證明 。)
解答 · 答案
先給 塊各放一個元素,已經用了 個元素。唯一剩餘的元素只能把其中一塊擴大到大小二。因此,劃分必有一對元素,其餘全是單元素塊。選擇那一對有 種,而且從結果能唯一找回這對元素。 時得到唯一的單塊劃分,也符合公式。
快速檢查
(六個不同元素中,恰有兩個大小為二的塊和兩個大小為一的塊的劃分有多少個?若再給四個塊分配四個指定的不同標籤,有多少種分配?)
解答 · 答案
大小分布為 ,因此計數為 。雖然大小有重複,但每個劃分包含四個不同的元素子集;把四個指定標籤雙射地分配給它們有 種。於是帶標籤的分配數為 。第二問沒有限制某個標籤必須用於某種大小的塊。
快速檢查
(把內部迴圈改成讓 從一遞增到 。追蹤 這一行,找出第一個錯誤值,並解釋遞推所需的哪個輸入已經被覆蓋。)
解答 · 答案
第三行開始前,陣列是 。遞增更新先寫入 ,再寫入 ,最後得到 。最後一項本應是 。遞推所需的 已被新的 覆蓋。遞減更新則會在修改 前讀到舊值一,使各項始終來自同一個上一行。
快速檢查
(直接求出 、 和 ,再分別核對帶符號公式。解釋為何該公式中的 必須表示一。)
解答 · 答案
從空集到自身有唯一函數,其空像等於空陪域,因此 。空函數不能覆蓋三個標籤,所以 。從三個元素到空集的函數不存在,所以 。
帶符號的和分別是 、 和 。中間的和中,即使沒有可用標籤,該項仍須數到一個空函數:由於沒有輸入,所有關於輸入的條件均自動成立。若令 ,就破壞了這個計數,得到錯誤答案。