動機
把互不相同的對象放入若干組,並不能僅由各組的大小決定。我們還必須指明哪些標籤出現在同一組,以及各組本身是否帶有名稱。置換的輪換又引入另一種選擇:每個組內部的循環次序。即使參數中出現的是同樣的整數,這些區別也會導出不同的計數序列。
斯特靈(Stirling)數用來整理其中兩種模型。貝爾(Bell)數對所有集合劃分求總和,而指數生成函數則表達帶標籤的塊如何組裝。同樣的數組也出現在多項式恆等式中:在那裏,普通冪與下降階乘以兩種不同的方式計數函數。我們將從被計數的對象出發推導這些聯繫,而不是把這些公式當作互不相關的數表。
定義
定義 2.7.1
(劃分與兩種斯特靈數組)
的一個集合劃分,是由互不相交的非空塊構成的無序集合,且這些塊的並集為 。設 為劃分成 個塊的劃分個數。設 為 上恰有 個互不相交輪換的置換個數,其中每個輪換帶有循環次序,而輪換的整體是無序的。定義 。
約定 ,它們對應空劃分或空置換。對正整數 ,約定 。當 或 時,兩種斯特靈數均取為零。這些約定使遞推式的邊界情形有意義,而無須虛構一個空塊。
定義 2.7.2
(下降階乘與形式指數級數)
令 ,並對 令 。對 令 。對帶標籤的計數 ,其指數生成函數為 ,在此處按實數上的形式級數來理解。把 寫作形式級數。
形式恆等式指係數相等,而不是關於數值收斂的斷言。乘積在每個次數上使用有限卷積。把一個級數代入常數項為零的另一個級數,同樣可以逐個係數地良好定義;這將用來論證貝爾數的生成函數。
定理/命題
定理 2.7.3
(兩個插入遞推式)
對 與 ,
從 到帶標籤的 元目標集的滿射共有 個。因此,對 ,由容斥原理得
必要時採用空定義域的計數約定 。
定理 2.7.4
(貝爾遞推式與指數生成函數)
對 ,
對每個 ,再對所有塊數求和,有
這些都是形式級數恆等式,包括常數項在內。
定理 2.7.5
(兩個互逆的多項式基)
對每個非負整數 ,作為 的多項式恆等式,
因此,第二類數組與帶符號的第一類數組是互逆的基變換。特別地,對 ,
證明思路或證明
證明
(插入最後一個標籤,以及為纖維命名)
在一個劃分中,標籤 要麼自成一個單點塊,要麼屬於其餘 個塊之一。去掉單點塊後得到劃分成 個塊的劃分;否則去掉該標籤後剩下 個塊,並需記錄哪一個塊將重新接收它。這些情形互不相交且可唯一還原,由此證得 的遞推式。
對於置換的輪換,標籤 要麼自成一個輪換,要麼被插入某個已有輪換中、緊接在其餘 個標籤之一的後面。去掉它即還原該插入,並保持輪換個數不變。這兩種情形證明了 的遞推式。插入位置對應的是帶標籤的元素,而不是輪換的個數:每個輪換提供的位置數等於它的長度。
一個滿射把其定義域劃分成非空的纖維,並把互不相同的目標標籤分配給這些塊。每個劃分恰有 種這樣的分配,即使有些塊大小相等也一樣,因為各塊的內容互不相同。容斥原理透過排除未被取到的目標標籤來計數滿射;按可用目標的個數 分組,便得到所示的交錯和公式。
證明透視
刪除操作必須恰好記住重構所需的選擇
兩條遞推式都來自同一步:刪去最大的標籤。它們之所以是等式,是因為刪除恰好配上還原所需的資訊。在集合劃分中,非單點標籤要靠指明 個尚存塊之一來接回;各塊由其內容區分,所以這 種選擇給出 個不同的劃分。在輪換中,標籤要靠指明它的前驅來接回,前驅是 減 1 個標籤之一,每種選擇都給出輪換個數相同的不同置換。因子 與 減 1 的差別全部來自這裏。單點情形是零值約定介入的地方:它使塊數或輪換數減一,而在 等於 0 或 時,相應的項按約定為零或為一,而不需另作論證。滿射公式用的是同一事實,即各塊可以區分,這次是為了使每個劃分恰有 的階乘種標號方式。
證明
(指定標籤所在的塊,以及有序塊)
對於貝爾遞推式,考察含有一個新指定標籤的那個塊。從其餘 個標籤中選出它的 個同伴,再把剩下的 個標籤任意劃分。指定標籤所在的塊與剩餘的劃分可以唯一地重構原對象。對同伴個數求和即證得遞推式。
要證明固定 時的生成函數,先給這 個非空塊排序。若它們的大小為 ,則把標籤分配到這些有序塊中共有 種方式。 中 的係數,恰是對總和為 的所有正整數大小,把倒數階乘權重相加。因此乘以 即得到有序塊劃分的個數;再除以 便忘掉塊的次序。在每個固定次數上,除空情形外,只有 的項起作用。對 求和這些形式恆等式,得到 ,其內層級數的常數項為零。
證明
(按像計數函數,再求逆)
對於第一個多項式恆等式,取正整數 ,計數從 到 元目標集的函數。其定義域的纖維構成劃分成某個 個非空塊的劃分。給這些塊分配互不相同的目標值,共有 種方式。求和即對每個正整數 得到該恆等式,進而得到多項式恆等式,因為非零多項式只有有限多個根。
對於第二個恆等式,把 乘以 ,得到係數遞推式
帶符號的輪換計數滿足完全相同的遞推式和相同的初值,所以由歸納法知兩組係數相等。最後,把第二個多項式展開式代入第一個,比較 的係數,即得逆數組公式。下降階乘構成一組基,是因為它們是次數相繼的首一多項式:比較最高次數得到線性無關,逐次相減得到生成整個空間。
例題詳解
例題 2.7.6
(六個帶標籤對象放入三個無名塊)
首先 ,。因此 。又 ,所以 。給三個盒子命名,則乘以 ,得到 種滿射分配。另一方面,容斥原理給出 ,這驗證了標籤與非空性的處理是一致的。
例題 2.7.7
(貝爾總數與塊大小模式)
由貝爾遞推式得 ,,,以及 。在四個標籤上,塊大小的模式有 、、、 與 。它們各自對應的集合劃分個數依次為一、四、三、六與一,總共十五。僅僅數這五種大小模式,數的是整數分拆,而不是帶標籤元素的集合劃分。
例題 2.7.8
(同樣的塊還帶有額外的輪換次序)
對四個標籤上恰有兩個輪換的置換,類型 的貢獻是:單點有四種選法,其餘標籤上的循環次序有兩種,共八個。類型 的貢獻是三種配對,共三個。所以 ,而 。大小為 的塊有 種循環次序:固定一個標籤作為起點,再排列其餘標籤。正是這些內部次序解釋了兩類斯特靈數之間的差別。
概念視角代數
把整行輪換數寫成一個乘積
輪換遞推式說明每一行都是一次因子的乘積:
因為把第 行的多項式乘以 ,正好重現 。 時乘積為 ,與 一致。把 換成 再乘以 ,便得到帶符號 的下降階乘展開。
為甚麼無名塊仍有均勻的標號計數
集合劃分是無序的,但它的各個塊是互不相同的集合。兩個大小相等的塊並不相同:互不相交的非空塊含有不同的元素。因此,即使若干塊大小一致,給盒子標號時也恰有完整的階乘個分配。這個標號映射的纖維大小是均勻的,這正是除以階乘有效的精確原因。
整數塊大小模式則有意忘掉了更多資訊。一個模式說明每種大小有多少個塊,卻不說明它們含有哪些元素。不同的模式有不同數目的實現方式,四個標籤的例子即說明了這一點。若不另作論證,把帶標籤的總數除以某個統一的模式因子,是無法恢復這些不同重數的。
輪換模型增加的是資訊,而不是忘掉資訊。對固定的集合劃分,在每個塊內獨立地選取一個循環次序。各塊循環次序數目的乘積,就是輪換支撐恰為這些塊的置換個數。對所有劃分求這些乘積之和,便得到無符號第一類數。這解釋了它們之間的關係,卻並未把它們所計數的對象等同起來。
正確理解指數生成函數
指數生成函數中的階乘分母記錄的是標籤的分配。兩個這樣的級數相乘,是把定義在所選互不相交標籤子集上的對象組合起來,從而在所得計數中產生二項式係數。普通生成函數對其背後的計數解釋使用另一套係數規則。在沒有檢驗係數之前,不應把形如有理函數或指數函數的同一套代數運算在兩種模型之間隨意搬用。
項 描述一個非空的帶標籤塊:每個正大小的標籤集上都恰有一種塊結構。去掉常數項,是因為劃分中沒有空塊。外層的指數函數則允許這類塊構成的無序集合。這種描述是證明中顯式的有序塊與階乘論證的簡寫,而不是對它的取代。
在零次,恰有一個由塊組成的空集合。因此,貝爾生成函數與零塊固定的級數,其常數係數都是一。若遺漏這一情形,遞推式在第一個輸入處以及形式指數恆等式都會失效。確定這些係數並不需要任何分析上的收斂問題。
概念視角組合
一種變換改變標籤,另一種變換改變多項式座標
滿射與劃分的差別在於是否給非空纖維命名。置換與劃分的差別在於塊內是否有循環次序。冪與下降階乘則是透過計數像集大小而聯繫起來的多項式基。同樣的數組聯繫著這些描述,但公式相等並不意味著它們的對象可以互換。
精確數表及其計算成本
從前一行計算斯特靈數的一行,依次遍歷所有合法的塊數。兩種遞推式為得到到指定下標為止的各行,都需要二次多項式量級的算術運算;若不再需要更早的項,則只需保留兩行。貝爾數可以透過對每一行第二類數求和得到,也可以由它們自己的遞推式得到。
這裏數的是對不斷增長的整數所做的算術運算次數。對正整數 ,每個劃分都可以編碼為把每個標籤映到其所在塊中最小標籤的函數。該編碼是單射,因為它的非空纖維可以恢復各個塊。因此 ,這給出劃分個數的二進制長度的 界。類似地,輪換計數至多為 。所以,初等的精確整數算術給出多項式位元複雜度的實現,儘管它與數表的運算次數所對應的單位成本界並不相同。
要計算精確計數,無須對形式的貝爾表達式作數值求值。遞推式只使用精確的加法與整數乘法,並自動保持整數性。若用浮點數近似指數函數,則需要另行給出誤差論證,才能透過取整來確認一個係數。
常見錯誤
反例模式
隔板法計數的是另一種對象
的正整數解為 ,共三個。但 。整數解描述的是兩個有名位置上的大小;它們並不說明哪四個標籤出現在一起,而集合劃分的塊是無名的。修正後的模型必須同時記錄標籤的歸屬,以及塊的名稱是否重要。
其餘兩個錯誤涉及符號與約定,而非模型本身。
常見錯誤
(丟掉第一類數的符號)
按冪展開所用的是 ,而不是 。已經有 ,而無符號的一行 會給出 。符號隨 交替變化。
常見錯誤
(容許空塊)
若容許空塊, 就成為 分成兩個塊的劃分, 會變成 而不是 ,而兩個空塊甚至無法區分。不要僅僅為了讓遞推式看起來整齊就允許出現空塊;請使用明確陳述的零值約定。
總結
集合劃分與置換的輪換導出不同的插入遞推式。貝爾數對劃分的各行求和,而帶標籤塊的組裝解釋了它們的指數生成函數。兩類斯特靈數(第一類帶符號)還給出普通冪與下降階乘之間互逆的變換。
練習
快速檢查
(利用計數意義計算 與 。)
指出第二個計數中唯一可能的非單點輪換類型。
解答 · 答案
:從兩個有名盒子的分配中排除兩種常值分配,再忘掉名稱。五個標籤上恰有四個輪換的置換,含有一個對換和三個不動點,所以 。沒有更長的輪換符合這個輪換個數。
快速檢查
(證明 ,並判斷何時不等式嚴格成立。)
把新標籤加為單點塊,並找出該像之外的一個劃分。
解答 · 答案
把新標籤加為獨立的塊,將 的劃分單射到 的劃分中。對 ,標籤 與新標籤同在一塊、其餘標籤均為單點塊的劃分,不在該像之中。因此對 有 。在 時兩者都是一,所以在非負下標中,等號恰好只在此處成立。
快速檢查
(把 展開為下降階乘的組合,並把 展開為普通冪。)
使用第四行,並在 處檢驗這兩個多項式表達式。
解答 · 答案
第二類數的一行給出 。把 相乘得到 ,與帶符號的輪換計數一致。在 處,第一個表達式給出 ,而第二個給出 ,這正是第四個下降階乘的正確值。