Skip to content

定义Definition

整数分拆

Integer partition

把正整数写成若干正整数之和且忽略加数次序的表示。

形式陈述 ​

正整数 n 的整数分拆是正整数的无序多重集合

λ=(λ1≥λ2≥⋯≥λk>0),∑iλi=n.

分拆数记为 p(n),约定 p(0)=1。其普通生成函数为

∑n≥0p(n)xn=∏m≥111−xm

(作为形式幂级数理解)。Ferrers 图把第 i 行画成 λi 个点;转置图给出共轭分拆,从而“恰有 k 个部分”的分拆与“最大部分为 k”的分拆等势。

直觉

整数分拆只记录各部分大小及其重数,不记录排列次序,因此 3+1 与 1+3 是同一对象。Ferrers 图把部分画成行长,使“部分个数”和“最大部分”通过转置互换。局部限制常在图形转置或生成函数乘积中变成另一种等价限制。

例子与边界

整数分拆把一个整数写成无序正整数和;集合划分保留底层元素的标签,第二类 Stirling 数计数其中恰有指定数量非空块的划分。集合划分的块无序,块内元素则可区分。

4 有五个分拆:4、3+1、2+2、2+1+1、1+1+1+1。

无限乘积在每个固定次数只涉及有限多个因子,因此形式幂级数意义良好;在 |x|<1 内,它还定义解析函数。

以 5 的分拆观察共轭:恰有两个部分的分拆为 4+1 与 3+2,转置 Ferrers 图后分别得到 2+1+1+1 与 2+2+1。后两者的最大部分恰为二,直接展示了部分个数与最大部分的交换。同一转置也把“部分数至多 k”与“最大部分至多 k”对应起来。

定义要求每个部分为正。若用零补齐表示,例如把 (3,1) 写成 (3,1,0),尾零不算作部分,也不产生新的分拆;分拆的长度始终是正部分的个数。分拆 0 采用空分拆,正好解释 p(0)=1。

推论与应用

自然数的无序加法分解可用普通生成函数 ∏k≥1(1−xk)−1 编码,每个因子选择部分 k 的重数。整数分拆连接对称函数、表示论、统计物理中的能级占据计数以及模形式中深刻的恒等式与同余性质。

在对称函数与 Schur 基中,大小为 d 的分拆标记次数 d 的基向量。变量数 n 只允许长度至多为 n 的分拆;达到 n≥d 后,所有分拆都已出现,所以稳定齐次空间的维数就是 p(d)。三次部分的 (3),(2,1),(1,1,1) 给出三个基向量,也解释两变量特化为什么会丢掉最后一种类型。

参考资料
  • Richard P. Stanley, Enumerative Combinatorics, Vol. 1, 2nd ed., Cambridge University Press, 2011,Ch. 1, partitions, Ferrers diagrams, and generating functions。
  • Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009,Ch. I, generating functions for partitions。
关系图谱7 个相邻概念 · 2 类关系

拖动节点调整位置。

显示关系

显示:依赖

  1. 前置三跳
  2. 前置二跳
  3. 前置一跳
  4. 当前条目
  5. 后续一跳
  6. 后续二跳
  7. 后续三跳
文字版关系按与当前条目的最短距离分组
类型化关系