第10章分拆数

告白的答案在银河的终点

——小松美和[8]

10．1图书室

10．1．1分拆数

一如往常的放学后。

「我拿来了。」米尔迦边说边走进图书室，她似乎是拿到了村木老师的问题。

我和蒂蒂望向放在桌上的纸张。

(从木村老师那里得到的卡片)

假设有面额为1元、2元、3元、4元……的硬币，倘若必须支付n元，其组合方式有几种？令组合的个数为P<n>(这种支付方法称为n的分拆，分拆的个数P<n>称为n的分拆数)。

举例来说，支付3元的方法有「3元硬币1枚」、「2元硬币一枚与1元硬币1枚」、以及「1元硬币3枚」这3种方式，故P<3>＝3。

问题10－1

求P<9>。

问题10－2

P<15>＜1000是否成立？

「只是算支付的方法，应该很简单吧。」高中一年级的学妹——活力少女蒂蒂说。

「是吗？」我说。

「咦？所谓P<9>就是支付9元的状况吧，依照『使用1元硬币的状况』、『使用2元硬币的状况』……的顺序思考就可以了吧？」

「蒂蒂，并没有那么简单，因为可以使用同样的面额，所以即使是使用1元的状况，也要考虑到『使用了几枚』。」

「学长我不会一直都是不小心忘了条件的蒂德菈喔，关于枚数我很清楚，只要冷静地慢慢往上数就没问题了。」蒂蒂似乎充满自信。

「是吗？一直往上数的话会失败喔，我想用广义的解法会比较安全，而且问题10－1的P<9>先不提，问题10－2的P<15>，应该会变成『非常大的数』。」

「真的吗，学长？『非常大的数』是多大？只是支付15元的吧？」

「蒂蒂，虽然只有15元，但是组合起来的话立刻就会爆发……」

碰。

一直没有说话的米尔迦用手拍了桌子，她想仿真爆发的音效吗？

我们愕然地停下对话。

「蒂德菈到那个角落，你去窗边的位置，而我在这里，大家都不要小说话、安静地思考。」

米尔迦一声令下，蒂蒂和我都点头同意。

「知道了还不快点行动。」

……我们就在放学后的图书室里在无声地开始用功。

10．1．2思考实例

面额依正整数(1，2，3，4，……)变化的硬币，用这些硬币来支付n元，这是求支付的方法数——分拆数——的问题。

和从前一样，我先从小的数进行具体的思考，用实例来抓到感觉是很重要的。

当n＝0的时候，也就是支付金额为0的状况……只有「不支付」一种方法，方法数为1，也可以说P<0>＝1。

P<0>＝1支付0元的方法有1种

当n＝1的时候……只有「使用1个1元」一种方法，所以P<1>＝1。

P<1>＝1支付1元的方法有1种

当n＝2的时候……有「使用1个2元」与「使用2个1元」的方法，所以P<2>＝2。

P<2>＝2支付2元的方法有2种

当n＝3的时候……有「使用1个3元」与「使用1个2元、1个1元」与「使用3个1元」3种方法。

由于再这样写下去太麻烦，所以「使用1个2元、1个1元」这种方法，就用2＋1表现，也就是这种写法。

2＋1(2元用1枚，1元用一枚)

当n＝3时有以下的3种方法。

3＝3

＝2＋1

＝1＋1＋1

等同于P<3>＝3。

P<3>＝3支付3元的方法有3种

唔，所谓的P<3>虽然是「支付3元的方法数」，不过也可以说成「将3分拆成数个正整数的方法数」，所以才被命名为「分拆数」吧。

n＝4的话，如下有5种，一共5个分拆，嗯，我已经抓到诀窍了

4＝4

＝3＋1

＝2＋2

＝2＋1＋1

＝1＋1＋1＋1

P<4>＝5支付4元的方法有5种

n＝5的话……有以下7种。

5＝5

＝4＋1

＝3＋2

＝3＋1＋1

＝2＋2＋1

＝2＋1＋1＋1

＝1＋1＋1＋1＋1

P<5>＝7支付5元的方法有7种

像这样让n逐渐变大时，就能稍微发现一些规则，数字倘若不够大，要找出规则性就不容易，以前米尔迦说过「少量的样本不容易发现规则」，但是数字增加得太大，具体举例就会变得困难。

继续下去吧，令n＝6，有以下11种表现方法。

6＝6

＝5＋1

＝4＋2

＝4＋1＋1

＝3＋3

＝3＋2＋1

＝3＋1＋1＋1

＝2＋2＋2

＝2＋2＋1＋1

＝2＋1＋1＋1＋1

＝1＋1＋1＋1＋1＋1

P<6>＝11支付6元的方法有11种

嗯，P<2>，P<3>，P<4>，P<5>，P<6>＝2，3，5，7，11，是和质数有关的规律吗？

P<7>会是13吗？

7＝7

＝6＋1

＝5＋2

＝5＋1＋1

＝4＋3

＝4＋2＋1

＝4＋1＋1＋1

＝3＋3＋1

＝3＋2＋2

＝3＋2＋1＋1

＝3＋1＋1＋1＋1

＝2＋2＋2＋1

＝2＋2＋1＋1＋1

＝2＋1＋1＋1＋1＋1

＝1＋1＋1＋1＋1＋1＋1

P<7>＝15支付7元的方法有15种

P<7>有15种，可惜不是质数。

而且也开始快速增加了，这样下去，当n＝8与n＝9的时候没问题吗？会不会算错啊，不，与其担心这个，不如继续尝试。

n＝8的状况。

8＝8

＝7＋1

＝6＋2

＝6＋1＋1

＝5＋3

＝5＋2＋1

＝5＋1＋1＋1

＝4＋4

＝4＋3＋1

＝4＋2＋2

＝4＋2＋1＋1

＝4＋1＋1＋1＋1

＝3＋3＋2

＝3＋3＋1＋1

＝3＋2＋2＋1

＝3＋2＋1＋1＋1

＝3＋1＋1＋1＋1＋1

＝2＋2＋2＋2

＝2＋2＋2＋1＋1

＝2＋2＋1＋1＋1＋1

＝2＋1＋1＋1＋1＋1＋1

＝1＋1＋1＋1＋1＋1＋1＋1

P<8>＝22支付8元的方法有22种

终于到n＝9了。

9＝9

＝8＋1

＝7＋2

＝7＋1＋1

＝6＋3

＝6＋2＋1

＝6＋1＋1＋1

＝5＋4

＝5＋3＋1

＝5＋2＋2

＝5＋2＋1＋1

＝5＋1＋1＋1＋1

＝4＋4＋1

＝4＋3＋2

＝4＋3＋1＋1

＝4＋2＋2＋1

＝4＋2＋1＋1＋1

＝4＋1＋1＋1＋1＋1

＝3＋3＋3

＝3＋3＋2＋1

＝3＋3＋1＋1＋1

＝3＋2＋2＋2

＝3＋2＋2＋1＋1

＝3＋2＋1＋1＋1＋1

＝3＋1＋1＋1＋1＋1＋1

＝2＋2＋2＋2＋1

＝2＋2＋2＋1＋1＋1

＝2＋2＋1＋1＋1＋1＋1

＝2＋1＋1＋1＋1＋1＋1＋1

＝1＋1＋1＋1＋1＋1＋1＋1＋1

P<9>＝30支付9元的方法有30种

嗯，这样村木老师的问题10－1就解决了，付9元的方法有30种，9的分拆数是30。

那10－2该怎么办呢？就算硬数P<15>想必也是『非常大的数』，还是应该求P<n>的一般项吧。

「现在是闭校时间。」

瑞谷老师出现了！已经这么晚了啊。

瑞谷老师是会定时出现的管理员老师，她会带着无法判断视线方向的深色眼镜，像机器人一样走到图书馆的中央宣布时间到了。

总之先到这里……已经知道问题10－1的答案是P<9>＝30了，不过还不知道问题10－2的答案。

※※解答10－1

P<9>＝30

10．2回去的路上

10．2．1斐波那契手势

我们三个人走在往车站的路上。

蒂蒂摆出一副像是要猜拳的动作。

「你在做什么？」我问。

「斐波那契手势。」

「那是什么？」

「也难怪学长不知道，因为这是我想出来的手势。」

「……？」

「这个就是代表『我非常喜欢数学！』的意思，是爱好数学的人打招呼的方式，无论是在见面或道别时都可以使用喔。因为是手势，所以即使语言不通，或是隔了一些距离的时候也可以传达给对方知道。很厉害害吧。」

蒂德菈露出一副得意的样子。

「那来试试看吧。」

蒂蒂将手伸到我的鼻子前面，连续摆动了四次。

「知道了吗？」

「……知道什么？」

「要仔细看手指比的数字，是1，1，2，3这样子增加唷。」

蒂蒂又再重新比了一次，手指数的确是1，1，2，3逐渐增加……然

「然后看到斐波那契手势的时候就要比出猜拳的布来响应。因为1，1，2，3的下一个是5，用手指比出斐波那契数列，这就是斐波那势。」

「……啊，是喔。米尔迦，关于刚才的P<9>……」

「啊、啊～～学长，不要忽视我啊～～」

我看向米尔迦，她的手指也在跟着比划。

「……咦？连米尔迦也在做手势，你到底在做什么啊？」我有点无力地发问。

「斐波那契手势。不过蒂德菈，5以后要怎么办？用两手来做出3＋5＝8吗？假如斐波那契手势继续下去的话，全世界的人的手都不够用唷。」米尔迦说。

「不，到5就停了。那就一起来比吧，我比出1，1，2，3的话，就要回应5喔……一、一、二、三……来～～」

米尔迦笑着伸出手。

……真让人觉得不好意思，我们又不是小学生。

不过蒂蒂仍然竖起三根手指并用大大的眼睛凝视我，真是拿她没办法，我只好伸出手回应。

「……五。」

「好～～谢谢。」

活力少女今天也是精神饱满。

10．2．2分组

我们走到了大马路旁，因为护栏让道路变得狭小，所以我们按照蒂蒂、我、米尔迦的顺序排成一列前进，蒂蒂不断地转头说话似乎有点危险，而我对于米尔迦站在我的身后，总觉得不太自在。

「问题10－1是手的运动，问题10－2就是脑的运动了。」米尔迦说。

蒂蒂转头说：「我已经完成问题10－1了，现在正在算问题10－2，实际写P<15>的时候才知道『非常大的数』是什么意思，个数突然膨胀起来了，虽然写到了50种，仍然没有结束，但是我想绝对不会超过1000种。」

「蒂蒂，看前面看前面，要小心前面的电线杆。」

「没问题的，学长，话说回来，P<9>是29种吧？」蒂蒂把笔记本对着我们打开。

①×8②＋⑦①×2＋⑦

③＋⑥①＋②＋⑥①×3＋⑥

④＋⑤①＋③＋⑤①×2＋⑤

①×2＋②＋⑤①×4＋⑤①＋④×2

①×2＋③＋④①＋②×2＋④①×3＋②＋④

①×5＋④③×3①＋②＋③×2

①×3＋③×2②×3＋③①×2＋②×2＋③

①×4＋②＋③①×6＋③①＋②×４

①×3＋②×3①×5＋②×2①×7＋②

①×⑨⑨

咦……29种？不是30种吗？

「这要怎么看？」我问。

「啊，就跟你看到的一样，像这个①×3，就是支付1元硬币3个的意思。」

「喔，原来如此，写法还真多。」

「没有②＋③＋④。」米尔迦越过我的肩膀看着笔记本点出问题，她的长发碰到我，同时传来淡淡的果香。

「唉呀，我明明确认了好几次……好痛！」蒂蒂的头撞到广告牌，我刚刚不是才提醒过……

车站到了。

「那我就先走了，明天见。」米尔迦轻轻地敲了一下蒂蒂的头身离开，她的路线和我们刚好相反。

「啊～～米尔迦学姐走了……我还在想可以用斐波那契手势向她的……」蒂蒂嘟起嘴，不断地动起指头。

这时候米尔迦举起右手，将五根手指在空中挥舞，她没有放慢速度，也没有回头。

10．3『Beans』

在蒂蒂提议要不要去喝杯咖啡后，我们就来到了车站前的『Beans』，她今天坐在我对面的位置上。

蒂蒂将牛奶加入咖啡后就只是在发呆，也忘了用汤匙搅拌，她似乎和平常有点不太一样，接着还说出像是自言自语的话。

「我也希望数学能变得更好一点，虽然没有忘记条件很重要，不过只有这样还是不行，真辛苦，想单纯用手算出P<15>，可是P<15>看起来是个『非常大的数』……」

她叹了一口气。

「啊～～学长的心里有没有我的位置呢……」

「咦？」

「咦？」蒂蒂的脸越来越红，「我刚才说出口了吗？啊，刚才的不算！不对，也不是不算！啊～～真是的。」

她的两只手在脸前晃来晃去，这不是斐波那契手势。

过了一会儿……

蒂蒂低下头缓缓道出：

「……学长国中三年级的时候，也就是我国中二年级时，学长在校庆的时候有发表过论题吧，是关于二进制的论题。在发表的最后，学长说了『数学是超越时间的』，历史上有许多数学家研究过二进制，于是才有现代计算机的诞生，而『数学是超越时间的』这句词组也留在我的心里，举例来说，在十七世纪研究二进制的莱布尼兹并不晓得二十一世纪有电脑的事，虽然他已经去世了，但是数学却超越了时间活着，并传达给现代的人……我从学长的话里感受到这件事情，啊，没错，我真心地认为觉得数学是可以超越时间的。」

……这么说起来，我好像有发表这种论题。

「学长当时放学后都会到图书间去吧，校庆之后，因为想要更接近学长，我也开始会去图书间……我就在图书间的角落看书，但是学长都一直忙着计算，完全没注意到我，也因为这样，那年冬天我获得了最常利用图书间的奖。」

她抬起头露出不好意思的笑容。

唔……我真的没注意到，我一直以为这个没人会来的图书间只有我一个人。

「当我……知道能和学长进同一个高中的时候，真的很高兴，能下定决心写信给学长真是太好了，我非常喜欢你叫我『蒂蒂』，当你说出『蒂蒂好厉害』的时候，我真的觉得好像做什么都会成功，而且学长也带我去了天文台……能跟学长还有米尔迦学姐一起讨论数学，让我非常快乐。」

……这么说起来，我们是有去过天文台没错。

「不过……我也有垂头丧气的时候，虽然能和学长互相讨论，但是自己一个人却什么都做不到，像今天我就失败了。」

嗯……我能懂你的心情，我看着米尔迦时也是一样的感觉。

「我的位置……学长的心里有我的位置吗？对学长而言，我可能只是一个蹦蹦跳跳的学妹而已，在学长的心里是否有我的位置呢？就算只是偶尔愿意教教我数学也可以……」

在我的心中某个看不见的领域……为了蒂蒂而存在的领域……

我开口说：

「嗯，无论什么时候都有。我喜欢和蒂蒂说话，我很佩服你的率直和理解能力，就像以前在『学仓』答应的一样，我任何时候都可以教你数学。嗯，与你的约定并没有改变……而且我也是只有自己一个人就什么都做不到，国中的时候在图书间计算虽然有趣，但是我现在更快乐，因为有能和我自由讨论数学的人……在我的心里，属于蒂蒂的位置一直都在，对我来说，你是我很重要的朋友。」（JoyJ：于是是朋友啊……）

「停～～」蒂蒂向我伸出右手、伸出她的五根手指。「谢、谢谢，我非常高兴。但是我似乎说得太超过了，所以到此为止。」

蜿蜒的道路盘旋在空间之中。

啊，原来如此，每次在回家的路上，蒂蒂会慢慢走的理由……

她……希望扩大和我一起分享的领域。

在这个高中生活中有限的时空里。

10．4自家

自家。

电子钟上显示着23点59分，23和59都是质数。（JoyJ：……）

家人都睡了，我在房间里算着数学，这是我最幸福的时刻。

家人对于我在挑战什么样的算式没有兴趣，就算完成有趣的算式变化、很高兴地和他们说明，也只会得到一句「好厉害」而已。

朋友是很珍贵的，米尔迦与蒂蒂可以和我一起面对问题、一起解决、一起检讨，穷尽知识与其对战、研讨解法，谈话之中有着名为的共通语言……我喜欢这样的时间，这和国中时在图书间度过的时不同，那时候只有我一个人在计算……不对不对，在那个时候的那个地方，蒂蒂或许也在吧……

……继续演算村木老师的问题吧，思考分拆数P<n>，来挑战是否能用生成函数解出P<15><1000成立与否的问题10－2。

所谓生成函数，就是使用x的乘幂将数列全部的项结合到一个函数中，在此之前，我和米尔迦曾经使用生成函数求出斐波那契数列与卡塔兰数的一般项，这次的P<n>是否也能用生成函数来找出一般项呢？只要能找出一般项P<n>的『对n的闭公式』，就能迅速解开问题10－2了。

将目前为止知道的P<n>做整理。

n0123456789……

P<n>11235711152230……

将这个数列的生成函数设为P(x)×P(x)的定义如下，这同时是生成函数的的定义。

P(x)＝P<0>x<0次方>＋P<1>x<1次方>＋P<2>x<平方>＋P<3>x<立方>＋P<4>x<4次方>＋P<5>x<5次方>＋……

将P<0>，P<1>，……的值实际代入，由于n次的系数为P<n>，所以会变成下面的式子……

P(x)＝1x<0次方>＋1x<1次方>＋2x<平方>＋3x<立方>＋5x<4次方>＋7x<5次方>＋……

为了不让各项混在一起而假设出形式上的变量x，将数列以系数的形态拥抱在名为生成函数的母亲怀里。

接着下一步是求出生成函数的『对x的闭公式』。

在求斐波那契数列F<n>的时候，是用递推公式来求闭公式，以x将P(x)的系数做转换，真是令人怀念。

求卡塔兰数C<n>时，是用生成函数的积求出闭公式，也体会到『平分』的乐趣。

分拆数P<n>又是如何呢？而且也不是求出生成函数之后，问题就会像魔法一样解开，有必要找出关于这个数列的本质。

继续研究分拆数的生成函数吧，夜晚还很漫长。

10．4．1为了选出来

我在房间里绕着圈子思考，虽然动手调查具体的数字很重要，但这样下去只会让组合的数字爆发而已。在变成『超级大的数』之前，必须跳到广义的解法，也就是米尔迦口中「脑的运动」。思考，思考吧。

……我打开窗户呼吸着夜晚的空气，听着远方传来的狗叫声……为什么我会喜欢数学呢？数学到底又是什么呢？米尔迦是这么说的：

「如康托尔所说『数学的本质是自由』，尤拉老师是自由的，他将无限大或无限小的概念灵活运用在自己的研究上，无论是圆周率的π，虚数单位的i，或是自然对数的底e，都是尤拉老师开始使用的文字，老师在当时无法横渡的河上架一座桥，就像在柯尼斯堡上架设新桥一样。」

桥……我能在未来的某处架设出一道新的桥吗？

稍微脱离生成函数来思考看看，自己是不是曾经有解过类似的问题呢？回想起来、回想起来……

『……对不起，我记不住。』

『……不对，不是要记起来，而是要思考、思考。』

似乎和蒂蒂曾经有过这种互动呢，发现自己把『思考很重要』这件事情『记起来』后，我笑了，思考虽然很重要，回想也是一样啊。

和蒂蒂的对话是在演算二项式定理的时候，将(x＋y)<n次方>展开后，会出现组合的数，这让蒂蒂十分惊讶，也让她知道()<n,k>和<组合,n,k>是同样的意思。

(x＋y)将变为n次方时，会从n个(x＋y)因式中各自选出x或y，然后成为x与y积的项，整合同类项之后，就是选出的方法数。

例如(x＋y)3展开的时候，从x与y的各因式中提出3个，就会产生下面8个项。

(<x>＋y)＋(<x>＋y)＋(<x>＋y)＝xxx＝x<立方>

(<x>＋y)＋(<x>＋y)＋(x＋<y>)＝xxy＝x<平方>y

(<x>＋y)＋(x＋<y>)＋(<x>＋y)＝xyx＝x<平方>y

(<x>＋y)＋(x＋<y>)＋(x＋<y>)＝xyy＝xy<平方>

(x＋<y>)＋(<x>＋y)＋(<x>＋y)＝yxx＝x<平方>y

(x＋<y>)＋(<x>＋y)＋(x＋<y>)＝yxy＝xy<平方>

(x＋<y>)＋(x＋<y>)＋(<x>＋y)＝yyx＝xy<平方>

(x＋<y>)＋(x＋<y>)＋(x＋<y>)＝yyy＝y<立方>

将这些全部加起来『整合同类项』之后，就成为积的展开。

(x＋y)(x＋y)(x＋y)＝1x<立方>y<0次方>＋3x<平方>y<1次方>＋3x<1次方>y<平方>＋1x<0次方>y<立方>

系数的1，3，3，1就是符合选出3个x、2个x、1个x、0个x的方法数，也就是说，将系数以表示的话，会成为下式。

(x＋y)(x＋y)(x＋y)＝()<3,3>x<立方>＋()<3,2>x<平方>y<1次方>＋()<3,1>x<1次方>y<平方>＋()<3,0>y<立方>

回想到这里，脑海中浮现出蒂蒂佩服的脸，让绕着房间走的我停下脚步。

咦？

好像有什么很重要的地方让我在意。

『蒂蒂佩服的脸。』……不，在更前面。

『不是要记起来，而是要思考。』……在这之后。

『依照选的方法数产生系数。』……。就是这个。

依照选的方法数产生系数。

用蒂蒂的分类方法——从因式中选出——嗯，有关系，一定和分拆数的生成函数有关，将算式当成无限和的无限积就好了，我知道了。

『知道了还不快点行动。』米尔迦的声音在我的心中响起。

我急忙开始计算，由于是无限积，所以不能称为『对x的闭公式』，不过应该可以得到积形式的生成函数P(x)。

……深夜的自家中，我安静地开始用功。

※※问题10－3(我设定的问题)

令分拆数的生成函数P(x)，求出积形式的P(x)。

10．5音乐教室

隔天。

在放学后的音乐教室，英英、我、还有米尔迦三个人在聊天。

「『必读尤拉』？我们这里是说『必弹巴哈』。」

英英一边用平台钢琴弹着歌德堡变奏曲一边聊天，她同样是高中二年级，虽然同学年，却跟我和米尔迦不同班级，她是钢琴社团『极强音』的社长，是个非常喜欢钢琴键盘的少女。

「嗯，巴哈不错。」米尔迦微笑地将手背在背后，配合音乐一步一步地绕着音乐教室享受气氛，她的心情似乎很好。

「不过今天蒂德菈儿没来吗？不是不管你在哪她都会出现吗？英英边演奏边对我说。

蒂德菈儿？

「她并没有特别跟着我吧。」我回答。

刚好这个时候，抱着笔记本的蒂蒂进入音乐教室。

「啊，学长在这里啊，我还在想学长不在图书室会去哪里呢。」

(这不是很认真地跟在后面吗？)英英小声地说。

「打扰到你们了吗？」蒂德菈看看我们。

「不会，蒂蒂，我们也没有在做什么。」我说。

「要听我感人的演奏吗？」

「好的好的……啊，对了。」我说：「蒂蒂来了正好，大家要不要听一下我昨晚的数学成果，米尔迦，我可以写出分拆数的式子吧。」

「是求一般项P<n>的闭公式吗？」米尔迦突然停下脚步，用严峻的眼神看着我问。

「不，不是，不是求一般项P<n>的闭公式，我算出了生成函数P(x)的无限积形式。」我回答她。

「那就好。」米尔迦再度恢复笑容。

「使用前面的黑板吧。」

我走到音乐教室前面，移动滑动式黑板做好准备，米尔迦和蒂蒂也靠近我。

英英说出「哎呀，要开始算数学了」后，弹钢琴的手就停了下来。

10．5．1我的发表(分拆数的生成函数)

「为了解开问题10－2，我采取的方式是求分拆数数P<n>的一般项，为此先从求生成函数P(x)开始，生成函数P(x)如下。」

P(x)＝P<0>x<0次方>＋P<1>x<1次方>＋P<2>x<平方>＋P<3>x<立方>＋P<4>x<4次方>＋P<5>x<5次方>＋……

「这是原本的定义，我自己设定了『找出积形式的生成函数P(x)』，把这当成是问题10－3，不过在解问题10－3之前为了方便说明，先来想想下面的问题10－4，就是加上硬币枚数与种类限制的『附加条件的分拆数』。」

※※问题10－4『附加条件的分拆数』

1元硬币、2元硬币、3元硬币各有1枚，请问3元的方法有几种。

「问题10－4并不难。将硬币限制为1、2、3元硬币3种，而且各只有1枚，要支付3元就只有『1元硬币与2元硬币』与『3元硬币』2种方法，这就是答案。」

※※解答10－4

两种方法。

「然后用问题10－4来说明生成函数，将使用各种硬币支付的金额如下列表。」

使用①所支付的金额，是0元或1元。

使用②所支付的金额，是0元或2元。

使用③所支付的金额，是0元或3元。

「在这里用下面的式子思考，使用形式上的变量x，将指数部分以『支付金额』表现，为了方便理解，把1写作x<0次方>。」

(x<0次方>＋x<1次方>)(x<0次方>＋x<平方>)(x<0次方>＋x<立方>)

「原来如此，很有趣。」米尔迦说。

「是啊。」我微笑回复。

「米尔迦学姐，『原来如此』是什么意思？学长，『是啊』又是什么意思呢？我完全不懂，哥哥姐姐要按照顺序说明啦～～」蒂蒂开始抱怨，她才说完，英英的钢琴就响起喜剧的配乐。

「继续下去吧。」米尔迦说。

「蒂蒂，刚才的式子要这样看……」我对她说。

(x<0次方>＋x<1次方>)(x<0次方>＋x<平方>)(x<0次方>＋x<立方>)

①的部分②的部分③的部分

「展开的话意义就很清楚了，这是将各硬币在各种支付状况中形变成指数，而且以各项表示所有支付的可能性。」

(x<0次方>＋x<1次方>)(x<0次方>＋x<平方>)(x<0次方>＋x<立方>)＝x<0＋0＋0次方>

＋x<0＋0＋3次方>

＋x<0＋2＋0次方>

＋x<0＋2＋3次方>

＋x<1＋0＋0次方>

＋x<1＋0＋3次方>

＋x<1＋1＋0次方>

＋x<1＋2＋3次方>

「譬如说，x<1＋2＋0次方>这项的指数1＋2＋0可以像下面这样解读。」

1→使用①支付的金额为1元

2→使用②支付的金额为2元

0→使用③支付的金额为0元

「……学长，请等一下，我还是不懂x<1＋2＋0次方>的意思，假如要①1枚、②1枚、③0枚的话，指数不要用1＋2＋0改用1＋1＋0不是比较好吗？」专注在式子上的蒂蒂用认真的表情发问。

「不是的，在这里不是『k元硬币的枚数』，而是要用『以k元硬币支付的金额』来想。」

「我的话会称为『k元硬币的贡献度』。」米尔迦提出建议。

「学长，我稍微懂了，的确展开式子后的x指数，就可以知道用①与②与③支付的所有可能性……呃，不过真不可思议，为什么一定要用(x<0次方>＋x<1次方>)(x<0次方>＋x<平方>)(x<0次方>＋x<立方>)这个式子呢？」

「这是因为(x<0次方>＋x<1次方>)(x<0次方>＋x<平方>)(x<0次方>＋x<立方>)『式子的展开方法』和『支付方法的所有可能性』刚好一致的关系，展开的时候会如下产生各项。」-

从x<0次方>＋x<1次方>选出一项-

从x<0次方>＋x<平方>选出一项-

从x<0次方>＋x<立方>选出一项，做出积

「这样做的话，就和下面的支付方法是一样的思考方式。」-

选出用①来支付的金额-

选出用②来支付的金额-

选出用③来支付的金额，做出和。

「啊，原来如此，我懂了。为了做出全部的组合，就利用式子展开的乘法分配吧……嘿～～」蒂蒂似乎能接受了。

我继续说明下去。

「展开的式子整理后会变成下面的算式，将同样有xk的项集中依照指数从小到大排列，也就是整合同类项。」

(x<0次方>＋x<1次方>)(x<0次方>＋x<平方>)(x<0次方>＋x<立方>)式子

＝x<0＋0＋0次方>＋x<0＋0＋3次方>＋x<0＋2＋0次方>＋x<0＋2＋3次方>展开

＋x<1＋0＋0次方>＋x<1＋0＋3次方>＋x<1＋1＋0次方>＋x<1＋2＋3次方>

＝x<0次方>＋x<立方>＋x<平方>＋x<5次方>＋x<1次方>＋x<4次方>＋x<立方>＋x<6次方>计算指数

＝x<0次方>＋x<1次方>＋x<平方>＋2x<立方>＋x<4次方>＋x<5次方>＋x<6次方>整合同类项，并按指数顺序排列

「蒂蒂，x<立方>的系数是2喔。你知道这代表什么意思吗？」

「嗯，系数是2的话……就是成为x<立方>的项有2个。实际上就是与……原来如此，我知道了，x<立方>的系数是2的意思，就是表示支付金额为3的时候有2种方法。」

「就是这样，将蒂蒂你现在说的再想一下。在我们面前的是使用形式变量x的乘幂和，然后x<n次方>的系数就是『支付金额为n的的方法数』。那『支付金额为n的的方法数』是什么呢？」

「『支付金额为n的的方法数』……啊，是分拆数！」

「是的，这个问题10－－4将硬币的枚数与种类加上限制，与村木老师的问题10－1和10－2出现的分拆数不同，不过却很相似，使用形式数x的乘幂和，其系数会变成『支付金额为n的的方法数』——这无疑是生成函数，也就是说，(x<0次方>＋x<1次方>)(x<0次方>＋x<平方>)(x<0次方>＋x<立方>)这个式子就是『加上限制的分拆数』的生成函数。」

※※问题10－4的『加上限制的分拆数』的生成函数

(x<0次方>＋x<1次方>)(x<0次方>＋x<平方>)(x<0次方>＋x<立方>)

「原来如此……说到生成函数，就会想到很复杂的无穷级数，不过也是有像(x<0次方>＋x<1次方>)(x<0次方>＋x<平方>)(x<0次方>＋x<立方>)一样，用小小的有限积做出的生成函数啊，迷你迷你生成函数……」蒂蒂做出了捏饭团的姿势。

「那么……」我继续说下去。

◎◎◎

那么，到这里为止是『有限制的分拆数』，现在开始要解除硬币数与种类的限制，不过讨论的方向仍然一样，然而已经不是像(x<0次方>＋x<1次方>)(x<0次方>＋x<平方>)(x<0次方>＋x<立方>)的『有限和的有限积』，而是像下面算式的『无限和的无限积』。

(x<0次方>＋x<1次方>＋x<平方>＋x<立方>＋……)①的贡献度

×(x<0次方>＋x<平方>＋x<4次方>＋x<6次方>＋……)②的贡献度

×(x<0次方>＋x<立方>＋x<6次方>＋x<9次方>＋……)③的贡献度

×(x<0次方>＋x<4次方>＋x<8次方>＋x<12次方>＋……)④的贡献度