整数拆分
一个正整数可以写成一些正整数的和。在数论上，跟这些和式相关的问题成为整数分拆、整数剖分、整数分割、分割数或划分数。最常见的问题就是给定正整数n，求不同数组$(a_1,a_2,…,a_k)$的数目，符合下面的条件：
- $a_1+a_2+ … +a_k = n (k大小不定)$
- $a_1 \ge a_2 \ge … \ge a_k > 0$
- 其他附加条件(例如限定”k是偶数”，或”$a_i$不是1就是2”等)
分割函数p(n)就是求符合以上第一个和第二个调教的数组数目。
拆分数量数列
4可以用5种方法写成和式4, 3+1, 2+2, 2+1+1, 1+1+1+1+1。因此 p(4) = 5
定义p(0) = 1，若n为负数则p(n) = 0
分割函数p(n),n从0开始：
1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77……(OEIS:A000041)
最简单的二重循环动态规划实现代码：
|
|
Ferrers图示与恒等式
每种分割方法都可用Ferrers图示表示。
Ferrers图示是将第1行放$a_1$个方格，第2行放$a_2$个方格……第k行放$a_k$个方格，来表示整数分割的其中一个方法。
借助Ferrers图示，可以推导出许多恒等式：
1.给定正整数k和n，n表达成不多于k个正整数之和的方法数目，等于将n分割成任意个不大于k的正整数之和的方法数目。
证明：将表示前者其中一个数组的Ferrers图示沿对角线反射，便得到后者的一个数组。即两者一一对应，因此其数目相同。
如图所示
2.上述恒等式等于将n+k表达成刚好k个正整数之和的方法的数目。
3.给定正整数n。将n表达成两两相异正整数之和的方法的数目，等于将n表达成奇数之和的方法的数目。
4.将n表达成p个1和q个2之和，这些方法的数目是第n个斐波那契数。
5.将n表达成多于1的正整数之和的方法数目是p(n)-p(n-1)。
Rademacher级数
1918年哈代和拉马努金发现渐进式：
p(n) ~ $\frac {exp(\pi \sqrt{2n/3})}{4n \sqrt 3} \quad as \quad n \rightarrow \infty$
1937年，Hans Rademacher得出一个更佳的结果：
$p(n) = \frac{1}{\pi \sqrt 2} \sum_{k=1}^{\infty}A_k(n) \sqrt k \frac{d}{dn} (\frac{sinh(\frac{\pi}{k} \sqrt{\frac{2}{3}(n-\frac{1}{24})})}{\sqrt {n-\frac{1}{24}}})$
$A_k(n) = \sum_{0 \le m < k;(m,k)=1 }{exp(\pi is(m,k)-2\pi inm/k)}$
(m,n)=1表示m,n互质时才计算那项。s(m,k)表示戴德金和。这条公式的证明用上了福特圆、法里数列、模群和戴德金函数
$p_k(n)$
当x限定将n表示成刚好k个正整数之和时，可以表示为$p_k(n)$。显然$p(n) = \sum_{k=1}^n{p_k(n)}$
性质
- 对于n>1, $p_n(n) = p_1(n) = 1$
- $p_2(n) = \left\lfloor n/2 \right\rfloor$ (OEIS:A004526)
- $p_3(n)= 最接近n^2/12的正整数$。(OEIS:A069905)
- $p_{n-1}(n) = 1$
- $p_k(n) = p_{k-1}(n-1) + p_k(n-k)$。
1.最小的那个数字是1时，除去那个数字，剩余个数为k-1
2.最小的数字大于1时，将每个位置上的数字都减去1，共减了k，剩余数字个数为k
$p_k(n)$能够抽象表示为n个相同的球放入m个相同的箱子的方法种数。
我们构建一个关于S -> T的映射
我们可以知道的对于S->T的映射
1)单射情况下 $|S| \le |T|$
2)满射情况下 $|S| \ge |T|$
根据单射和满射的情况，这是一个很优秀的计算出上下界的方法
我们构建划分和组合两种方式
$$
\begin{aligned}
partition \quad
& \begin{cases}
x_1+x_2+ … +x_k = n \\
(x_1,x_2,…,x_k) & x_1\ge x_2 \ge … \ge x_k \ge 1
\end{cases}
\\
\\
composition \quad
& \begin{cases}
x_1+x_2+ … +x_k = n \\
(x_1,x_2,…,x_k) & x_i \ge 1
\end{cases}
\end{aligned}
$$
对于partition的结果k个数字可以任意排序，建立一个集合S，对于composition建立一个集合T，那么S到T的映射必然是满射的，因为必然包含了T中所有的结果，S中甚至可能会出现重复的部分，那么就能得知：
$|S| \ge |T| \Leftrightarrow k!p_k(n) \ge \binom{n-1}{k-1}$.
同理对于partition的结果k个数字可以任意排序，建立一个集合S，对于composition建立一个集合T，希望S到T的映射必是单射的，那么只有在任意$x_i$和$x_j$不相等的情况下成立，那么就构造$x_1+k-1 \ge x_2+k-2 \ge … \ge x_k \ge 1$，因为是单射就能得到如下结果
$|S| \le |T| \Leftrightarrow k!p_k(n) \le \binom{n+(k-1)k/2-1}{k-1}$.
$$
\frac{\binom{n-1}{k-1}}{k!} \le p_k(n) \le \frac{\binom{n+(k-1)k/2-1}{k-1}}{k!}
$$
那么由n趋向于无穷，可以推算得知这趋向于一个极限。
生成函数求解p(n)
定义p(n)的生成函数如下
$$
\sum_{n=0}^{\infty}p(n)x^n = \prod_{k=1}^{\infty}(\frac{1}{1-x^k})
$$
因为左侧式子理解成生成函数就是对于一个n拆成多个正整数相加.
$$
1取了多少次->(1+x^1+x^2+x^3+…) \\
2取了多少次->(1+x^2+x^4+x^6+…) \\
3取了多少次->(1+x^3+x^6+x^9+…) \\
\vdots \\
\sum_{n=0}^{\infty}p(n)x^n = (1+x^1+x^2+x^3+…)(1+x^2+x^4+x^6+…)(1+x^3+x^6+x^9+…) \cdots
$$
上式是因为当|x|<1时，根据无穷级数的求解可知
$$
\sum_{i=0}^{\infty}x^i = \frac{1}{1-x}
$$
所以得到p(n)的生成函数$\sum_{n=0}^{\infty}p(n)x^n = \prod_{k=1}^{\infty}(\frac{1}{1-x^k})$
根据欧拉发现的五边形数定理，描述欧拉函$\phi(x)$如下：
$$
\prod_{n=1}^{\infty}(1-x^n) = \sum_{k=-\infty}^{\infty} (-1)^kx^{k(3k-1)/2} = \sum_{k=0}^{\infty} (-1)^kx^{k(3k \pm 1)/2} \\
(1-x)(1-x^2)(1-x^3) … = 1-x-x^2+x^5+x^7-x^{12}-x^{15}+x^{22}+x^{26}+… \\
这些系数都属于广义五边形数
$$
那么我们就很容易发现欧拉函数的导数是分割函数的母函数：
$$
\frac{1}{\phi(x)} = \sum_{k=0}^{\infty} p(k)x^k \quad <=> \quad 1 = \phi(x)\sum_{k=0}^{\infty} p(k)x^k \\
(1-x-x^2+x^5+x^7-x^{12}-x^{15}+x^{22}+x^{26}+…)(1+p(1)x+p(2)x^2+p(3)x^3+…) = 1
$$
那么在考虑$x^n$项的系数的时候，在n>0的情况下，系数都为0，那么就能得到
$$
p(n)-p(n-1)-p(n-2)+p(n-5)+p(n-7)+… = 0 \\
p(n) = p(n-1)+p(n-2)-p(n-5)-p(n-7)+ …
$$
这个的时间复杂度可以在O(nlogn)时间内解决。
对整数划分问题的添加限制扩展
问题 HDU 4658
给定正整数n，计算有多少种划分方法，但要保证划分出来相同的数字最多出现k次。方法数对10^9+7取模。
1<=n,k<=10^5
题解
这里先认定$p_k(n)$和前面的解释不同，在这里代表对n划分，相同的数字最多出现k次的答案。根据生成函数可知
$$
\begin{aligned}
p_k(n) & = (1+x^1+x^2 + … + x^{k-1})(1+x^2+x^4+…+x^{2k-2})… \\
& = \frac{1-x^k}{1-x} \frac{1-x^{2k}}{1-x^2} \frac{1-x^{3k}}{1-x^3}… \\
& = \prod_{i=1}^{\infty} \frac{1-x^{ik}}{1-x^i} \\
\because \quad 1/\phi(x) & = p(x) \quad and \quad \phi(x) = \prod_{i=1}^{\infty}{(1-x^i)} (欧拉函数) \\
\therefore \quad p_k(n) & = \phi(x^k)p(x) = (1-x^k - x^{2k}+x^{5k}+x^{7k} …)(p(0)x^0+p(1)x^1+p(2)x^2+…) \\
& = \sum_{i=0}^{\infty} (-1)^ix^{(3i \pm 1)∗i/2} \sum_{i=0}^{\infty}{p(i)x^i} \quad (ps:i=0, (3i \pm 1)∗i/2均得到0，单只计算一次) \\
\end{aligned}
$$
最后结果很清晰了，初始化求出p(x)的数组，时间复杂度在$O(n^{3/2})$，后面对于两者，只要系数相加为n，然后把对应的两个系数乘在一起即可（就是求系数得n的卷积），后面这一步的时间复杂度就小很多,$O(n^{1/2})$。
代码实现如下
|
|
Reference
1.五边形数定理
2.整数分拆
3.欧拉函数
