“这七种整数分拆,所以 $p(5)=7$。随着 $n$ 增大,逐个列举很快变得不现实。Hardy–Ramanujan 公式不负责列举,而是给出分拆总数的精确主导增长规律:”
形式陈述
正整数
分拆数记为
(作为形式幂级数理解)。Ferrers 图把第
直觉
整数分拆只记录各部分大小及其重数,不记录排列次序,因此
例子与边界
整数分拆把一个整数写成无序正整数和;集合划分保留底层元素的标签,第二类 Stirling 数计数其中恰有指定数量非空块的划分。集合划分的块无序,块内元素则可区分。
无限乘积在每个固定次数只涉及有限多个因子,因此形式幂级数意义良好;在
以
定义要求每个部分为正。若用零补齐表示,例如把
推论与应用
自然数的无序加法分解可用普通生成函数
在对称函数与 Schur 基中,大小为
若同时限制部分数至多
形状与增长记录
分拆只规定格子的位置,还没有给格子填标签。Young表在形状上增加行、列比较规则;保留标签不超过
参考资料
- 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。