整数划分的递归关系是怎么讨论出来的

Question

整数划分的递归关系是怎么讨论出来的？有人给我说说吗，看不懂书上说啥？

Answer 1

整数划分的递归关系是通过分析整数划分的性质和规律得出的。

整数划分是将一个正整数拆分成若干个正整数，使得它们的和等于原数的过程。例如，对于整数4，它的不同划分方式有：

• 4
• 3 + 1
• 2 + 2
• 2 + 1 + 1
• 1 + 1 + 1 + 1

通过观察这些划分，我们可以发现：

1. 对于划分中的每个数，它必须小于等于原数。
2. 划分中可以有重复的数，如上例中的2 + 2。
3. 划分中的数是无序的，如上例中的3 + 1和1 + 3是相同的划分。

基于这些性质，我们可以得出整数划分的递归关系：

设p(n)表示将整数n拆分成若干个正整数的划分总数，则：

1. 如果划分中最大的数是1，则问题转化为将n拆分成n个数的和，即p(n) = 1 + p(n-1)。
2. 如果划分中最大的数大于1，则问题转化为将n拆分成最大数为k的数的和，其中k可以从1到n-1取值。因此，p(n) = p(n-1) + p(n-2) + ... + p(n-k)。

这样，我们就可以使用递归的方式求解整数划分问题。