整数合成

整数合成是把一个正整数写成若干个正整数之和，并把加数的顺序作为结果的一部分。例如 $1 + 3$ 和 $3 + 1$ 是四的两种不同合成。合成的每个加数称为一个部件，其部件数可以固定，也可以在计数时变化。

把分割放在单位之间

将四写成四个单位的和，在三个间隙中决定是否放入分割。若只在第二个间隙分割，就得到 $2 + 2$ ；若在第一个和第三个间隙分割，就得到 $1 + 2 + 1$ 。没有分割时得到只有一个部件的 $4$ 。

四个单位之间有三个间隙，在第一个和第三个间隙设置分割，得到一、二、一三个部件。 — 四个单位排成一行。两条分割线确定三个连续的部分，分别含一个、两个、一个单位。

这个方法既能从分割得到合成，也能从合成恢复分割。具体说，对 $n = a_{1} + \dots + a_{k}$ ，其中各 $a_{i}$ 是正整数，在第 $a_{1}$ 、 $a_{1} + a_{2}$ ，直到 $a_{1} + \dots + a_{k - 1}$ 个单位之后放分割。每个位置严格在 $1$ 与 $n - 1$ 之间，而且彼此不同。反过来，相邻分割线之间的单位数给出原来的有序部件。因此两种表示一一对应。

定理。 当 $n \geq 1$ 时， $n$ 的合成总数为 $2^{n - 1}$ 。恰有 $k$ 个部件的合成数为 $(\binom{n - 1}{k - 1}) (1 \leq k \leq n) .$

证明。 每个间隙独立地有放分割或不放分割两种选择，因此总数为 $2^{n - 1}$ 。恰有 $k$ 个部件时，需要从 $n - 1$ 个间隙中选出 $k - 1$ 个放分割。按部件数相加，也得到 $\sum_{k = 1}^{n} (\binom{n - 1}{k - 1}) = 2^{n - 1} .$ 这与二项式定理中系数之和的公式一致。^[1]

一个完整的计数例子

将五写成三个正整数之和，并区分顺序。五个单位之间共有四个间隙，选两个放分割，得到 $(\binom{4}{2}) = 6$ 种。逐一列出为 $\begin{matrix} 1 + 1 + 3, 1 + 2 + 2, 1 + 3 + 1, \\ 2 + 1 + 2, 2 + 2 + 1, 3 + 1 + 1. \end{matrix}$ 每一项的部件数都是三，各部件之和都是五。这里 $1 + 1 + 3$ 与 $3 + 1 + 1$ 的部件相同，但顺序不同。

如果每个部件至少为二，先给三个部件各分配二。总量必须至少为六，因而总量五时没有解。若总量改为八，令 $a_{i} = 2 + b_{i}$ ，便得到非负整数方程 $b_{1} + b_{2} + b_{3} = 2$ 。按隔板法，在两个单位与两个隔板组成的四个位置中选出两个隔板，可得 $(\binom{4}{2}) = 6$ 种。例如 $(b_{1}, b_{2}, b_{3}) = (0, 2, 0)$ 对应合成 $2 + 4 + 2$ 。允许 $b_{i} = 0$ ，与原部件至少为二的条件相符。

与整数分拆的关系

整数分拆忽略部件顺序。五的分拆 $3 + 1 + 1$ 对应三个合成 $3 + 1 + 1$ 、 $1 + 3 + 1$ 和 $1 + 1 + 3$ 。若一个分拆有 $k$ 个部件，不同数值的出现次数为 $m_{1}, \dots, m_{r}$ ，则它产生 $\frac{k!}{m_{1}! \dots m_{r}!}$ 个不同合成。先把 $k$ 个部件视作有标签并排列，再除去相同数值内部交换造成的重复，就得到这一公式。于是同一个分拆对应的合成数取决于重复次数。

通常约定零有一个空合成，它含零个部件。这项约定便于使用递推与生成函数，但 $2^{n - 1}$ 的计数公式只在上文声明的 $n \geq 1$ 范围内使用。

参考资料

↑ Ira M. Gessel、Richard P. Stanley，Algebraic Enumeration，第2节，合成与子集的一一对应。访问于2026年11月7日。

[1] Ira M. Gessel、Richard P. Stanley，Algebraic Enumeration，第2节，合成与子集的一一对应。访问于2026年11月7日。

[1]