動機
對整數作分拆不同於對帶標籤的集合作分拆。整數記錄的是不可區分的單位,因此其加數的次序被捨去。圖示可以把這種次序的流失精確化,並揭示一種有用的對稱性:交換行與列,就交換了部分的個數與最大部分。
重數給出第二種描述。它使母函數的出現變得自然,因為選擇每種大小出現多少次,與選擇其他大小的出現次數是互相獨立的。無窮乘積是形式的:任何一個係數只會受到有限多個因子的影響。圖中的一個方陣隨後給出一種不那麼顯然的分解,把分拆分成兩個更小的受限分拆。
下文所有計數、圖示映射與乘積恆等式均已證明。
定義
定義 2.9.1
(整數分拆及其圖示)
非負整數 的一個分拆,是一個有限的非遞增列表 ,其各項之和為 。其長度為 ,最大部分為 。零的唯一分拆是空分拆;其長度與最大部分都取為零。記 為全部分拆的個數。
Ferrers 圖在第 行有 個左對齊的格子。其共軛的各部分為 。重數 是等於 的部分的個數,因此 。
記 為最大部分至多為 的分拆的個數,並規定 ,而對正整數 有 ;另記 為 恰好有 個部分的分拆的個數。部分都是正的,所以一個給定的分拆只用到有限多個非零重數。形式變量 記錄總大小;第二個變量 可以記錄長度。
Durfee 邊長是滿足 的最大整數 ,即圖中左上角最大方陣的邊長。對於空圖,它為零。由其極大性可知,該方陣下方的每一行,其長度至多為 。
定理/命題
定理 2.9.2
(共軛與減一給出精確的限制映射)
共軛是保持大小的對合。它交換部分的個數與最大部分。因此,至多有 個部分的 的分拆,與最大部分至多為 的分拆個數相等。
對於 且 ,恰好有 個部分的 的分拆,與至多有 個部分的 的分拆一一對應。當 時,不存在這樣的分拆。恰好零個部分只在 時出現。
定理 2.9.3
(形式母函數乘積與奇部/相異部相等)
分拆級數及其按長度的細化為
最大部分的上界 把第一個乘積截斷到 。重數的上界則把對應的因子換成相應的有限幾何和。此外,在每個大小上,由相異部分構成的分拆個數都等於由奇數部分構成的分拆個數,其級數恆等式為
定理 2.9.4
(Durfee 分解給出第二個分拆級數)
每個分拆都可以由其邊長為 的 Durfee 方陣、方陣右側至多有 個部分的一個分拆,以及方陣下方最大部分至多為 的一個分拆唯一地得到。因此
採用空積約定, 項為一。在固定次數下,只有 不超過該次數的指標才可能有貢獻。
證明思路或證明
證明
(轉置與減一映射)
對格子座標作轉置,交換行與列,並保持格子的個數。左對齊以及行長非遞增,使得列長也構成一個非遞增列表。轉置兩次得回原來的格子集合,這就證明了對合性。每一列的格子數至多等於原來的行數,而第一列恰好有這麼多格子;這證明了長度與最大部分的互換。
對於恰好有 個部分的分拆,把它的 個部分都減去一並去掉零。所得的非遞增正整數列表總和為 ,且至多有 個部分。反之,把這樣的列表用零補足到長度 ,再把每一項加一。這兩個操作互為逆運算,包括 時較小的分拆為空分拆的情形。
證明
(重數乘積與奇數/相異部分恆等式)
對於乘積,大小 可以出現任意非負次數,給出因子 。把各因子相乘,就是選定恰好的各個重數,並把它們對總大小的貢獻相加。由於幾何因子的分母常數項為一,它在形式上可逆。對於次數 ,滿足 的因子只貢獻其常數項,這證明了該無窮乘積逐個係數地有良好定義。若每選取一個部分就多保留一個因子 ,由同樣的論證即得二元乘積。整個過程沒有用到 的任何數值,也沒有用到分析意義上的收斂。
相異部分的因子是 。由於 ,消去偶數指標的因子後,在形式上只剩下奇數指標的分母因子。為說明消去是合理的,取定一個所需的次數並保留所有相關的因子;非常數項起始次數高於該次數的未配對因子不影響該次數的係數。有限次的消去證明了在該次數上等式成立,而該次數是任意的。
另有一個直接的雙射。在奇數部分的分拆中,把每個重數寫成二進制。對於二進制中位於第 位的每個非零數位,把奇數部分 的 個副本換成一個部分 。此時各部分互不相同,因為每個正整數都有唯一的二的冪因子和奇數餘因子。反之,把每個相異部分拆成其奇數餘因子的相應個數的副本。對每個餘因子而言,所出現的不同的二的冪恰是它的二進制重數數位,所以兩個映射互為逆映射並保持總和。
證明透視
重數展開提供了可逆的選擇
二進制雙射靠兩個唯一性事實支撐,各自用在一個方向。二進制展開的唯一性使正向映射有良好定義:一個重數只有一組數位,所以輸出是確定的。正整數分解為二的冪乘奇數的唯一性則一身兩用:它使輸出的各部分互不相同,因為來自不同奇數部分或不同數位的乘積各不相同;它也使逆映射能從每個相異部分讀出奇數餘因子與數位位置。總大小保持不變,因為每次替換把 的 2 的 次方個副本換成總和相同的一個部分。母函數的證明以另一條路線得到同一等式:那裏的關鍵一步是有限截斷,它容許逐個次數地約去無窮多個因子。
證明
(去掉並重新接上 Durfee 方陣)
對於 Durfee 分解,去掉左上角的 方陣。其右側剩餘的格子至多佔據方陣的那 行,且長度非遞增。其下方剩餘的各行,由極大方陣的定義,長度至多為 。這恰是所述的兩個受限分拆。
反之,把任一這樣的右側圖附在方陣的各行上,把任一這樣的下方圖放在方陣下方。兩個區域內部的行長都是有序的;方陣的最後一行長度至少為 ,而下方的第一行長度至多為 ,所以它們的交界處滿足分拆條件。不會出現更大的方陣,因為下一行太短。重建是唯一的。方陣貢獻的大小為 ,而共軛使得兩個剩餘區域的母函數都等於截斷到 的乘積。乘法計入了兩個獨立的區域,對唯一的方陣大小求和便證明了該恆等式。
係數表有一個合理的更新次序
命題 2.9.5
(最大部分的遞推式)
對 及每個整數 ,
其中對 規定 。
證明
(按大小為 的部分是否出現劃分)
最大部分至多為 的 的分拆,或者不含等於 的部分,由 計數;或者含有這樣的部分。若這樣的部分出現,則去掉一個副本;剩下的分拆仍可能含有更多的副本,這就解釋了為甚麼該項的下標仍是當前的 。把去掉的副本加回去則是逆運算。
要計算直到大小 的各係數,開始時在零處計數為一,在其他大小處為零。依次處理從一到 的部分大小;對於當前的部分大小,按總和遞增的次序更新各總和,即加上(該總和減去該部分大小)處的計數。較小的總和已經把當前的部分大小計入,恰好對應不受限制的重數。若按總和遞減的次序處理,則反而會施加另一種只許使用一次的限制。對部分大小的外層次序,防止了把相同加數的不同排列當作不同的分拆來計數。
這用到 次加法和 個儲存值。對於 ,每個分拆按非遞增順序寫出後,都是其總和的一個特定的有序分拆,而正整數的有序分拆對應於相鄰單位之間空隙的子集。因此 ,所有表值只需 個位元。所以直接的整數加法對 也給出多項式的位元界。這是一個直到數值指標為止的表,並不聲稱對單個極大指標的請求,其時間是其二進制長度的多項式。
例題詳解
例題 2.9.6
(一個圖示同時展示共軛與兩個 Durfee 區域)
對於 ,總大小為十二。其共軛為 :各列的高度為四、三、三、一和一。長度四與最大部分五互換了。
Durfee 邊長為三。去掉其九個格子後,剩下右側分拆 ,大小為二,以及下方分拆 ,大小為一。兩者都滿足各自的限制,且 。極大方陣條件在第四行不成立,所以邊長不是在所有放得下的方陣中任意選取的。
例題 2.9.7
(二進制重數把奇數部分變為相異部分)
取十一的奇數部分分拆 。三個 3 按二進制展開「三等於一加二」來拆分,得到部分三與六。兩個 1 得到部分二。所得的相異分拆是 。
求逆時,六貢獻兩個 3,三再貢獻一個 3,二貢獻兩個 1。原來的重數恰好恢復。這個映射並不是盲目地把每個重複的對子都替換掉,而不記錄其奇數餘因子;唯一的二的冪分解,才避免了碰撞。
例題 2.9.8
(五的七個分拆,及兩個相等的子族計數)
五的分拆有 、、、、、 和 。因此 。
相異的有 。奇數部分的有 。該雙射分別把這些奇數部分分拆映為 。計數全部分拆與計數某個受限子族,是不同的係數問題,即使同一個乘積構造可以組織這兩者。
概念視角組合
行、重數與方陣區域描述的是同一些帶權對象
共軛改變的是邊界限制,重數按部分大小把選擇分開,而 Durfee 方陣則分離出一個唯一的中心形狀及兩個互相獨立的餘部。每種觀點都保留總大小,並規定了如何重建分拆。正是這一共同的權重,使得各母函數恆等式與精確的限制計數互相一致。
常見錯誤
反例模式
整數分拆不是帶標籤集合的分拆
整數三的分拆有 ,只有三個。帶標籤的三元集合有五個集合分拆:塊大小模式二加一,其單點標籤有三種選擇。這些選擇在整數分拆中是不存在的。各大小模式上的纖維大小不同,所以不存在統一的一個除法,能把帶標籤的計數轉化為整數的計數。
形式乘積並不自動容許代入諸如一這樣的數值:在 時每個因子 都沒有定義。
常見錯誤
(容許零作為部分)
若零是不受限制的部分大小,則 、、 等都會是二的不同分拆, 便是無窮大。部分必須為正;零的空分拆是唯一的例外,它根本沒有部分。
常見錯誤
(至多 個部分與恰好 個部分)
六至多分成兩個部分的分拆是 ,共四個;恰好兩個部分的只有三個。減一映射聯繫的是 恰好 個部分的分拆與 至多 個部分的分拆,而不是 的。
常見錯誤
(使用非極大的方陣)
在 中,角落也放得下一個 方陣。去掉它之後,下方剩下的行是 ,最大部分超過二,所以下方區域不是最大部分至多為邊長的分拆。只有極大方陣(這裏邊長為三)才給出這個分解,並使它唯一。
總結
共軛與減一在部分的各種限制之間給出精確的映射。重數的選擇產生有良好定義的形式乘積,而二進制展開則直接證明奇數部分與相異部分相等。極大的 Durfee 方陣給出第二種完整的分解,而其係數算法依賴於正確的、不受限制的重數的更新次序。
練習
快速檢查
(數出八恰好分成三個正部分的分拆。把它們與五至多有三個部分的分拆聯繫起來,並列出結果。)
在加回一之前,先用零補足。
解答 · 答案
五的至多有三個部分的分拆是 。補足到三項並加一,得到 。由已證明的雙射可知,這就是所要求的全部五個分拆,而不是假定一個簡短的清單已經窮盡。
快速檢查
(求計數六恰好有兩個部分的分拆的係數。給出它們的共軛,其最大部分恰好為二。)
把直接枚舉與恰好長度的母函數表達式作比較。
解答
兩個部分的分拆是 。減一後得到總和為四、至多有兩個部分的分拆,其級數為 。其四次係數計數的是大小為一和二的部分所滿足的無限制重數方程的解的個數,等於三。等價地,恰好長度的級數是 ,其六次係數為三。
其共軛是 ,每個的最大部分恰好為二。它們的唯一性與完備性由共軛的對合性得出。
快速檢查
(證明:每個部分至多出現兩次的分拆,與沒有部分被三整除的分拆,個數相等。)
使用形式消去,或把二進制重數雙射改為三進制;給出一個可逆的構造。
解答
從一個各部分都不被三整除的分拆出發。對每個部分大小 ,把它的重數按三進制展開。第 位上的數位零、一或二,產生同樣多個大小為 的部分。每個正整數都唯一地分解為三的冪乘以一個不被三整除的數,所以輸出中每個大小至多使用兩次。反過來作這個分解,就恢復原來的重數和總大小。
同一恆等式為 ,只需把每個因子寫成 並逐個係數地消去即可得到。這兩種論證證明的都是個數的完全相等,而不僅僅是對小例子的核對。