整数划分 (Integer Partitions)¶

整数划分（Integer Partition / 整数分拆） 是组合数学与数论中的核心经典问题。它是指将一个正整数 $n$ 表示为若干个正整数之和的方案（通常不考虑加数的顺序）。

在算法竞赛与大厂面试中，围绕“划分数是否有封闭公式”、“限制划分为 $k$ 个部分”、“互不相同的数划分”以及“球盒模型映射”经常延伸出极高频的动态规划、母函数与数学推导题。

1. 核心定义与易混淆模型全景辨析¶

对于正整数 $n$，其划分可以形式化为：

\[ n = a_1 + a_2 + \dots + a_k \quad (a_1 \ge a_2 \ge \dots \ge a_k \ge 1) \]

其中每一个 $a_i$ 称为一个部分（Part），$k$ 为划分的大小（Size / 部分数）。由于约定了从大到小排列，$(4, 1)$ 与 $(1, 4)$ 被视为同一种划分。

许多初学者在探索“划分数公式”时，常将无序整数划分与有序组成或集合划分混淆。以下是经典球盒模型对照表：

问题模型	元素是否有别	容器是否有别	顺序是否有影响	方案数表示	计算公式 / 核心复杂度
无序整数划分 (Partitions)	相同球	相同盒	无关	$p_k(n)$ 或 $p(n)$	递推 DP $\mathcal{O}(nk)$ / 五角数 $\mathcal{O}(n\sqrt{n})$
有序整数划分 (Compositions)	相同球	不同盒	有关	$c_k(n)$	隔板法 $\binom{n-1}{k-1}$（总数 $2^{n-1}$）
第二类斯特林数 (Set Partitions)	不同球	相同盒	无关	$S(n, k)$	容斥公式 / 递推 $S(n,k)=S(n-1,k-1)+kS(n-1,k)$
放苹果问题 (允许盘子为空)	相同球	相同盒	无关	$p_{\le k}(n)$	等价于 $p_k(n+k)$

2. 大小为 k 的正整数划分种类数¶

记 $p_k(n)$（或 $p(n, k)$）为将正整数 $n$ 拆分成恰好 $k$ 个正整数的方案数。

2.1 为什么一般的 k 没有简单封闭式？¶

初学者常好奇：为什么有序划分有简单的组合数公式 $\binom{n-1}{k-1}$，而无序划分 $p_k(n)$ 却没有像 $\binom{n}{k}$ 那样单一初等函数的公式？ - 数学本质：无序划分消除了对称性，其母函数分母为 $(1-x)(1-x^2)\dots(1-x^k)$。分母中包含了各个阶数的单位根（Roots of Unity），导致其在代数上是一个关于 $n$ 的 $k-1$ 次准多项式（Quasi-polynomial）。 - 其系数具有以 $\text{lcm}(1, 2, \dots, k)$ 为周期的周期性震荡，因而对于一般的 $k$，不存在单一的多项式或初等封闭解。

2.2 核心递推关系 (动态规划基石)¶

尽管没有通用简单式，但 $p_k(n)$ 拥有极其优雅的二维递推公式：

\[ p_k(n) = p_k(n - k) + p_{k - 1}(n - 1) \]

flowchart TD
    subgraph "划分总数 p_k(n)"
        Total["将 n 拆分成恰好 k 个正整数: n = a_1 + a_2 + ... + a_k"]
    end

    Total --> Branch1["分类 1: 最小的部分为 1 (a_k = 1)"]
    Total --> Branch2["分类 2: 所有的部分均大于等于 2 (a_k >= 2)"]

    Branch1 --> Sub1["拿掉这个 1<br>剩下 k-1 个数和为 n-1<br>方案数: p_{k-1}(n-1)"]
    Branch2 --> Sub2["给每个数统一减去 1<br>得到 k 个依然 >=1 的数，总和为 n-k<br>方案数: p_k(n-k)"]

边界条件：¶

当 $k > n$ 或 $k \le 0$ 时：$p_k(n) = 0$；
当 $k = 1$ 时：$p_1(n) = 1$（仅有 $n$ 本身）；
当 $k = n$ 时：$p_n(n) = 1$（仅有全部为 $1$ 的一种划分）；
$p_0(0) = 1$。

2.3 Ferrers 图与对偶定理¶

Ferrers 图（费雷尔图） 是直观分析整数划分的几何工具。用 $k$ 行圆点或方块表示每一部分的数值。

例如，$n = 10$ 划分为 $4 + 3 + 2 + 1$ 的 Ferrers 图为：

● ● ● ●   (4)
● ● ●     (3)
● ●       (2)
●         (1)

沿着主对角线翻转（转置，Conjugate Partition），得到的对偶划分为 $4 + 3 + 2 + 1$。

核心对偶定理： 将 $n$ 拆分成恰好 $k$ 个正整数的划分数，严格等于将 $n$ 拆分成“最大数为 $k$”的划分数。

推论：将 $n$ 拆分成至多 $k$ 个正整数的方案数 $p_{\le k}(n)$，严格等于将 $n$ 拆分成所有数均不超过 $k$ 的方案数。

2.4 固定小 k 时的精妙取整公式¶

对于较小的 $k$（$k = 1, 2, 3$），数学家推导出了极为简洁的四舍五入 / 向下取整封闭解：

$k = 1$： $$p_1(n) = 1$$
$k = 2$： $$p_2(n) = \left\lfloor \frac{n}{2} \right\rfloor$$ 解释：设 $a + b = n$ 且 $1 \le a \le b$，则 $a$ 可取 $1, 2, \dots, \lfloor n/2 \rfloor$，共 $\lfloor n/2 \rfloor$ 种。
$k = 3$： $$p_3(n) = \text{round}\left( \frac{n^2}{12} \right) = \left\lfloor \frac{n^2 + 6}{12} \right\rfloor$$ 数值验证：
$n = 3$: $\lfloor 15/12 \rfloor = 1$（$1+1+1$）
$n = 4$: $\lfloor 22/12 \rfloor = 1$（$2+1+1$）
$n = 5$: $\lfloor 31/12 \rfloor = 2$（$3+1+1, 2+2+1$）
$n = 6$: $\lfloor 42/12 \rfloor = 3$（$4+1+1, 3+2+1, 2+2+2$）
$n = 7$: $\lfloor 55/12 \rfloor = 4$（$5+1+1, 4+2+1, 3+3+1, 3+2+2$）
$k \ge 4$ 为什么失效？：从 $k=4$ 开始，单位根周期包含 $2, 3, 4$（最小公倍数周期为 $12$），使得余项不仅含符号修正 $(-1)^n$，还含三次根与虚数单位 $i$，无法被单一的二次或三次多项式四舍五入精确覆盖。

2.5 渐近估计公式 (当 n 很大时)¶

当 $k$ 保持固定且 $n \to \infty$ 时，多项式的最高次项占绝对主导地位：

\[ p_k(n) \sim \frac{n^{k-1}}{k! \, (k-1)!} \]

例如： - $k = 2$ 时：$p_2(n) \sim \frac{n}{2! \cdot 1!} = \frac{n}{2}$； - $k = 3$ 时：$p_3(n) \sim \frac{n^2}{3! \cdot 2!} = \frac{n^2}{12}$； - $k = 4$ 时：$p_4(n) \sim \frac{n^3}{4! \cdot 3!} = \frac{n^3}{144}$。

3. 母函数与代数生成理论¶

在代数组合学中，划分数最紧凑的数学工具是形式幂级数（母函数）。

3.1 大小为 k 的母函数¶

将 $n$ 拆分为至多 $k$ 个部分（等价于每个数 $\le k$）的生成函数为：

\[ P_{\le k}(x) = \sum_{n=0}^\infty p_{\le k}(n) x^n = \frac{1}{(1 - x)(1 - x^2)(1 - x^3)\cdots(1 - x^k)} \]

由于 $p_k(n) = p_{\le k}(n - k)$（每个数先分配一个 1），恰好包含 $k$ 个部分的母函数为：

\[ P_k(x) = \sum_{n=k}^\infty p_k(n) x^n = \frac{x^k}{(1 - x)(1 - x^2)\cdots(1 - x^k)} \]

3.2 全局无限制划分数的欧拉母函数¶

若不限制划分的大小 $k$，正整数 $n$ 的总划分数记为 $p(n)$。欧拉给出了著名的全划分母函数：

\[ P(x) = \sum_{n=0}^\infty p(n) x^n = \prod_{i=1}^\infty \frac{1}{1 - x^i} = \frac{1}{(1-x)(1-x^2)(1-x^3)\cdots} \]

展开每一项 $\frac{1}{1 - x^i} = 1 + x^i + x^{2i} + x^{3i} + \dots$，其中 $x^{c \cdot i}$ 代表数字 $i$ 在划分中出现了 $c$ 次。

4. 全局整数划分数与欧拉五角数定理¶

计算前 $n$ 项无限制划分数 $p(n)$ 有两种主流算法范式：

4.1 完全背包模型：O(n^2)¶

把可用的数字 $1, 2, \dots, n$ 看作体积与价值相等的物品，每种物品可选无限多次，背包容量为 $n$： - 状态定义：$dp[j]$ 表示和为 $j$ 的划分数。 - 转移方程：$dp[j] = (dp[j] + dp[j - i]) \bmod MOD$（$i$ 从 $1$ 到 $n$ 外层循环，$j$ 从 $i$ 到 $n$ 正序遍历）。

4.2 欧拉五角数定理：O(n * sqrt(n)) 极速递推¶

欧拉研究母函数的分母 $\prod_{i=1}^\infty (1 - x^i)$（欧拉函数 $\phi(x)$），发现了惊人的五角数定理（Pentagonal Number Theorem）：

\[ \prod_{i=1}^\infty (1 - x^i) = 1 + \sum_{m=1}^\infty (-1)^m \left( x^{\frac{m(3m-1)}{2}} + x^{\frac{m(3m+1)}{2}} \right) \]

其中指数 $g_m = \frac{m(3m \pm 1)}{2}$ 称为广义五角数序列：$1, 2, 5, 7, 12, 15, 22, 26, 35, 40, \dots$。

将母函数与其倒数相乘：$P(x) \cdot \prod_{i=1}^\infty (1 - x^i) = 1$，通过对比系数，得到 $p(n)$ 的高效递推公式：

\[ p(n) = p(n - 1) + p(n - 2) - p(n - 5) - p(n - 7) + p(n - 12) + p(n - 15) - \dots \]

符号规律为：正、正、负、负、正、正、负、负……。因为 $g_m \approx \frac{3}{2}m^2$，对于给定的 $n$，不超过 $n$ 的五角数只有 $\mathcal{O}(\sqrt{n})$ 个！

复杂度跃迁：计算单项 $p(n)$ 只需要 $\mathcal{O}(\sqrt{n})$ 次加减法；计算前 $N$ 项划分数的整体时间复杂度为 $\mathcal{O}(N\sqrt{N})$，极大优于背包的 $\mathcal{O}(N^2)$。

5. 经典变体与性质拓展¶

5.1 奇数划分与互异划分 (Euler's Partition Theorem)¶

定理：将正整数 $n$ 划分为若干互不相同的正整数的种类数，严格等于将 $n$ 划分为若干奇正整数的种类数。

母函数证明： - 互异划分的母函数：$Q(x) = \prod_{i=1}^\infty (1 + x^i)$ - 利用恒等式 $1 + x^i = \frac{1 - x^{2i}}{1 - x^i}$：

\[ Q(x) = \prod_{i=1}^\infty \frac{1 - x^{2i}}{1 - x^i} = \frac{(1-x^2)(1-x^4)(1-x^6)\cdots}{(1-x)(1-x^2)(1-x^3)(1-x^4)\cdots} \]

所有的偶数幂因子在分子分母中全部两两抵消，只剩下分母中的奇数项：

\[ Q(x) = \prod_{j=1}^\infty \frac{1}{1 - x^{2j-1}} \]

这正是将数字划分为奇数的母函数！

5.2 放苹果问题 (允许部分为 0)¶

经典面试题：将 $m$ 个相同的苹果放入 $n$ 个相同的盘子中，允许盘子为空，求总分配方案数。 - 设盘子中非空盘子数为 $k$（$1 \le k \le n$），相当于将 $m$ 划分为至多 $n$ 个正整数，即 $p_{\le n}(m)$。 - 根据对偶性，先给每个盘子放 1 个苹果，则相当于将 $m + n$ 个苹果放入 $n$ 个非空盘子：

\[ \text{Ways}(m, n) = p_{\le n}(m) = p_n(m + n) \]

6. 算法竞赛与面试高频题实战¶

6.1 洛谷 P1025 / 经典面试题：数的划分¶

题目描述：将整数 $n$ 分成 $k$ 份，且每份不能为空，任意两份不能相同（不考虑顺序，如 $1, 1, 5$ 与 $1, 5, 1$ 属于同一种）。求划分方案数。$1 \le n \le 200, 2 \le k \le 6$。

题解思路：直接应用本专题的核心递推式 $dp[i][j] = dp[i-1][j-1] + dp[i-j][j]$。

#include <iostream>
#include <vector>

long long solve_partition_k(int n, int k) {
    if (k <= 0 || n < k) return 0;
    std::vector<std::vector<long long>> dp(n + 1, std::vector<long long>(k + 1, 0));
    dp[0][0] = 1;

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= std::min(i, k); ++j) {
            dp[i][j] = dp[i - 1][j - 1] + dp[i - j][j];
        }
    }
    return dp[n][k];
}

int main() {
    int n = 7, k = 3;
    std::cout << solve_partition_k(n, k) << "\n"; // 输出 4 (1+1+5, 1+2+4, 1+3+3, 2+2+3)
    return 0;
}

6.2 LeetCode 343. 整数拆分 (Integer Break)¶

题目描述：给定一个正整数 $n$，将其拆分为 $k$ 个正整数的和（$k \ge 2$），并使这些整数的乘积最大化。返回可以获得的最大乘积。

深度数学证明： 1. 因子均分原理：设将 $n$ 拆分为 $k$ 个数，当每个数相等时乘积最大（均值不等式），此时单项为 $x = n/k$，总乘积为 $f(x) = x^{n/x} = (x^{1/x})^n$。 2. 极值点分析：考察函数 $g(x) = x^{1/x}$，两边取对数求导 $\ln g(x) = \frac{\ln x}{x} \implies g'(x) = g(x) \frac{1 - \ln x}{x^2}$。驻点为 $x = e \approx 2.718$。 3. 离散整数最优选择：在离散整数中，$2$ 和 $3$ 距离 $e$ 最近。对比 $2^{1/2} = \sqrt{2} \approx 1.414$ 与 $3^{1/3} = \sqrt[3]{3} \approx 1.442$，显然 $3$ 优于 $2$。同时 $2 \times 2 \times 2 = 8 < 3 \times 3 = 9$，因此 3 个 2 总是劣于 2 个 3。 4. 贪心策略：尽可能多地拆出 $3$；若最后余 $4$，拆为 $2 \times 2$（优于 $3 \times 1$）；若最后余 $2$，直接保留。

class Solution {
public:
    int integerBreak(int n) {
        if (n <= 3) return n - 1; // 2 -> 1*1=1, 3 -> 1*2=2
        int product = 1;
        while (n > 4) {
            product *= 3;
            n -= 3;
        }
        product *= n; // 此时 n 剩下 2, 3 或 4
        return product;
    }
};

7. 工业级 C++ 整数划分算法模板库¶

以下提供开箱即用的模块化模板结构体 IntegerPartition，集成了： 1. $\mathcal{O}(nk)$ 动态规划求任意 $p_k(n)$； 2. $\mathcal{O}(1)$ 小 $k$ 封闭取整公式（$k = 1, 2, 3$）； 3. $\mathcal{O}(N\sqrt{N})$ 欧拉五角数定理批量预处理全局无限制划分数 $p(n)$。

#include <vector>
#include <cmath>
#include <algorithm>

struct IntegerPartition {
    // 1. O(n * k) 动态规划: 计算恰好拆分成 k 个正整数的划分数 p_k(n)
    static long long countKParts(int n, int k) {
        if (k <= 0 || n <= 0 || k > n) return 0;
        if (k == 1 || k == n) return 1;
        std::vector<std::vector<long long>> dp(n + 1, std::vector<long long>(k + 1, 0));
        dp[0][0] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= std::min(i, k); ++j) {
                dp[i][j] = dp[i - 1][j - 1] + dp[i - j][j];
            }
        }
        return dp[n][k];
    }

    // 2. O(1) 封闭公式: 针对小 k 的快速取整求解
    static long long formulaSmallK(int n, int k) {
        if (k <= 0 || n < k) return 0;
        if (k == 1) return 1;
        if (k == 2) return n / 2;
        if (k == 3) {
            // 等价于 round(n^2 / 12) = floor((n^2 + 6) / 12)
            return (1LL * n * n + 6) / 12;
        }
        return -1; // k >= 4 时无简单单项多项式取整公式
    }

    // 3. O(N * sqrt(N)) 欧拉五角数定理: 批量计算前 N 项全局无限制划分数 p(0...N)
    static std::vector<long long> computeAllPartitions(int n, long long mod = 1e9 + 7) {
        std::vector<long long> p(n + 1, 0);
        p[0] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int m = 1;; ++m) {
                long long g1 = 1LL * m * (3 * m - 1) / 2;
                long long g2 = 1LL * m * (3 * m + 1) / 2;
                if (g1 > i && g2 > i) break;
                long long sign = (m % 2 == 1) ? 1 : -1;
                if (g1 <= i) {
                    p[i] = (p[i] + sign * p[i - g1]) % mod;
                }
                if (g2 <= i) {
                    p[i] = (p[i] + sign * p[i - g2]) % mod;
                }
            }
            p[i] = (p[i] % mod + mod) % mod;
        }
        return p;
    }
};

8. 考点总结与速查清单¶

需求场景	推荐算法 / 公式	核心复杂度
小 $k$ 快速手算 ($k=1,2,3$)	$p_1(n)=1,\quad p_2(n)=\lfloor \frac{n}{2} \rfloor,\quad p_3(n)=\lfloor \frac{n^2+6}{12} \rfloor$	$\mathcal{O}(1)$
指定划分数 $k$ ($n, k \le 3000$)	递推式 $dp[i][j] = dp[i-1][j-1] + dp[i-j][j]$	$\mathcal{O}(nk)$ 时间，$\mathcal{O}(nk)$ 空间
全划分数前缀表 ($N \le 10^5$)	欧拉五角数定理 $p(n) = \sum (-1)^{m-1} p(n - g_m)$	$\mathcal{O}(N\sqrt{N})$ 时间，$\mathcal{O}(N)$ 空间
互异数划分 vs 奇数划分	欧拉划分定理，二者方案数严格相等	概念转化与母函数展开
乘积最大化 (LeetCode 343)	贪心尽可能拆出 $3$，余 $4$ 拆成 $2 \times 2$	$\mathcal{O}(1)$ 数学 / $\mathcal{O}(n)$ DP

需求场景	推荐算法 / 公式	核心复杂度
小 \(k\) 快速手算 (\(k=1,2,3\))	\(p_1(n)=1,\quad p_2(n)=\lfloor \frac{n}{2} \rfloor,\quad p_3(n)=\lfloor \frac{n^2+6}{12} \rfloor\)	\(\mathcal{O}(1)\)
指定划分数 \(k\) (\(n, k \le 3000\))	递推式 \(dp[i][j] = dp[i-1][j-1] + dp[i-j][j]\)	\(\mathcal{O}(nk)\) 时间，\(\mathcal{O}(nk)\) 空间
全划分数前缀表 (\(N \le 10^5\))	欧拉五角数定理 \(p(n) = \sum (-1)^{m-1} p(n - g_m)\)	\(\mathcal{O}(N\sqrt{N})\) 时间，\(\mathcal{O}(N)\) 空间
互异数划分 vs 奇数划分	欧拉划分定理，二者方案数严格相等	概念转化与母函数展开
乘积最大化 (LeetCode 343)	贪心尽可能拆出 \(3\)，余 \(4\) 拆成 \(2 \times 2\)	\(\mathcal{O}(1)\) 数学 / \(\mathcal{O}(n)\) DP