10.1.1 分拆數
和往常一樣，在放學後。
「我拿來了哦。」米爾嘉來到圖書室，手裡好像拿著村木老師出的題目。
她把卡片在桌子上攤開，我和泰朵拉好奇地湊過頭去。
從村木老師那裡拿到的卡片
假設有面值為 1 元、2 元、3 元、4 元……的硬幣。為了支付 n 元，請思考硬幣的組合方式有幾種。假設組合方式的個數為 Pn（各種支付方法稱為 n 的分拆方式，分拆方式的個數 Pn 稱為 n 的分拆數）。
比如，支付 3 元的方法有三種，一種是「1 枚 3 元硬幣」，另一種是「1 枚 2 元硬幣和 1 枚 1 元硬幣」，還有一種是「3 枚 1 元硬幣」。所以P3 = 3。
問題 10-1
P9 是多少？
問題 10-2
P15 < 1000 是否成立？
「這只不過是計算支付方法而已，應該很簡單啊。」高中一年級的學妹 泰朵拉高聲說道。
「是嗎？」我說。
「嗯？ P9 不就是要求出總金額為 9 元的支付方法的個數嗎？按照『使用 1 元硬幣的時候』『使用 2 元硬幣的時候』……這樣的順序來考慮不是很好嗎？」泰朵拉說。
「沒有這麼簡單哦，泰朵拉。相同面值的硬幣可以重複使用，所以即使是使用 1 元的時候，也必須要考慮『到底要用幾枚』。」我說。
「學長……我不是那個經常忘記條件的泰朵拉了。關於硬幣枚數的條件我知道啊。不過我覺得只要耐心數的話總能計算出來。」泰朵拉自信地說。
「是這樣嗎？即使一個一個地數也可能會出錯哦，我想還是用一般的方法解比較安全吧。先不管問題 10-1 中的 P9，問題 10-2 中的 P15 應該會 是個『了不得的數字』。」我說。
「會這樣嗎，學長？什麼是『了不得的數字』？只不過是 15 元的支付方法嘛。」泰朵拉說。
「泰朵拉，即使是 15 元，組合數也會大得驚人的。」我說。
「呯！」
一直沉默著沒有開口說話的米爾嘉用手拍了下桌子。那聲音響得讓我們都懷疑是不是哪裡爆炸了。
我們一下子停止了對話。
「泰朵拉，你到那邊的角落裡去。你坐到那裡窗邊的位子。我就坐在這裡。大家閉上嘴，安靜思考一下。」米爾嘉命令道。
聽了她的命令，泰朵拉和我互相點點頭，說：「知道了，我們馬上搬。」
——放學後的圖書室，我們都閉上嘴，開始學習。
10.1.2 舉例
硬幣的面額為正整數 (1, 2, 3, 4, ... )，有點與眾不同。使用這種硬幣支付 n 元，求支付方法的個數——分拆數 Pn。
和往常一樣，我從比較小的具體數字開始思考。通過具體例子來感受是非常重要的。
當 n 為 0 的時候，也就是支付金額為 0 元的時候，方法只有一個，那就是「不付錢」。可以說 P0 = 1。
P0 = 1 0 元的支付方法有 1 種
當 n 為 1 的時候，也就是支付金額是 1 元的時候，只有「使用 1 元硬幣」這一個方法。所以 P1 = 1。
P1 = 1 1 元的支付方法有 1 種
當 n 為 2 的時候，有 2 種支付硬幣的方法，一種是「使用 1 枚 2 元硬幣」，另一種是「使用 2 枚 1 元硬幣」。所以 P2 = 2。
P2 = 2 2 元的支付方法有 2 種
當 n 為 3 的時候，有 3 種支付硬幣的方法，一種是「使用 1 枚 3 元硬幣」，另一種是「使用 1 枚 1 元硬幣和 1 枚 2 元硬幣」，還有一種是「使用 3 枚 1 元硬幣」。
這樣寫成文字實在是太麻煩了，乾脆就把「使用 1 枚 2 元硬幣和 1 枚 1 元硬幣」這種支付方法表示成 2 + 1 就好了。也就是說，可以像下面這樣來考慮。
這樣一來，當 n = 3 的時候，就可以表示成以下 3 種情況。
也就是說 P3 = 3。
P3 = 3 3 元的支付方法有 3 種
嗯。P3 可以叫作「支付 3 元的方法的個數」，也可以稱為「將 3 分拆成幾個正整數的方式的個數」。所以我們給 Pn 這類數取名為分拆數。
如果 n 為 4 的話，就可以分成以下 5 種情況。嗯，我有點發現其中的訣竅了。
P4 = 5 4 元的支付方法有 5 種
如果 n 為 5 的話，就可以找到以下 7 種情況。
P5 = 7 5 元的支付方法有 7 種
如果像這樣擴大 n 的數值，就能夠逐漸看出一些有規律的東西。如果數字不擴大的話，很難發現其規律性。以前，米爾嘉曾經說過「少數例子無法體現規律性」。但是如果數字很大的話，接下去舉例就會逐漸變難。
好，暫且繼續進行下去。假設 n 為 6，那就可以展開成以下 11 種加法組合。
P6 = 11 6 元的支付方法共有 11 種
嗯，
，是不是與質數有關呢。
那麼 P7 是不是 13 呢？
P7 = 15 7 元的支付方法有 15 種
P7 是 15，真可惜，不是質數。
儘管如此，但它至少是在逐漸變大。這樣下去的話，考慮 n = 8 和 n = 9 不會出什麼問題吧？會不會數錯呢？算了，與其有閒工夫在這裡擔心，還不如耐心地數數看。
n = 8 的時候。
P8 = 22 8 元的支付方法有 22 種
終於到了計算 n = 9 的時候了。
P9 = 30 9 元的支付方法有 30 種
嗯，這下就解出了村木老師的問題 10-1。9 元的支付方法共有 30 種，9 有 30 種分拆法。
問題 10-2 該怎麼做呢？要數出 P15 是多少，那一定是個『了不得的 數字』吧。我應該先求出 Pn 的通項公式再求具體數值吧。
「放學時間到了。」
瑞谷老師登場了！啊，已經這麼晚了啊。
瑞谷老師是到了一定時間就會出現的圖書管理員。她帶著一副顏色很深的眼鏡，深到我們甚至看不清她的視線正看往哪裡，她像個機器人那樣精密地移動，一直走到圖書室中央，在那裡宣佈「放學時間到了」。
那就先到此為止吧——問題 10-1 的答案是 P9 = 30，而問題 10-2 的答案還不知道。
解答 10-1
P9 = 30