整數分拆問題是一個古老而又十分有趣的問題。所謂整數的分拆，指將一個正整數表示為若干個正整數的和。
整數分拆理論，主要是研究各種類型的分拆函數的性質及其相互關系。早在中世紀，就有關于特殊的整數分拆問題的研究。18世紀40年代，L.歐拉提出了用母函數法（或稱形式冪級數法）研究整數分拆，證明了不少有重要意義的定理，為整數分拆奠定了理論基礎。解析數論中的圓法的引進，使整數分拆理論得到了進一步發展。整數分拆與模函數有密切關系，并在組合數學、群論、概率論、數理統計學及質點物理學等方面都有重要應用。
原理
整數分拆問題是一個古老而又十分有趣的問題。所謂整數的分拆，指將一個正整數表示為若干個正整數的和。
分類
根據是否考慮分拆部分之間的排列順序，我們可以將整數分拆問題分為有序分拆（composition）和無序分拆（partition）。兩者之間的區別如下：
在有序分拆中，考慮分拆部分求和之間的順序。假定，之間不同的排序記為不同的方案，稱之為n的有序k拆分，如3的有序2拆分為：。我們可以將這個問題建模為排列組合中的“隔板”問題，即n個無區別的球分為r份且每份至少有一個球，則需要用個隔板插入到球之間的個空隙，因此總共的方案數為。
在無序拆分中，不考慮其求和的順序。一般假定，，我們稱之為n的無序k拆分，如3的無序k拆分為：。這種拆分可以理解為將n個無區別的球分為r份且每份至少有一個球。
一般情況下，無序拆分的個數用 p(n) 表示，則 p(2)=1，p(3)=2，p(4)=5。在通常情況下，整數分拆是指整數的無序分拆。
例子
例1 有1克、2克、3克、4克的砝碼各一枚，問能稱出多少重量，并各有幾種稱法。
該問題可以看成n拆分成1,2,3,4之和且不允許重復的拆分數，利用母函數計算如下：
表示稱出4克有2種方案，是和，以此類推，超出10克便無法稱出。
例2 將14分拆成兩個自然數的和，并使這兩個自然數的積最大，應該如何分拆？分析與解 不考慮加數順序，將14分拆成兩個自然數的和，有共七種方法。經計算，容易得知，將14分拆成時，有最大積。
例3 將15分拆成兩個自然數的和，并使這兩個自然數的積最大，如何分拆？
分析與解 不考慮加數順序，可將15分拆成下列形式的兩個自然數的和：。顯見，將15分拆成時，有最大積。
注：從上述兩例可見，將一個自然數分拆成兩個自然數的和時，如果這個自然數是偶數2m，當分拆成時，有最大積；如果這個自然數是奇數，當分拆成時，有最大積。
例4 將14分拆成3個自然數的和，并使這三個自然數的積最大，如何分拆？
分析與解 顯然，只有使分拆成的數之間的差盡可能地小（比如是0或1），這樣得到的積才最大。這樣不難想到將14分拆成時，有最大積。
拆分數估計
歷史上，有很多關于整數拆分的研究，其中包括英國劍橋大學的G.E戈弗雷·哈代和印度學者斯里尼瓦瑟·拉馬努金，拉馬努拉和哈代通過自己的研究，找到了一個相關的漸進的公式，描述如下。
正整數n拆分成若干個正整數之和，其不同的拆分數用表示，的母函數為：
則拆分數估計可以表示為：
拆分數估計定理證明
令
根據馬克羅林級數：
所以：
而
又由于
所以
故
所以
但
所以
設 有
曲線是向上凸的，所以曲線 在的切線為，即有
所以
因為,由均值不等式，得
所以
拆分數性質
性質一
整數n拆分成最大數為k的拆分數，和數n拆分成k個數的和的拆分數相等。
性質二
整數n拆分成最多不超過m個數的和的拆分數，和n拆分成最大不超過m的拆分數相等。
性質三
整數n拆分成互不相同的若干奇數的和的拆分數，和n拆分成自共軛的Ferrers圖像的拆分數相等。
拆分數計算方法
整數拆分可以利用漸進公式計算，隨著N的無限大，整數拆分估算值接近實際值，現代還可以利用計算機的方法進行求解。在這里，主要介紹4中計算方法。
遞推法
根據n和m的關系，考慮下面幾種情況：
（1）當時，不論m的值為多少，只有一種劃分，即；
（2）當時，不論 的值為多少（），只有一種劃分，即；
（3）當時，根據劃分中是否包含n，可以分為兩種情況：
（a）劃分中包含n的情況，只有一個，即；
（b）劃分中不包含n的情況，這時劃分中最大的數字也一定比n小，即n的所有劃分；
因此，。
（4）當時，由于劃分中不可能出現負數，因此就相當于f(n,n)；
（5）當時，根據劃分中是否包含m，可以分為兩種情況：
（a）劃分中包含 的情況，即，其中的和為，可能再次出現m，因此是的m劃分，因此這種劃分個數為；
（b）劃分中不包含m的情況，則劃分中所有值都比m小，即n的劃分，個數為；
因此，。
綜合以上各種情況，可以看出，上面的結論具有遞歸定義的特征，其中（1）和（2）屬于回歸條件，（3）和（4）屬于特殊情況，而情況（5）為通用情況，屬于遞歸的方法，其本質主要是通過減少n或m以達到回歸條件，從而解決問題。
詳細遞推公式描述如下：
參考源碼
這個版本的時間復雜度較高，運行效率很低。
動態規劃法
考慮到在上一節使用遞歸中，很多的子遞歸重復計算。如在計算時，劃分成為 ，進一步劃分為 ，接下來轉換為，這樣就產生了重復，然而，在遞歸的時候，每個都需要被計算一遍，因此可見，位于底層的狀態，計算的次數也越來越多。這樣在時間開銷特別大，是造成運算慢的根本原因，比如算120的時候需要3秒中，計算130的時候需要27秒鐘，在計算機200的時候....計算10分鐘還沒計算出來。
鑒于此，我們已經分析出了普通遞推關系中存在大量的冗余造成了重復計算，最終導致了運行時間太長，一種自然地想法是能夠用一種技巧，以避免重復計算？這里我們使用動態規劃的思想進行程序設計。
在上一節中，已經分析了狀態轉移的方程，因此，我們在求解子問題時，利用標記的思想，首先檢查產生的子問題是否在之前被計算過，這是因為對于相同的子問題，得到的結果肯定是一樣的，因此利用這一步去掉冗余的操作，極大減少了計算的時間開銷。對于沒有標記的子問題來說，一定是沒有被計算過，這樣，在計算完成后，順便標記一下子問題，以確保以后不用再重復計算。利用這個特性，可以確保所有的劃分子問題都無重復，無遺漏的恰巧被計算一次。
動態規劃版主要是利用了標記思想進行加速。
參考源碼如下：
這樣的算法效率快了很多。
生成函數法
對于整數拆分問題，也可以從另一個角度，即“母函數”的角度來考慮這個問題。所謂母函數，即為關于x的一個多項式，滿足：
則我們稱為序列 的母函數。我們從整數劃分考慮，假設的某個劃分中，1的出現個數記為，的個數記為，…，的個數 記為顯然有：
因此 的劃分數，也就是從1到 這 個數字的組合，每個數字理論上可以無限重復出現，即個數隨意，使它們的和為。顯然，數字 可以有如下可能，出現0次（即不出現），1次，2次，…，次等等。把數字用 表示，出現 次的數字用 表示，不出現用1表示。例如，數字2用 表示，2個2用 表示，3個2用 表示，k個2用 表示。則對于從1到 的所有可能組合結果我們可以表示為：
上面的表達式中，每個括號內的多項式代表了數字的參與到劃分中的所有可能情況。因此，該多項式展開后，由于，因此 就代表了 的劃分，展開后項的系數也就是的所有劃分個數，即。
由此我們找到了關于整數劃分的母函數，剩下的問題就是，我們需要求出 的展開后的所有系數。為此，我們首先要做多項式乘法，對于計算機編程來說，并不困難。我們把一個關于 的多項式用一個整數數組 表示，代表 的系數，然后卷積即可。
參考源碼：
這樣基于生成函數的方法實際上快了很多。
五邊形數法
設第n個五邊形數為，那么，即序列為：
對應圖形如下：
設五邊形數的生成函數為，那么有：
以上是五邊形數的情況。下面是關于五邊形數定理的內容：
五邊形數定理是一個由歐拉發現的數學定理，描述歐拉函數展開式的特性。歐拉函數的展開式如下：
即：
可見，歐拉函數展開后，有些次方項被消去，只留下次方項為的項次，留下來的次方恰為廣義五邊形數。
五邊形數和分割函數的關系：歐拉函數的倒數是分割函數的母函數，亦即：
其中 為 的分割函數。上式配合五邊形數定理，有：
在 時，等式右側的系數均為0，比較等式二側的系數，可得
因此可得到分割函數的遞歸式：
所以，通過上面遞歸式，我們可以很快速地計算的整數劃分方案數了。
參考代碼：
以上設計的代碼是最高效的。
通過比較上述四種算法，可見整數拆分的劃分方法比較多樣，且不同的算法運行效率差距比較大，需要仔細理解和思考。
參考資料 >