整数分拆

整数分拆是把一个非负整数表示成若干正整数之和，并且只记录各加数出现的次数。改变加数的排列顺序不会得到新的分拆。分拆中的每个加数叫作部件，通常把部件按非递增顺序书写。

例如，五有七个分拆： $$\begin{array}{c}5,4+1,3+2,3+1+1,\\ 2+2+1,2+1+1+1,1+1+1+1+1.\end{array}$$ 其中 $3+2$ 与 $2+3$ 是同一个分拆。记 $p(n)$ 为 $n$ 的分拆数，则 $p(5)=7$。约定零有一个空分拆，故 $p(0)=1$；这个约定使后面的递推式与生成函数在边界处成立。

部件数与最大部件

将每个部件画成一行点，并使各行左端对齐，得到费雷尔图。分拆 $3+2$ 对应两行，第一行三个点，第二行两个点。按列重新读取，同一组点给出 $2+2+1$。

同一分拆图交换行与列。原来的两行成为新图的最大行长二，原来的最大行长三成为新图的三行。

一般地，对非递增正整数列 ${\lambda }_1\ge \cdots \ge {\lambda }_k$，令第 $j$ 列的点数为 $$\lambda {\text{'}}_j=\mathrm{\#}\{i:{\lambda }_i\ge j\}.$$ 列数为 ${\lambda }_1$，每列的点数仍非递增，因此 ${\lambda }^{\prime }$ 也是同一个整数的分拆，称为原分拆的共轭分拆。再次交换行列会回到原图，所以共轭是一一对应。它把部件数恰为 $k$ 的分拆对应到最大部件恰为 $k$ 的分拆。

固定部件数的递推

记 $q(n,k)$ 为 $n$ 分拆成恰好 $k$ 个正部件的方式数。约定 $q(0,0)=1$，当 $n<0$、$k<0$ 或只有一个下标为零时取零。对正整数 $n,k$，有 $$q(n,k)=q(n-1,k-1)+q(n-k,k).$$

证明。 把分拆分成两类。若至少有一个部件等于一，删去一个一，得到 $n-1$ 的一个恰有 $k-1$ 个部件的分拆，反向操作是添回一个一。若所有部件都至少为二，就把每个部件减一，得到 $n-k$ 的一个恰有 $k$ 个部件的分拆，反向操作是给每个部件加一。两类互不重叠且各自对应可逆，故数量相加得到递推式。

对 $n=5,k=2$，两类依次是 $4+1$ 和 $3+2$。递推右边也给出 $q(4,1)+q(3,2)=1+1=2$。当 $n\ge 1$ 时，对所有可行的部件数求和，便得到 $p(n)=\sum _{k=1}^{n}q(n,k)$。空分拆按前述约定单独计为 $p(0)=1$。

生成函数

若部件一出现 $m_1$ 次、部件二出现 $m_2$ 次，依此类推，分拆总和为 $\sum _{j}j{m}_j$。用每个非负次数选择构造形式幂级数，可得 $$\sum _{n=0}^{\mathrm{\infty }}p(n)x^n=\prod _{j=1}^{\mathrm{\infty }}\frac{1}{1-x^j}.$$ 每个因子是 $1+x^j+x^{2j}+\cdots$，选择 $x^{j{m}_j}$ 相当于选定大小为 $j$ 的部件出现 $m_j$ 次。相乘后 $x^n$ 的系数恰好数出所有总和为 $n$ 的次数选择。对固定的 $n$，只有 $j\le n$ 的因子会影响该系数，所以此处作为形式幂级数有明确含义。

例如，取前五个因子并保留五次以内的项，其 $x^5$ 系数为七，与开头逐一列出的分拆一致。若要求部件互不相同，把各因子换成 $1+x^j$ 即可，每个大小只允许出现零次或一次。

整数合成也把正整数写成正部件之和，但保留顺序。因此五分成两个部件时，分拆有 $4+1$ 和 $3+2$ 两种，合成则有 $1+4,2+3,3+2,4+1$ 四种。