Skip to content

整数分拆

Integer partition

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

条目类型
定义

形式陈述

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

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

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

n0p(n)xn=m111xm

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

直觉

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

例子与边界

整数分拆把一个整数写成无序正整数和;第二类 Stirling 数则计数把带标签元素划分为给定数量的非空块。前者不保留元素身份,后者的块无序但块内装的是可区分对象。

4 有五个分拆:43+12+22+1+11+1+1+1。这不同于有序的整数合成,例如 3+11+3 在分拆中相同。共轭把“部分数至多 k”与“最大部分至多 k”对应。无限乘积在每个固定次数只涉及有限多个因子,因此形式幂级数意义良好;把它当作复函数时还需 |x|<1 等收敛条件。若允许零部分,必须先固定部分数,否则会产生无限多冗余表示。

整数 5 有七个分拆:5,4+1,3+2,3+1+1,2+2+1,2+1+1+1,15。其中恰有两个部分的分拆有 4+1,3+2 两个;最大部分恰为二的也有 2+2+1,2+1+1+1 两个,二者由 Ferrers 图转置对应。若把次序计入,3+11+3 分开,得到的是 composition 而非 partition。

推论与应用

自然数的无序加法分解可用普通生成函数 k1(1xk)1 编码,每个因子选择部分 k 的重数。与集合划分不同,整数分拆不保留底层标号元素;它连接对称函数、表示论、统计物理中的能级占据计数以及模形式中深刻的恒等式与同余性质。

参考资料
  • 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。
关系图谱6 个相邻概念 · 2 类关系

拖动节点调整位置。

显示关系

显示:依赖

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