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