最近在複習數論和微分方程時，正好想到 yoshi 之前有寫過一個數字拆解的程式。當時稍為研究了一下，不過因為忙專案，所以就沒再繼續下去。現在剛好有點閒時間，就把問題重新思考一遍。數字拆解的意思是一個正整數 n 可以有幾種相加的方法。例如 2 = 2 + 0 = 1 + 1，有兩種加法、3 = 3 + 0 = 2 + 1 = 1 + 1 + 1，有三種拆解法，因此類推下去：

3 = 3 + 0 = 2 + 1 = 1 + 1 + 1
4 = 4 + 0 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1
5 = 5 + 0 = 4 + 1 = = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1

令 f, g 為兩函式, f : N -> N, f(n) 的值是 n 的拆解總數，g(i,j) 的值是用小於等於 j 的數字來拆解 i 的結果總合，則：

f(n) = Σg(i,j) , where 0 <= i < n and j = n - i

也就是說：

f(3) = g(2,1) + g(1,2) + g(0,3)
f(4) = g(3,1) + g(2,2) + g(1,3) + g(0,4)
f(5) = g(4,1) + g(3,2) + g(2,3) + g(1,4) + g(0,5)

g(3,2) 就是用 2 以下的數字來拆解 3 的總合。從上述中我們知道總共有兩個可能，分別是 2+1 和 1+1+1，因此 g(3,2) = 2。另外以 g(1,3) 來說，用 3 來拆解 1 是沒有意義的，同樣用 2 也是，所以 g(1,3) = g(1,1)，也用是用 1 以下的數字拆解 1，只有一種結果：1+0，所以 g(1,3) = g(1,1) = 1。由此可知，上述等式會變成：

f(3) = g(2,1) + g(1,1) + g(0,0)
f(4) = g(3,1) + g(2,2) + g(1,1) + g(0,0)
f(5) = g(4,1) + g(3,2) + g(2,2) + g(1,1) + g(0,0)

f(n) = Σg(i,j) , where 0 <= i < n and j = min(n-i, i)

當我把 f(1) 到 f(20) 各項數字以類似二元樹的方法排列出來後去剖析，發現在二元樹左半部的分支部份其實是很穩定在成長的，而右分支的部份比較浮動。既然左分支的數字很穩定，那麼我就把左分支的資訊儲存在一維陣列中，長度為 n+1。更重要的是，左分支的數正好依序是 f(0) 到 f(n/2) 的值！因此左分支就不用再煩惱了，我只要把每個介於 0 到 n-1 的數字拆解結果算出來，那麼左分支的值就自動會出現。右分支的部份比較浮動，因此我使用二維陣列來儲存，大小是 (n-6)*(n-5)/2。在空間上差不多是 n+1 + (n^2-11n+30)/2。在右分支的計算上，原本是還要遞迴地去計算 g(3,2) 的值，但是我的右分支所儲存的資訊並不需要重複計算，只需要拿已經計算好的數值繼續累加上去就可以了，這使得計算的時間從 O(n^3) 大幅降低到 O(n^2) 以下。這種差別有點類似以下的例子：

最後的結果，重複計算 100 次所花的時間為 30 ms，跑 1000 次約為120 ms，跑10000 次約為 1050 ms。所以每跑一次差不多介於 0.1 ms ~ 0.3 ms 之間。另外全部計算完畢後，serie 陣列中所儲存的資訊就是各個數字拆解的結果，所以從 1 到 100 中每個數字拆解也都一併計算完成了。

數字分解程式：

Definition:
PartitionsP(n) gives the number p(n) of unrestricted partitions of the integer n. I parsed the result from 1 to 20, and listed all in the form of binary tree. Then I found that the numbers of left side increase stably. So I wrote this program in Java to count PartiotionsP(n).