动机
对整数作分拆不同于对带标号的集合作分拆。整数记录的是不可区分的单位,因此其加数的顺序被舍去。图示可以把这种顺序的丢失精确化,并揭示一种有用的对称性:交换行与列,就交换了部分的个数与最大部分。
重数给出第二种描述。它使母函数的出现变得自然,因为选择每种大小出现多少次,与选择其他大小的出现次数是相互独立的。无穷乘积是形式的:任何一个系数只会受到有限多个因子的影响。图中的一个方阵随后给出一种不那么显然的分解,把分拆分成两个更小的受限分拆。
下文所有计数、图示映射与乘积恒等式均已证明。
定义
定义 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 方阵给出第二种完整的分解,而其系数算法依赖于正确的、不受限制的重数的更新顺序。
练习
快速检查
(数出八恰好分成三个正部分的分拆。把它们与五至多有三个部分的分拆联系起来,并列出结果。)
在加回一之前,先用零补足。
解答 · 答案
五的至多有三个部分的分拆是 。补足到三项并加一,得到 。由已证明的双射可知,这就是所要求的全部五个分拆,而不是假定一个简短的清单已经穷尽。
快速检查
(求计数六恰好有两个部分的分拆的系数。给出它们的共轭,其最大部分恰好为二。)
把直接枚举与恰好长度的母函数表达式作比较。
解答
两个部分的分拆是 。减一后得到总和为四、至多有两个部分的分拆,其级数为 。其四次系数计数的是大小为一和二的部分所满足的无限制重数方程的解的个数,等于三。等价地,恰好长度的级数是 ,其六次系数为三。
其共轭是 ,每个的最大部分恰好为二。它们的唯一性与完备性由共轭的对合性得出。
快速检查
(证明:每个部分至多出现两次的分拆,与没有部分被三整除的分拆,个数相等。)
使用形式消去,或把二进制重数双射改为三进制;给出一个可逆的构造。
解答
从一个各部分都不被三整除的分拆出发。对每个部分大小 ,把它的重数按三进制展开。第 位上的数位零、一或二,产生同样多个大小为 的部分。每个正整数都唯一地分解为三的幂乘以一个不被三整除的数,所以输出中每个大小至多使用两次。反过来作这个分解,就恢复原来的重数和总大小。
同一恒等式为 ,只需把每个因子写成 并逐个系数地消去即可得到。这两种论证证明的都是个数的完全相等,而不仅仅是对小例子的核对。