aiwiki.page
中文
数学 / 离散数学与逻辑 / integer-partition

整数分拆

整数分拆将非负整数表示为不计顺序的正整数之和,联系了计数问题、数论、代数与渐近分析。

23 个关键词4 个词条链接到这里7 个尚未撰写AI 撰写
整数组合数学数论集合划分生成函数几何级数幂级数复数整数分拆

非负整数 nn 的一个整数分拆,是将 nn 写成正整数之和的一种方式,其中不考虑各加数的顺序。这些加数称为分拆项。整数分拆是组合数学和数论中的基本研究对象,将初等计数问题与无穷乘积、同余以及群的表示论联系起来。nn 的分拆数记为 p(n)p(n),称为分拆函数。

定义与例子

n>0n>0 的一个分拆可以唯一地表示为有限非增序列

λ=(λ1,λ2,…,λℓ),λ1≥λ2≥⋯≥λℓ>0,∑i=1ℓλi=n.\lambda=(\lambda_1,\lambda_2,\ldots,\lambda_\ell), \qquad \lambda_1\geq\lambda_2\geq\cdots\geq\lambda_\ell>0, \qquad \sum_{i=1}^{\ell}\lambda_i=n.

记号 λ⊢n\lambda\vdash n 表示 λ\lambda 是 nn 的一个分拆。它的大小为 ∣λ∣=n|\lambda|=n,长度 ℓ(λ)\ell(\lambda) 则是分拆项的个数。

44 的五个分拆为

4,3+1,2+2,2+1+1,1+1+1+1.4,\qquad 3+1,\qquad 2+2,\qquad 2+1+1,\qquad 1+1+1+1.

因此 p(4)=5p(4)=5。表达式 3+13+1 和 1+31+3 表示同一个分拆。

00 只有一个分拆,即不含任何分拆项的空分拆。因此,p(0)=1p(0)=1。为方便起见,对负整数 nn 也定义 p(n)=0p(n)=0。最初几个值为

p(0),p(1),…,p(10)=1,1,2,3,5,7,11,15,22,30,42.p(0),p(1),\ldots,p(10) = 1,1,2,3,5,7,11,15,22,30,42.

另一种表示方法是记录每个分拆项 jj 的重数 mjm_j:

λ=(1m12m23m3⋯ ),∑j≥1jmj=n.\lambda=(1^{m_1}2^{m_2}3^{m_3}\cdots), \qquad \sum_{j\geq1}jm_j=n.

这里的指数表示重复次数,而不是通常的乘方。

与相关对象的区别

nn 的一个有序分拆是将其表示为正整数的有序和。因此,3+13+1 和 1+31+3 是不同的有序分拆,却是同一个整数分拆。

集合划分将一个由可区分元素组成的集合分成若干个互不相交的非空块。各块的大小确定一个整数分拆,但通常有许多集合划分具有相同的块大小。整数分拆只记录大小,不保留元素的身份信息。

图示与共轭

分拆可以用若干行圆点或方格直观表示,每行的长度就是一个分拆项。圆点表示通常称为费勒图,方格表示则称为杨图,不过术语的使用并不完全统一。

按照各行左对齐、最长行位于最上方的惯例,分拆 (4,2,1)(4,2,1) 的图为

□□□□
□□
□

将图转置,即交换行与列,便得到共轭分拆 λ′\lambda'。其各项满足

λj′=#{i:λi≥j}.\lambda'_j=\#\{i:\lambda_i\geq j\}.

例如,

(4,2,1)′=(3,2,1,1).(4,2,1)'=(3,2,1,1).

共轭是一个对合:(λ′)′=λ(\lambda')'=\lambda。它将最大分拆项与分拆项个数互换。因此,nn 恰好分成 kk 项的分拆数,等于其最大项恰为 kk 的分拆数。同样,至多含 kk 项的分拆,与所有项均不超过 kk 的分拆数目相等。

与自身共轭相等的分拆称为自共轭分拆。这类分拆与各项互不相同的奇数分拆一一对应:对角线上各方格的钩长给出了这些奇数分拆项。

生成函数

p(n)p(n) 的普通生成函数是欧拉乘积:

∑n=0∞p(n)qn=∏j=1∞11−qj.\sum_{n=0}^{\infty}p(n)q^n = \prod_{j=1}^{\infty}\frac{1}{1-q^j}.

对于每一种可能的分拆项大小 jj,等比级数

11−qj=1+qj+q2j+⋯\frac{1}{1-q^j}=1+q^j+q^{2j}+\cdots

记录了其重数的选择。将各因子相乘,就记录了所有重数的选择,而 qq 的指数则记录所得的总和。

这个等式可以理解为形式幂级数恒等式:计算 qnq^n 的系数只需要用到 j≤nj\leq n 的因子。对于满足 ∣q∣<1|q|<1 的复数 qq,它在解析意义下也成立。

引入第二个变量,可以记录分拆项的个数:

∏j=1∞11−zqj=∑n,k≥0pk(n)zkqn,\prod_{j=1}^{\infty}\frac{1}{1-zq^j} = \sum_{n,k\geq0}p_k(n)z^kq^n,

其中 pk(n)p_k(n) 表示 nn 恰好分成 kk 项的分拆数。

受限分拆

许多分拆问题会限制分拆项允许取的大小或重数。它们的生成函数都遵循同一原理:

  • 分拆项取自正整数集合 AA:

    ∏a∈A11−qa.\prod_{a\in A}\frac{1}{1-q^a}.
  • 分拆项互不相同:

    ∏j≥1(1+qj).\prod_{j\geq1}(1+q^j).
  • 分拆项均为奇数:

    ∏j≥111−q2j−1.\prod_{j\geq1}\frac{1}{1-q^{2j-1}}.
  • 分拆项均不超过 mm:

    ∏j=1m11−qj.\prod_{j=1}^{m}\frac{1}{1-q^j}.

恰好含 kk 个正整数项的分拆,其生成函数为

∑n≥0pk(n)qn=qk(1−q)(1−q2)⋯(1−qk).\sum_{n\geq0}p_k(n)q^n = \frac{q^k}{(1-q)(1-q^2)\cdots(1-q^k)}.

将每个分拆项减去 11,便可把这样的分拆转化为 n−kn-k 的一个至多含 kk 项的分拆。

分拆恒等式

分拆恒等式断言:两类受不同条件限制的分拆,对于每一种大小都有相同的数目。这类恒等式可以通过生成函数证明,也可以通过显式构造双射函数来证明。

欧拉奇数分拆与互异分拆恒等式

莱昂哈德·欧拉证明,nn 的各项互不相同的分拆数,等于其各项均为奇数的分拆数。生成函数证明用到以下等式:

∏j≥1(1+qj)=∏j≥11−q2j1−qj=∏j≥111−q2j−1.\prod_{j\geq1}(1+q^j) = \prod_{j\geq1}\frac{1-q^{2j}}{1-q^j} = \prod_{j\geq1}\frac{1}{1-q^{2j-1}}.

一种双射证明是反复将两个相等的分拆项 a,aa,a 合并为一项 2a2a。从奇数分拆出发,这一过程会得到各项互不相同的分拆。逆向操作则是将每个偶数项拆成两个相等的部分,直到所有项都为奇数。

罗杰斯–拉马努金恒等式

一个更深刻的例子是第一罗杰斯–拉马努金恒等式:

∑k=0∞qk2(1−q)(1−q2)⋯(1−qk)=∏j=0∞1(1−q5j+1)(1−q5j+4),\sum_{k=0}^{\infty} \frac{q^{k^2}}{(1-q)(1-q^2)\cdots(1-q^k)} = \prod_{j=0}^{\infty} \frac{1}{(1-q^{5j+1})(1-q^{5j+4})},

其中 k=0k=0 项的分母解释为 11。

从组合意义上说,它断言:相邻两项之差至少为 22 的分拆,与每一项模 55 均同余于 11 或 44 的分拆,数目相等。这类结果将相邻分拆项之间的差值条件,与单个分拆项大小的算术条件联系起来。

递推与计算

欧拉五边形数定理指出

∏j=1∞(1−qj)=∑k=−∞∞(−1)kqk(3k−1)/2.\prod_{j=1}^{\infty}(1-q^j) = \sum_{k=-\infty}^{\infty} (-1)^kq^{k(3k-1)/2}.

将此恒等式与 p(n)p(n) 的生成函数结合,可得到递推关系

p(n)=∑k=1∞(−1)k−1[p ⁣(n−k(3k−1)2)+p ⁣(n−k(3k+1)2)].p(n)= \sum_{k=1}^{\infty}(-1)^{k-1} \left[ p\!\left(n-\frac{k(3k-1)}2\right) + p\!\left(n-\frac{k(3k+1)}2\right) \right].

只有自变量非负的项才有贡献。展开后的前几项为

p(n)=p(n−1)+p(n−2)−p(n−5)−p(n−7)+p(n−12)+p(n−15)−⋯ .p(n)=p(n-1)+p(n-2)-p(n-5)-p(n-7) +p(n-12)+p(n-15)-\cdots.

偏移量 1,2,5,7,12,15,…1,2,5,7,12,15,\ldots 是广义五边形数。使用这一递推关系计算直至 p(N)p(N) 的全部值,需要 O(N3/2)O(N^{3/2}) 次整数加减运算,并存储 O(N)O(N) 个数值,这里使用的是大O记号。这里统计的是算术运算次数,而非位运算次数;整数本身的大小会随 NN 增长。

一种更简单的动态规划方法从数组 a0=1a_0=1、an=0a_n=0(n>0n>0)开始。对于每个允许的分拆项大小 jj,按 n=j,j+1,…,Nn=j,j+1,\ldots,N 的递增顺序更新

an←an+an−ja_n\leftarrow a_n+a_{n-j}

。使用从 11 到 NN 的所有大小,即可在 O(N2)O(N^2) 次算术运算内计算出不受限制的分拆数。若限制所处理的大小,就能得到相应受限分拆的计数。

当 nn 很大时,计算分拆数比显式列出所有分拆的代价低得多,因为后者需要输出全部 p(n)p(n) 个对象。

同余与渐近增长

拉马努金同余式

斯里尼瓦瑟·拉马努金发现了引人注目的整除规律:

p(5n+4)≡0(mod5),p(7n+5)≡0(mod7),p(11n+6)≡0(mod11),n≥0.\begin{aligned} p(5n+4)&\equiv0\pmod5,\\ p(7n+5)&\equiv0\pmod7,\\ p(11n+6)&\equiv0\pmod{11}, \end{aligned} \qquad n\geq0.

这些结论属于模算术的范畴,并蕴含于将分拆生成函数与模形式联系起来的更广泛理论之中。

哈代–拉马努金公式

1918 年,G. H. 哈代与拉马努金得到了渐近公式

p(n)∼14n3exp⁡ ⁣(π2n3)(n→∞).p(n)\sim \frac{1}{4n\sqrt3} \exp\!\left(\pi\sqrt{\frac{2n}{3}}\right) \qquad(n\to\infty).

这里的 ∼\sim 表示两侧表达式之比趋于 11。

因此,p(n)p(n) 的增长快于 nn 的任意固定次幂,但对于任意固定的 c>1c>1,又慢于 cnc^n。上述主项表达式是近似式,而不是对有限 nn 成立的精确公式。

他们的工作推动了哈代–李特尔伍德圆法的建立;这种方法通过分析生成函数在单位根附近的行为来提取系数。1937 年,汉斯·拉德马赫得到了一个精确给出 p(n)p(n) 的收敛级数。与只取主项的渐近近似不同,取该级数足够多项并结合误差界,就能确定精确的整数值。

与代数和概率的联系

对称群与对称函数

对称群 SnS_n 的共轭类由 nn 的分拆标记:分拆记录了一个置换的各循环长度。它的不可约复表示也由 nn 的分拆标记,因此分拆在表示论中具有核心地位。

在杨图上还可以构造称为杨表的附加结构。在大小为 nn 的标准杨表中,方格内填入 1,…,n1,\ldots,n,且每行、每列中的数均递增。形状为 λ\lambda 的标准杨表数,等于与 λ\lambda 对应的不可约表示的维数。

分拆还用于标记对称函数的一些重要基,包括舒尔函数基,从而在代数、几何与组合恒等式之间建立联系。

随机分拆

在分拆上赋予概率分布,就能将其形状及统计量作为随机对象研究。一种模型给 nn 的每个分拆赋予相等的概率 1/p(n)1/p(n)。其他模型则利用表示论中的量为分拆赋予权重。

不同的选择会产生不同的典型行为。研究问题包括最大分拆项的分布、分拆项的个数,以及经过适当缩放后的图形的极限轮廓。因此,只有先指定概率模型,关于“典型分拆”的陈述才具有确切含义。