整數分劃

有關 p(n) 的等式有很多，但是至今沒有找到一個通項公式。由於 p(n) 在數論中的重要地位，因此大規模計算 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) 的值是多少？

通常的遞歸法其實是最糟糕的辦法，因此幾乎不用（很小的 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. 如果你按照遞推公式進行遞歸計算，會導致大量的函式調用和大量的重複計算並占用大量的空間。

其實這個算法在 Knuth 的《電腦程式設計藝術》第四卷組合算法中已經收錄了。

整數分劃與對稱群和組合數學的關係

說到分劃就不能不提對稱群和組合數學。

抽象代數中熟知的結論：n 階對稱群 Sn 的共軛類與 n 的分劃一一對應，而一個有限群的不可約復表示和它的共軛類個數相同，因此可以期待：Sn 的不可約復表示和它的共軛類一一對應，這就是美妙的對稱群表示論。

在組合數學中，n 的分劃與 Young 表的組合學，對稱函式，計數理論密不可分，很多組合問題最後都可以歸結為 Young 表的計數。

如果你對這方面感興趣，我推薦你閱讀 Stanley 的名著《計數組合學》第二卷。

如果你不感興趣，那我就推薦你一個公式：

Hook 公式