第二天。
放学后，在音乐教室里，我、盈盈还有米尔嘉三人在一起说话。
你们去讨论你们的欧拉，我呢就来弹我的巴赫。
盈盈坐在钢琴旁边弹着变奏曲边说。她是高中二年级的学生，虽然是和我一个年级的，但是不与我和米尔嘉同班。她担任钢琴爱好者协会“最强音”的会长，是一个非常喜欢琴键的小女孩。
“嗯，巴赫很好啊。”米尔嘉边笑边把两手放在身后，合着钢琴的拍子，一步一步在音乐教室里来回走动，一副很陶醉的样子。她的心情很好。
“对了，泰朵拉今天会来吗？不是只要有你在的地方，不管在哪里她都会过来的吗？”盈盈一边继续弹奏一边朝我问道。
泰朵拉。
“那孩子并不是一直追随着我哦。”我说。
就在那时，泰朵拉怀里抱着笔记本走进了音乐教室。
“啊，原来您在这里啊。我看您不在图书室，还想您怎么了呢。”
“她还追得真紧啊。”盈盈小声嘀咕道。
“是不是给你们添麻烦了？”泰朵拉打量着我们。
“没关系，泰朵拉。我也没什么要紧的事情做。”我说。
“你听到我那令人感动的演奏了吗？”盈盈问。
“嗯嗯，我听了。——啊，对了。”我说，“泰朵拉来得正好，大家一起来讨论一下昨晚的成果吧。米尔嘉，我可以写写分拆数的式子吗？”
“你的意思是说你求了通项 Pn 的有限项代数式吗？”米尔嘉顿时站起身，很严肃地问我。
“没有，不是，我并没有求出通项公式 Pn 的有限项代数式，而是求得了生成函数 P(x) 的无限积的形式。”我说。
“那就好。”米尔嘉的脸上又露出了笑容。
“那么就用前面的黑板吧。”我走到音乐教室前面，滑动了一下黑板，准备开始写字。米尔嘉和泰朵拉也凑了过来。
盈盈说：“啊呀，你们开始做数学了啊。”边说边停下了弹钢琴的手。
10.5.1 我的发言（分拆数的生成函数）
“为了解出问题 10-2，我想到了求分拆数 Pn 的通项公式。为此首先要求生成函数 P(x)。生成函数 P(x) 可以写成以下形式。”我说。
“我只是照定义式的样子写出了这个式子。我自己假设了问题 10-3‘寻找乘积形式的生成函数 P(x)’。但是在解问题 10-3 之前，为了便于说明，我们先来考虑一下接下来的问题 10-4，就是对硬币的枚数和种类加以限制的‘带有限制的分拆数’问题。”我说道。
问题 10-4 “ 带有限制的分拆数”
1 元硬币、2 元硬币和 3 元硬币各有 1 枚。支付 3 元的方法有几种？
“这个问题 10-4 并不难。因为限制了硬币的种类，只有 1、2、3 元，而且各种硬币都只有 1 枚，所以支付 3 元的方法只有两种：一种是使用 1 元和 2 元硬币，还有一种是使用 3 元硬币。这就是答案。”
解答 10-4
2 种。
“对了，利用问题 10-4，我们来说明一下生成函数。我来列举一下使用各种硬币能够支付的金额。”
使用 可以支付的金额是 0 元或者是 1 元。
使用 可以支付的金额是 0 元或者是 2 元。
使用 可以支付的金额是 0 元或者是 3 元。
“在这里，我们考虑一下以下式子。它使用了形式上的变量 x，指数部分表示‘可以支付的金额’。为了便于理解，1 可以写作 x0。”
“原来如此。真是有意思啊。”米尔嘉说。
“是啊。”我微笑着说。
“米尔嘉，你说什么‘原来如此’呢？学长，你说什么‘是啊’呢？我不明白。学姐，学长，拜托你们按照逻辑顺序把话说清楚好吗？”泰朵拉开始抱怨起来。这时，盈盈弹奏起滑稽的片段。
“你继续说说看。”米尔嘉说。
“泰朵拉，刚才的式子应该这样理解哦。”我说。
“展开后或许你就能理解了。各个硬币所能支付的金额变成了指数，而且可以支付的所有可能性都变成了项出现。”我又说。
“比如说，x1+2+0 这一项的指数 1 + 2 + 0 可以这样理解。”
1 使用 可以支付的金额 1 元2 使用 可以支付的金额 2 元0 使用 可以支付的金额 0 元
“学长，等一下。可我还是不太明白 x1+2+0 的意 思。如果使用 1 枚 、1 枚 、0 枚 ，那么指数就不应该是 1 + 2 + 0，而应该是 1 + 1 + 0，不是吗？”泰朵拉一副很认真的表情，不停地追问。
“啊，不对。这里考虑的不是‘k 元硬币的枚数’，而是‘k 元硬币可以支付的金额’。”我说。
“如果是我的话，我会把它称为‘k 元硬币贡献的部分’。”米尔嘉说。
“学长，我有点明白了。确实，看了展开式后，从 x 的指数能够看出使用 、、 进行支付的所有可能性，但是还是有些不可思议。为什么非得考虑 不可呢？”泰朵拉问道。
“这个嘛，是因为‘公式的展开方法’和‘支付方式的所有可能性的获取方法’的原理是相同的。将 展开时，各项是这样形成的。”我答道。
从 x0 + x1 中选择项，
从 x0 + x2 中选择项，
从 x0 + x3 中选择项，然后求积。
“这种选择方法和下面这种考虑支付方法时的做法一样。”
选择用 来支付的金额，
选择用 来支付的金额，
选择用 来支付的金额，然后求和。
“哈哈，原来如此。我明白了。为了求出所有组合，所以就把式子展开了。……呵呵。”泰朵拉似乎可以接受我的说法。
于是我继续解释。
“整理展开后的式子，我们可以得到以下式子。合并含有 xk 的项，也就是合并同类项，按照指数从小到大的顺序进行排列。”
“泰朵拉，x3 前的系数变成了 2 吧。你认为这个意味着什么呢？”我问道。
“嗯，你是问为什么系数是 2 吗？——因为 x3 的项只有两项啊。具体说来，就是 x0+0+3 和 x1+2+0。——原来如此，我明白了。x3 前的系数变成 2，就表示支付的金额是 3 元时支付方法有 2 种。”她说。
“正是如此。我们再来考虑一遍泰朵拉刚才说的话。在我们面前是使用了形式上的变量 x 的幂的和。然后，xn 的系数是‘支付金额是 n 时支付方法的个数’。那么，‘支付金额是 n 时支付方法的个数’究竟是什么呢？”我问道。
“‘支付金额是 n 时支付方法的个数’是……啊，是分拆数！”泰朵拉恍然大悟。
“是啊。因为问题 10-4 中，硬币的枚数和种类都受到限制，所以和村木老师的问题 10-1 及问题 10-2 中所出现的分拆数不同。但是，情况也非常相似。存在使用了形式上的变量 x 的幂的和，而它的系数又是‘支付金额是 n 时支付方法的个数’，这种情况只可能是生成函数了。也就是说， 是‘带有限制的分拆数’的生成函数。”我说。
问题 10-4 的“带有限制的分拆数”的生成函数
“原来如此……说到生成函数，就要出现无穷级数，我还以为会很麻烦呢。原来像 这类因式那么少的有限项积也会成为生成函数啊。迷你生成函数……”泰朵拉摆了一个捏饭团的手势。
“那么……”我继续说道。
◎ ◎ ◎
到此为止我们所说的是“带有限制的分拆数”。从这里开始，我们解除对硬币的枚数和种类的限制。但是，讨论的推进方法还是相同的。只不过这里不再是 这种“有限项和的有限项积”，而是“无限项和的无限项积”，如下所示。
无限项和的出现与不限制硬币枚数这一条件相对应。
无限项积的出现与不限制硬币种类这一条件相对应。
展开这个无限项和的无限项积后，支付方法的所有可能性就可以一口气算出来。求出乘积，合并同类项之后，我们就可以开始观察 xn 的项。这样一来，xn 的系数就是 n 的分拆数。为什么这么说呢？这是因为 xn 的系数就和“n 元的支付方法的个数”相同。
“系数是分拆数的形式上的幂级数”，也就是上面所写的无限项和的无限项积，就是“分拆数的生成函数”。这样一来，P(x) 就可以写成以下形式。
好了，在这里我们转变一下视角。将形式上的变量 x 想象成 0 ≤ x < 1 的实数，然后用等比数列的公式来计算。这样一来，k 元硬币贡献的部分就可以表示成以下的分数形式。
P(x) 中的无限项和都可以用这个公式来表示成分数形式。
“无限项和的无限项积”变为了“分数的无限项积”。这就是变成了乘积形式的生成函数 P(x)。我们把 ×（乘号）统一写成 ·（点号）。
解答 10-3 （分拆数 Pn 的生成函数 P(x)“积的形式”）
我们来整理一下到此为止的内容吧。为了求出村木老师问题 10-2 中的 P15，我想到要先求出通项公式 Pn。为此，我又想到了求 Pn 的生成函数 P(x)，并自己假设了问题 10-3。最后，如上面的解答 10-3 所示，我求得了乘积形式的生成函数 P(x)。
接下来，我准备考虑下面的问题 X。
问题 X
将下面的函数 P(x) 进行幂级数展开的时候，xn 的系数为多少？
xn 的系数为 Pn。求出通项公式 Pn 后，再来探讨一下问题 10-2 中的不等式 P15 是否小于 1000。
“求分拆数的通项公式”的“旅行地图”
到这里我不再继续说了。
◎ ◎ ◎
“你是想正面求解吗？”米尔嘉立即开口问道。
“是的。”
“嗯。不过如果只是证明问题 10-2 的不等式的话，是没有必要非求出 Pn 不可的，不是吗？”米尔嘉说。
“这个……道理上来讲是这样的。”我开始不安起来。
“不过我既没有求出通项 Pn，也没有求出 P15，就把问题 10-2 解答出来了。”米尔嘉说。
“啊？”
10.5.2 米尔嘉的发言（分拆数的上限）
“只要证明问题 10-2 的不等式 P15 < 1000 的话，不一定非要求出 P15 的值。”米尔嘉一边这样说，一边跟我调换了一下位置，站在了黑板前。
“分拆数 Pn 会急剧增加，变成泰朵拉所说的‘了不得的数字’。所以在这里，我想先分析一下分拆数 Pn 的上限在哪里。”
“上限指的是什么呢？”泰朵拉马上问道。
“上限指的是，对于任意大于等于 0 的整数 n，满足 Pn ≤ M(n) 的函数 M(n)。虽然 Pn 会随着 n 的变大而变大，但是不会大于 M(n)，这个 M(n) 就是上限。另外，上限有无数个，而不是仅限于一个。”
“就是说上面有一个界限么？”泰朵拉把手放在头顶上说。
“对。上限这个词有时候表示常数，在这里却不是这样。M(n) 说到底就是关于 n 的函数。那么，观察 P0, P1, P2, P3, P4 会发现，它们都与斐波那契数列 F1, F2, F3, F4, F5 相等。”
米尔嘉用手指点过 1, 2, 3, 4，在 5 那里停下了。
“遗憾的是 P5 不等于 F6，尽管这样，但因为我们知道 P5 = 7，F6 = 8，所以依然可以得到
于是我推测，虽然 Pn = Fn+1 这个等式不成立，但
这个不等式也许是可以成立的。接下来，可以证明它确实是成立的。也就是说，这里使斐波那契数列 Fn+1 作为 Pn 的上限 M(n) 了。证明的时候使用数学归纳法即可。”米尔嘉说。
◎ ◎ ◎
根据斐波那契数列求分拆数 Pn 的上限
假设分拆数 ，斐波那契数列 。这时，对于所有的整数 n ≥ 0，以下不等式成立。
下面用数学归纳法来证明。
首先，当 n 为 0 和 1 时，Pn ≤ Fn+1 成立。
然后，对于任意整数 k ≥ 0，只要证明
这个式子成立就可以了。
为什么这么说呢？这是因为如果这个式子成立的话，那么
由 P0 ≤ F1 和 P1 ≤ F2 可以得到 P2 ≤ F3。
由 P1 ≤ F2 和 P2 ≤ F3 可以得到 P3 ≤ F4。
由 P2 ≤ F3 和 P3 ≤ F4 可以得到 P4 ≤ F5。
由 P3 ≤ F4 和 P4 ≤ F5 可以得到 P5 ≤ F6 ……
也就是说，对于任意整数 n ≥ 0，都有 Pn ≤ Fn+1 成立。这是数学归纳法的解法。这些说明是特意为泰朵拉做的补充说明，因为我看到她现在头上有一个大大的问号。
现在，如果让我们来计算“k + 2 元的支付方法”的话，根据最小面值的硬币，我们可以把支付方法分为以下三种情况。
（1）最小面值的硬币为 的时候
（2）最小面值的硬币为 的时候
（3）最小面值的硬币大于等于 的时候
接下来，进行如下操作，将“k + 2 元的支付方法”变更为“k + 1 元的支付方法”或者是“k 元的支付方法”。
（1）最小面值的硬币为 的时候：去掉 1 枚 ，这样剩下来的硬币就 是“k + 1 元的支付方法”了。
（2）最小面值的硬币为 的时候：去掉 1 枚 ，这样剩下来的硬币就是“k 元的支付方法”了。而且，这种支付方法中最小面值的硬币不是 。
（3）最小面值的硬币大于等于 的时候：假设最小面值的硬币为 ，取 1 枚 ，将它进行以下替换。
替换之后，将 去掉 1 枚，这样剩下的硬币就是“k 元的支付方法”了。而且，这种支付方法中最小面值的硬币是 。
也就是说，按照以上操作方法，我们可以将任意的“k + 2 元的支付方法”变更为“k + 1 元的支付方法”或者是“k 元的支付方法”。这时，变更出来的支付方法都会不同。换句话说，变更出来的支付方法不会互相冲突。
可能理解上会比较困难吧，我们来具体地看一下 k + 2 = 9 的分拆，可以用下面的图表来说明。去掉的硬币用两条线划掉，替换的硬币用下划线表示。有很多 1 的地方就用 ... 代替了。
从这样的操作方法中我们可以看到，“k + 2 元的支付方法”的个数不可能超过“k + 1 元的支付方法”的个数与“k 元的支付方法”的个数之和。
那么，从以上讨论可以看出，对于所有的整数 k ≥ 0，分拆数 Pk+2, Pk+1, Pk 之间存在以下关系。
那么，假设
成立，结合上述结果，我们可以认为下述不等式是成立的。
根据斐波那契数列的定义，右边与 Fk+3 相等。所以，以下不等式也成立。
综上，对于任意整数 k ≥ 0，下式是成立的。
通过数学归纳法的证明可知，对于任意整数 n ≥ 0，Pn ≤ Fn+1 成立。
好了，到此为止我们的工作就结束了。看来分拆数 Pn 要比斐波那契数列 Fn+1 矮一头啊。——啊，我们的工作还没完，还没把问题 10-2 解决呢。根据 ，我们可以制作出以下斐波那契数列的表格。
n012345678910111213141516...Fn01123581321345589144233377610987...从这个表中可以看出 F16 = 987，所以以下不等式成立。
这样答案就出来了。
P15 < 1000
所以问题 10-2 的不等式是成立的。
好了，这下我们的工作才真正告一段落。
我们没有求出 Pn 的通项公式，别说通项公式了，就连 P15 为多少我们都没有求，就完成了证明。
解答 10-2
P15 < 1000 成立。
米尔嘉很满足地关上了话匣子。
10.5.3 泰朵拉的发言
“嗯，那个……”泰朵拉举起手。
“嗯，泰朵拉，你有什么问题？”米尔嘉用手指了一下。
“没有，不是问问题……我也解出了问题 10-2，想做一下发言。”泰朵拉害羞地说。
“好的啊，那我和你交班。”米尔嘉边说边递出粉笔。
“没有，那个，我很快就会发言完的。15 元的支付方法我都罗列出来了。这么一数，得到 P15 的值为 176，
P15 = 176 < 1000
所以问题 10-2 的不等式成立。”
泰朵拉边说，边摊开她的笔记本给我们看。
米尔嘉迅速检查了一下泰朵拉列举的支付方法。
“嗯，确实是对的。这个……是泰朵拉艰苦奋战后的胜利成果。”米尔嘉苦笑着，摸了摸泰朵拉的头。
“呵呵，这次总算没有算错。”泰朵拉说。
我什么都说不出口。