CVBB ACM Team

分拆：将自然数n写成递降正整数和的表示。

$$n=r_1+r_2+⋯+r_k\quad r_1≥r_2≥⋯≥r_k≥1$$

和式中每个正整数称为一个部分。

分拆数：p_n。自然数n的分拆方法数。

自0开始的分拆数：

其中恰有k个部分的分拆，称为k部分拆数，记作p(n,k)。

本题要求计算k部分拆数p(n,k)。多组输入，其中n上界为10000，k上界为1000，对1000007取模。

显然，k部分拆数 p(n,k)同时也是下面方程的解数：

$$n-k=y_1+y_2+⋯+y_k\quad y_1≥y_2≥⋯≥y_k≥0$$

如果这个方程里面恰有j个部分非0，则恰有p(n-k,j)个解。因此有和式：

$$p(n,k)=∑_{j=1}^k p(n-k,j)$$

相邻两个和式作差，得：

$$p(n,k)=p(n-1,k-1)+p(n-k,k)$$

根据这个可以轻易地写出程序。

#include<stdio.h>
#include<string.h>
 
int p[10005][1005];/*将自然数n分拆为k个部分的方法数*/ 
 
int main()
{
	int n,k;
	while(~scanf("%d%d",&n,&k))
	{
		memset(p,0,sizeof(p));
		p[0][0]=1;
		int i;
		for(i=1;i<=n;++i)
		{
			int j;
			for(j=1;j<=k;++j)
			{
				if(i-j>=0)/*p[i-j][j]所有部分大于1*/
				{
					p[i][j]=(p[i-j][j]+p[i-1][j-1])%1000007;/*p[i-1][j-1]至少有一个部分为1。*/
				}
			}
		}
		printf("%d\n",p[n][k]);
	}
}

生成函数：一种幂级数。各项的系数为数列中的对应项。

由等比数列求和公式，有：

$$1/(1-x^k )=1+x^k+x^2k+x^3k+⋯$$

$$1+p_1 x+p_2 x^2+p_3 x^3+⋯=\frac{1}{1-x} \frac{1}{1-x^2} \frac{1}{1-x^3}…$$

对于k部分拆数，生成函数稍微复杂。具体写出如下：

$$∑_{n,k=0}^∞ {p(n,k) x^n y^k }=\frac{1}{1-xy} \frac{1}{1-x^2 y} \frac{1}{1-x^3 y}…$$

Ferrers图：将分拆的每个部分用点组成的行表示。每行点的个数为这个部分的大小。

根据分拆的定义，Ferrers图中不同的行按照递减的次序排放。最长行在最上面。

例如：分拆12=5+4+2+1的Ferrers图。

Ferrers图.png

将一个Ferrers图沿着对角线翻转，得到的新Ferrers图称为原图的共轭，新分拆称为原分拆的共轭。显然，共轭是对称的关系。

例如上述分拆12=5+4+2+1的共轭是分拆12=4+3+2+2+1。

最大k分拆数：自然数n的最大部分为k的分拆个数。

根据共轭的定义，有显然结论：

最大k分拆数与k部分拆数相同，均为p(n,k)。