什么是整数分划

p(n) 的值是多少？

怎样顺序打印输出一个整数的全部分划？

整数分划与对称群和组合数学的关系

什么是整数分划

给定一个正整数 n , 一个由 r 个正整数组成的数组 λ ＝ ( x1 , x2, . . . . , xr) 如果满足

x1 + x2 + ··· + xr = n 且 x1 ≥ x2 ≥ ··· ≥ xr ≥ 1，

就称数组 λ 是 n 的一个分划。n 的所有不同的分划的个数记作 p(n)。

比如说 4 的分划 p(4) = 4 ：

4 = 4 ;

4 = 3 + 1 ;

4 = 2 + 2 ;

4 = 2 + 1 + 1 ;

4 = 1 + 1 + 1 + 1 ;

我们可以像字典给单词排顺序一样给 n 的所有分划排一个顺序：对于 n 的两个不同的分划 λ ＝ ( x1 , x2, . . . . , xr) 和 μ ＝ ( y1 , y2, . . . . , ys)，如果 λ 的 “首字母” x1 比 μ 的 “首字母” y1 大，就规定在字典序下 λ 比 μ 大，反之则规定 μ 比 λ 大。如果 x1 = y1 ，那么就比较它们的下一个 “字母” x2 和 y2 . . . . 这样继续下去，直到 λ 和 μ 在某一个位置上分出大小，根据这个位置上的大小关系来定义 λ 和 μ 之间的大小关系。在上面的例子中，我们就是按照字典序依次排列的 4 的分划。显然，( n ) 是所有分划中最大的，而 ( 1 , 1 , . . . , 1) 则是所有分划中最小的。大家可以看到，这个比较 n 的分划的大小的规则和 C 语言比较字符串大小的规则是一样的。

鉴于百度目前仍然不支持数学公式的显示，p(n) 的很多美妙的性质在这里无法详细叙述，我只能简要地用描述的语言介绍一点基本的东西。

p(n) 的值是多少？

有关 p(n) 的等式有很多，但是至今没有找到一个通项公式。由于 p(n) 在数论中的重要地位，因此大规模计算 p(n) 的值并从中发现规律，得出数学猜测就成为一个很重要的研究手段。

通常的递归法其实是最糟糕的办法，因此几乎不用（很小的 n 才用）。在计算机代数软件中广泛使用的办法主要有两种：

1. 基于欧拉五角数定理的递推方法。它可以把时间复杂度降低为 O( n^(1.5) )，但是它仍然要计算大量的中间结果（对所有小于 n 的 m 都要计算 p(m)），因此适合 n 是中等规模的情形。

2. 基于 Hardy - Ramanujan - Rademacher 等式的方法。HRR 等式是数论中最重要的等式之一，像 Riemann - zeta 函数一样，它把数论中许多深刻的现象融合在一个等式内。HRR 等式给出的级数收敛到 p(n) 的速度很快 （第一项就是 p(n) 的渐进估计），因此对很大的 n ，基于 HRR 等式的算法是目前唯一的途径。

怎样顺序打印输出一个整数的全部分划？

如果你在百度上搜索的话，会看到所有人都在使用递归的方法。这方法很直观，但是很不幸，效率也非常的低下。还记得 Fibonacci 数列吗 F(n) 吗？ p(n) 和 F(n) 很类似：

1 . 它们都以指数的速度增长。

2. 如果你按照递推公式进行递归计算，会导致大量的函数调用和大量的重复计算并占用大量的空间。

实际上打印分划的算法十分的简单（按照逆字典打印的话绍复杂一点），代码如下：

void print_partition ( int n )

{ int i = 1;

int m = 1;

int h = 1;

int t , r ;

int a[ n+1 ] ;

for ( ; i < n + 1 ; ++ i ) a[ i ] = 1 ;

a[ 1 ] = n ;

printf ( "%d \", a[ 1 ] ) ;

while ( a[ 1 ] ! = 1 )

{ if ( a [ h ] == 2 ) { a[ h-- ] -- ; m++ ; }

else { r = --a[ h ];

t = m - h + 1 ;

while ( t >= r ) { a[ ++h ] = r ; t -= r ; }

if ( t == 0 ) m = h ;

else m = h + 1 ;

if ( t >= 2 ) a[ ++h ] = t ;

}

for ( i = 1 ; i < m + 1 ; i++ )

printf ( "%d ", a[ i ] ) ;

printf ( "\" ) ;

}

}

为了便于在百科的网页中阅读，我加进去不少空白，所以如果你直接拷贝的话代码的缩进效果可能会不大好。:P 这也许是国内网页中最先出现的非递归的程序实现，其实这个算法在 Knuth 的《计算机程序设计艺术》第四卷组合算法中已经收录了。

算法想法很简单：这里的 h 代表最后一个大于等于 2 的元素的下标，（申请了 n + 1 的空间，a[ 0 ] 空着，a [ 1 ] 初始化为 n ，其他的全部初始化为 1）， m 代表当前的分划的长度。每一次循环对当前的分划在尾部进行调整，调整为在字典序下的下一个分划，以 a[ 1 ] = 1 为循环结束的条件。

这个程序的好处很多：

1. 没有任何函数的递归调用，我们只是在不停的循环。

2. 整个过程全部在一个固定的长度为 n + 1 的数组上操作，再加上几个辅助变量，占用空间很少。

3. 不必担心整数溢出的问题。尽管 p(n) 增长的很快，但是我们使用的所有变量都不超过 n 。

4. 通过设置初始状态，你可以从某个固定的分划处开始打印，打印完以后你就知道这个分划在字典序下 “排行老几” ，这一点是递归方法做不到的。

5. 给定一个参数 K ，我们可以只打印排在第 K 位上的分划（在程序中再设置一个计数器即可），递归做不到这一点。

有道是 “天下程序一大抄”。希望这个程序能够帮助大家 “抛弃” “低级趣味” 的递归算法。

整数分划与对称群和组合数学的关系

说到分划就不能不提对称群和组合数学。

抽象代数中熟知的结论：n 阶对称群 Sn 的共轭类与 n 的分划一一对应，而一个有限群的不可约复表示和它的共轭类个数相同，因此可以期待：Sn 的不可约复表示和它的共轭类一一对应，这就是美妙的对称群表示论。

在组合数学中，n 的分划与 Young 表的组合学，对称函数，计数理论密不可分，很多组合问题最后都可以归结为 Young 表的计数。

如果你对这方面感兴趣，我推荐你阅读 Stanley 的名著《计数组合学》第二卷。

如果你不感兴趣，那我就推荐你一个公式：

Hook 公式