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