什麼是整數分劃
給定一個正整數 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) 的值是多少？
通常的遞歸法其實是最糟糕的辦法，因此幾乎不用（很小的 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 ( intn )
{ 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 \n", 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;
elsem = h + 1;
if ( t >= 2 )a[ ++h ] = t ;
}
for ( i = 1 ;i < m + 1 ;i++)
printf ("%d ", a[ i ]);
printf ( "\n" );
}
}
為了便於在百科的網頁中閱讀，我加進去不少空白，所以如果你直接拷貝的話代碼的縮進效果可能會不大好。: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 公式
