第7章折积

使人感到完全没有错误的完美解法，

是怎么样才能想到的呢？

使人感到充分展现事实的完美实验，

又是如何被发现的呢？

到底要怎么做，我才能想到或发现那些东西呢？

——波利亚[1]

7．1图书室

7．1．1米尔迦

高中二年级的冬天。

「看过这个问题吗？」

在放学后的图书室里，我在惯用的座位上准备开始计算时，米尔迦跑了过来，她在我的面前放了一张纸，并用两手撑着桌子站着。

「这是什么？」我问。

「从村木老师那里拿来的问题。」她回答。

纸上这么写着。

※※问题7－1

0＋1＝（0＋1）

1的话1种(C<1>＝1)

0＋1＋2＝(0＋(1＋2))

＝((0＋1)＋2)

2的话2种(C<2>＝2)

0＋1＋2＋3＝(0＋(1＋(2＋3)))

＝(0＋((1＋2)＋3))

＝((0＋1)＋(2＋3))

＝((0＋(1＋2))＋3)

＝(((0＋1)＋2)＋3)

3的话5种(C<3>＝5)

0＋1＋2＋3＋……＋n＝？

n的话有几种(C<n>＝？)

「这题目好长，要是能再直接一点就好了。」我边将目光离开纸上边抱怨。

「喔……要直接一点？问题需要写出必要的重点以及维持适当的长度，还要形式化、定义用语、没有暧昧、威严中带有香气、能打动心灵……像这样吗？」

「就是这样。」我说。

「开玩笑就到此为止，我的递推公式就快完成了。」

「等一下，米尔迦，你是什么时候拿到这个的？」

「午休到教师办公室的时候，虽然有点偷跑。不过我已经确实交给你了，你从头开始吧，我到别的地方想，拜拜。」

米尔迦挥挥手，优雅地移动到窗边的座位，我的目光没有离开她。窗外是一棵棵已经落叶的梧桐树，更远的地方则是一片蓝天，天气虽然晴朗，却相当地寒冷。

我和米尔迦同样是高中二年级的学生，我们的数学老师村木老师有时候会出问题给我们，虽然老师有点奇怪，不过似乎满中意我们的。

米尔迦的数学很好，我虽然也不差，却赢不了她，每当我在图书室享受推演算式的乐趣时，她就会凑过来发表意见，并拿走我的自动铅笔擅自在我的笔记本上书写，然后开始演讲，不过这种时光也不会让人觉得不愉快……

我喜欢听米尔迦专心说话，也喜欢看她闭眼沉思，金属框的眼镜与她很相配，很搭配她脸庞清楚的线条……（无名之声：怎么不是喜欢她讲述的数学？）

不，比起这些，还是先回到问题上吧。她正在窗边思考答案，似乎是已经到达递推公式了，如果是她的话，或许很快就解决了。

将要解的问题整理一下吧。

0＋1，0＋1＋2，0＋1＋2＋3，……的式子，还有括号，因为有写着1的话1种，2的话2种，3的话5种，所以是要求括括号方法的总数，目标是求出0＋1＋2＋3＋……＋n这个式子括括号方法的总数。

n代表什么呢？算式0＋1＋2＋3＋……＋n从0开始表示共加了n＋1个数，n可以代表0＋1＋2＋3＋……＋n这个式子里『加号(＋)的个数』。

括括号的规则又是什么？在加号左右的式子称为项——两边各取一个数，也就是会像(0＋1)或(0＋(1＋2))这种2项的和(或是类似的组合)。但是不考虑(0＋1＋2)这种3项的和。

那按照理论，先从实例开始，题目写出了n＝1，2，3的状况，所以就先从n＝4开始，呃……出乎意料地多。

0＋1＋2＋3＋4＝(0＋(1＋(2＋(3＋4))))

＝(0＋(1＋((2＋3)＋4)))

＝(0＋((1＋2)＋(3＋4)))

＝(0＋((1＋(2＋3))＋4))

＝(0＋(((1＋2)＋3)＋4))

＝((0＋1)＋(2＋(3＋4)))

＝((0＋1)＋((2＋3)＋4))

＝((0＋(1＋2))＋(3＋4))

＝(((0＋1)＋2)＋(3＋4))

＝((0＋(1＋(2＋3)))＋4)

＝((0＋((1＋2)＋3))＋4)

＝(((0＋1)＋(2＋3))＋4)

＝(((0＋(1＋2))＋3)＋4)

＝((((0＋1)＋2)＋3)＋4)

竟然有14种，也就是4的话会有14种。

我在写的时候发现到规则，快找到有关「括括号方法的总数」的递推公式了。

举出实例后，接下来就是广义化，问题中当加号有n个时则将「括括号方法的总数」设为C<n>，刚才加号有4个，所以是C<4>＝14，到目前为止知道的有C<1>＝1，C<2>＝2，C<3>＝5，C<4>＝14，啊，也将C<0>＝1算进去，列出来就会出现下面的表。

n01234……

C<n>112514……

C<5>应该也会变得更大，那么，下一步就是「做出对C<n>的递推公式」了，做出来后，最后的目标就是「做出对于n，C<n>的闭公式」。

正当着手开始做出递推公式时，一位女孩从图书室的门口跑了过来。

是蒂蒂。

7．1．2蒂蒂

「啊～～学长。」蒂蒂跑到我的身旁，慌慌张张地开口：「已经开始用功了，我太慢了吗？」

蒂蒂是高中一年级的学生，总之就是我的学妹，她会像小松鼠或是小狗、小猫一样地黏着我，常常跑来问我一些数学的问题，不只是针对不懂的问题，也会提出根本上的疑问，虽然有点黏人，不过也不算是困扰。

「很急吗？」

「不、不会不会，没关系，只是有点事想问而已。」蒂蒂边向我摇手边后退三步。「打扰到你就不好了，所以等你要回去的时候再……今天也会待到关门吗？」

「是啊，我想应该会待到瑞谷管理员来宣布闭校为止，要一起回去吗？」

我偷偷地看向窗边，米尔迦面对桌子坐着，并将注意力集中在纸上，由于她背对着我，所以看不到她的表情，而她也没有任何动作。

「好的，请务必让我陪同，那我先告辞了。」

蒂蒂轻巧地踏稳脚步，在敬礼之后向右转，直接走出图书室，不过她在出去的那一瞬间偷偷瞄了米尔迦一眼。

7．1．3递推公式

那么，回到「括括号方法的总数」的递推公式。

从0到4有5个数，中间有4个加号。仔细想想，现在要求的是「括括号方法的总数」，所以那些数字本身并没有意义。也就是说：

((0＋1)＋(2＋(3＋4)))

可以用下列算式取代。

((A＋A)＋(A＋(A＋A)))

为了要做出递推公式，就必须看穿『括括号方法』背后的构造，然后找出规则性。由于这个式子有四个加号，所以先汇整成3个加号以下的状况，也就是说……

((A＋A)＋(A＋(A＋A)))——加号有四个

这种模式，也可以用这种情况来看。

((A＋A)＋(A＋(A＋A)))

1个加号2个加号

嗯，看出来了，最后的加号——也就是要注意最后才会加到的加号在哪里，以上式为例，从左边数来第二个是最后的加号，整个式子会根据最后的加号分成左右两个式子，将加号的位置从左边开始顺序移动的话，就能做出排他性质的类别，有4个加号的式子可以区分成以下4种，如果在最后的加号做上<>，会像下面一样。

((A)<+>(A＋A＋A＋A))

((A＋A)<+>(A＋A＋A))

((A＋A＋A)<+>(A＋A))

((A＋A＋A＋A)<+>(A))

在这个分类里，还是有像(A＋A＋A＋A)一样还没括完括号、依然是3项以上的和，不过加号的个数越变越少，所以可以带入之前的形式，嗯，这样似乎就能做出递推公式了。

有四个加号的形式，也就是说：

(A＋A＋A＋A＋A的形式)

有以下类别。

(A的形式)<分别对应于>(A＋A＋A＋A的形式)

(A＋A的形式)<分别对应于>(A＋A＋A的形式)

(A＋A＋A的形式)<分别对应于>(A＋A的形式)

(A＋A＋A＋A的形式)<分别对应于>(A的形式)

从这里开始发展成「类别的个数」。将「有n个加号的式子的括括号方法的总数」以C<n>表示的话，就能做出对C<n>的递推公式。

「分别对应于」的意思就是对应到「方法的总数」的积，在n＝4的状况，也就是以C1来表现式子时，C4会是下面4项的和。

C<0>×C<3>，C<1>×C<2>，C<2>×C<1>，C<3>×C<0>

也就是C<4>能写成下面式子。

C4＝C<0>C<3>＋C<1>C<2>＋C<2>C<1>＋C<3>C<0>

不错，这样就能广义化了。

C<n＋1>＝C<0>C<n－0>＋C<1>C<n－1>＋……＋C<k>C<n－k>＋……＋C<n－0>C<0>

出现了漂亮的式子了，在这里使用Σ让结构能更清楚呈现。

C<0>＝1

C<n＋1>＝Σ<k=0到n,C<k>C<n－k>>(n≥0)

很好，这样递推公式就完成了。

赶快来验算吧。

C<0>＝1

C<1>＝Σ<k=0到0,C<k>C<0－k>>＝C<0>C<0>＝1

C<2>＝Σ<k=0到1,C<k>C<1－k>>＝C<0>C<1>＋C<1>C<0>＝2

C<3>＝Σ<k=0到2,C<k>C<2－k>>＝C<0>C<2>＋C<1>C<1>＋C<2>C<0>＝5

C<4>＝Σ<k=0到3,C<k>C<3－k>>＝C<0>C<3>＋C<1>C<2>＋C<2>C<1>＋C<3>C<0>＝14

1，1，2，5，14，和一开始的实例吻合。

这样终于来到刚才米尔迦说的。递推公式就快完成了」的阶段，还真花了不少时间啊。

「现在是闭校时间。」

管理员瑞谷老师过来提醒大家。老师一向穿着紧身裙，戴着容易被误会成太阳眼镜的深色眼镜。平常会待在最里面的管理员室，时间到了就会无声无息地出现在图书室中央，提醒大家闭校时间到了。瑞谷管理员就像时钟一样。

喔，话说回来米尔迦呢？

转头看了一下，她已经不在了。

※※C<0>＝1

C<n＋1>＝C<k>C<n－k>(n≥0)

7．2于回家的路上将其广义化

「学长，『广义化』是什么呢？」蒂蒂用闪亮的双眼、开朗的声音向我发问。

我与蒂蒂并肩往车站走去，虽然在那之后有试着找过米尔迦，不过我到处都找不到她，而且连书包也消失，应该是回去了，真奇怪，就算已经解开了村木老师的问题，要回去也要先打声招呼吧。

天色虽然有点昏暗，不过路灯仍未亮起，我们走在住宅区间的复杂小路上。这是从学校到车站的最短距离，蒂蒂平常虽然都蹦蹦跳跳的，不过在回家的时候却会不可思议地慢慢走，我也只好配合着她的步调。

「要用一般的方法说明广义化并不容易，想想数学公式好了，想象有2或是3这种具体的数字构成的公式，将这样的公式变换成对任意整数n皆成立的代表性公式就称为『广义化』。」

「对任意整数n皆成立的公式……吗？」

「对，并不是对2或是3这种个别数字的公式，整数有无限个，并无法对2，3，4，……等等一一列举，应该说虽然可以列举，但是无法表现出全部，所以用含有变量n的方式替代，然后变量n可以代换任何整数皆成立。这就是『对任意整数皆成立的公式』。用『对所有整数皆成立』来表示也可以。」

「变数n……」

「在广义化的时候常常会出现新的变量，也可以说是『导入变量而形成的广义化』。」

蒂蒂突然打了一个大喷嚏。

「会冷吗？话说回来……你没围围巾啊。」

「是的，今天早上匆匆忙忙地从家里出来……」哈啾，她的鼻子又发出声响。

「这个借你，方便的话就用吧。」我把自己的围巾拿给她。

「谢、谢谢……哇，好温暖……不过这样就变成学长会冷了吧。」

「没关系没关系。」

「对不起，要是能『平分』围巾就好了。」

「……这就太大胆了……」

「咦？……唉呀！不是、不是啦，我不是那个意思……」她慌张赶摇手，而我只是嘻嘻笑着。「说、说到这里，刚才的『对任意整数皆成立的公式』，能再讲得更清楚一点吗？」蒂蒂赶紧将话题拉回来，她边挥着手边重新站好。

「好的好的，不过因为走路时没办法写算式，这样不好说明，假如你有时间的话，我们到『Beans』解释吧。」

「有时间，有时间。」蒂蒂突然加快脚步追过我，围着层层围巾的她看起来非常可爱。

「学长，快点～～」转头喊我的蒂蒂吐出白色的气息。

7．3于『Beans』演算二项式定理

在车站前的『Beans』里，我们一边喝着咖啡，一边展开算式。

例如这个公式。

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

「好的，呃……这是对于x和y的恒等式吧。」

嗯，这是将x＋y这个式子平方并展开后的样子表现出来，下个式子是三次式。

(x＋y)<立方>＝x<立方>＋3x<平方>y＋3xy<平方>＋y<立方>

到这里都没问题，接下来就试着将这个公式对指数广义化，也就是并非平方或三次方，而是『n次方的公式』，就是要求(x＋y)n的展开式的意思。

※※问题7－2

令n为1以上的整数，展开下面的式子。

(x＋y)<n次方>

首先在广义化之前，先将知道的具体知识整理一下，举出实例，然后观察它，这也是确认自己对问题是否已经理解了，『举例是理解的试金石』，将(x＋y)<n次方>以n＝1，2，3，4代入，就会像下面的式子。

(x＋y)<1次方>＝x＋y

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

(x＋y)<立方>＝x<立方>＋3x<平方>y＋3xy<平方>＋y<立方>

(x＋y)<4次方>＝x<4次方>＋4x<立方>y＋6x<平方>y<平方>＋4xy<立方>＋y<4次方>

然后进入广义化的过程，现在开始要求的就像下面这个式子。

(x＋y)<n次方>＝x<n次方>＋……＋y<n次方>

已经知道会出现x<n次方>项和y<n次方>项，之后只要把x<n次方>＋……＋y<n次方>的……部分填起来就好。

「……对不起，我记不住。」蒂蒂说。

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

再来思考下面这式子吧。

(x＋y)<1次方>＝(x＋y)

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

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

(x＋y)<4次方>＝(x＋y)(x＋y)(x＋y)(x＋y)

(x＋y)<n次方>＝(x＋y)(x＋y)(x＋y)……(x＋y)

n个

「这我就懂了，就是把(x＋y)乘n次。」

是啊，所以当n个(x＋y)互乘的时候，就是从每一个(x＋y)中选出x或是y来乘，譬如说三次方，就是从三个(x＋y)中各自选出1个x或y，思考全部的选择方式，将选择的部分以<>作记号。

(<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<立方>

这样就全部列出来了，然后将这些全部相加

xxx＋xxy＋xyx＋xyy＋yxx＋yxy＋yyx＋yyy＝x<立方>＋x<平方>y＋x<平方>y＋xy<平方>＋x<平方>y＋xy<平方>＋xy<平方>＋y<立方>

就变成

x<立方>＋3x<平方>y＋3xy<平方>＋y<立方>

这就是我们要求的式子，从(x＋y)(x＋y)(x＋y)展开的「和的积」，变成x<立方>＋3x<平方>y＋3xy<平方>＋y<立方>这种「积的和」；反过来说将「积的和」变成「和的积」就是因式分解。

「原来如此，我终于懂了……总觉得xxx，xxy，xyx，……，yyy这些的排列方式好像有规则性。」

嗯，很敏锐喔，蒂蒂。

「嘿嘿。」她害羞地伸了伸舌头。

那继续吧，要从(x＋y)中选出x或y其中之一，那么『全部选择x的选法』会有几个呢？

「嗯，一定要选x的话……就只有1个。」

没错，那么『x有n－1个，y有1个的选法』呢？

「嗯，最右边选y，其它选x，右边数来第二个选y……这样的话会有n个。」

答对了，正确答案，那接下来是广义化啰，『x有n－k个，y有k个的选法』有几个？

「呃，嗯，n是(x＋y)的个数的话，那k是什么？」

这是很好的问题，k是为了要广义化而导入的变量，表示选择y的个数，k为整数，并满足0≤k≤n的条件，刚才我们讨论的是k＝0(全部选择x的选法)和k＝1(y有1个的选法)的情形。

「所以这就是从n个里面选出k个的情形，因为选择的顺序已经决定好了，所以是组合……吧。」

对，组合，用y选择k个，x选择n－k个的情形来作组合的话，就会如下式。

()<n,k>＝((n－0)(n－1)…(n－(k－1)))/((k－0)(k－1)…(k－(k－1)))

这就是x<n－k次方>y<k次方>的系数。

「学长，我有问题。」蒂蒂举起右手，「『()<n,k>』是什么呢？组合的话是<组合,n,k>吧，假如是这个的话我还懂……」

「是的，()<n,k>和nCk完全一样，在数学的书里，组合很常写成()<n,k>。另外，矩阵和向量的写法也很类似()<n,k>，不过和组合没有关系。」

「好，我知道了，还有一个问题，组合我记得是……

<组合,n,k>＝n!/(k!(n－k)!)

这和学长的式子不太一样。」

不，假如将(n－k)!的部分约分之后就会发现其实是一样的、譬如说，从5个里面选出3个……

<组合,5,3>＝5!/(3!(5－3)!)

＝5!/(3!2!)

＝(5×4×3×2×1)/(3×2×1×2×1)

＝(5×4×3)/(1×2×1)

＝()<5,3>

看，是一样的。

组合若是用递降阶乘表现会更清楚。所谓的递降阶乘写作x<n次递降阶乘>，是从第n阶的阶梯不断下降的积喔，也就是说像这样。

<n次递降阶乘>＝(x－0)(x－1)(x－2)……(x－(n－1))——共n个因式

普通阶乘n！的递降阶乘写成……

n!＝n<n次递降阶乘>

使用递降阶乘，就可以将()<n,k>表现得更漂亮。

()<n,k>＝n<k次递降阶乘>/k<k次递降阶乘>

※※从n个中选k个出来组合的个数

<组合,n,k>＝()<n,k>

＝n!/(k!(n－k)!)

＝((n－0)(n－1)…(n－(k－1)))/((k－0)(k－1)…(k－(k－1)))

＝n<k次递降阶乘>/k<k次递降阶乘>

「呃、这个……」

抱歉，稍微离题了，回到主题吧，已经得到(x＋y)n的展开式了，为了将规则性表现出来会写得稍微冗长一点。

(x＋y)n＝(选0个y)

＋(选1个y)

＋……

＋(选k个y)

＋……

＋(选n个y)

＝()<n,0>x<n－0次方>y<0次方>

＋()<n,1>x<n－1次方>y<1次方>

＋……

＋()<n,k>x<n－k次方>y<k次方>

＋……

＋()<n,n>x<n－n次方>y<n次方>

注意每一项变化的部分，用Σ来表现就会得到下列的式子，这是二项式定理。

※※解答7－2

(x＋y)<n次方>的展开(二项式定理)

(x＋y)<n次方>＝Σ<k=0到n,()<n,k>x<n－k次方>y<k次方>>

一开始就算知道这个展开还是不容易记忆，不过有自己动手导出公式的经验就不会太难记了，不断练习让自己导出公式的话，就会在不知不觉中记住，之后就不需要再慢慢导了……虽然这是反过来的说法，不过也颇有趣的。

「学长……出现了Σ，似乎突然变得很难了……」

假如不安的话，也可以将Σ表示的项具体地写出来，k＝0的时候、k＝1的时候、k＝2的时候，在习惯之前这很重要。

「啊……不过没想到会在这里用到组合，读机率的时候，练习选红球和白球的问题时，计算中有一堆乘法让我印象深刻，演算变得像在练习约分一样，不过没想到在算式展开当中会以这种方式用到组合。」

接下来就是验算了，思考具体的例子，广义化后，在完成前一定要验算，在这里不能偷懒，用n＝1，2，3，4确认。

(x＋y)<1次方>＝Σ<k=0到1,()<1,k>x<n－k次方>y<k次方>>

＝()<1,0>x<1次方>y<0次方>＋()<1,1>x<0次方>y<1次方>

＝x＋y

(x＋y)<平方>＝Σ<k=0到2,()<2,k>x<n－k次方>y<k次方>>

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

＝x<平方>＋2xy＋y<平方>

(x＋y)<立方>＝Σ<k=0到3,()<3,k>x<n－k次方>y<k次方>>

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

＝x<立方>＋3x<平方>y＋3xy<平方>＋y<立方>

(x＋y)<4次方>＝Σ<k=0到4,()<4,k>x<n－k次方>y<k次方>>

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

＝x<4次方>＋4x<立方>y＋6x<平方>y<平方>＋4xy<立方>＋y<4次方>

蒂蒂将式子一个个确认之后点点头说：「虽然公式里出现一堆文字会让人觉得『啊，好烦』，不过一想到这是广义化的结果，就觉得可以接受，会有一堆文字也是没办法的事。」

嗯，为了取代无限个具体的公式，而用了n这个变量替代，这就是广义化的公式。在各项的部分也用了k这个变数来广义化。

「是的，不过……n－k和k交错在一起，要分辨也很麻烦。」

不要将n－k和k分开思考，而是要想『和就是n』，然后在这个和中从0到n间取平衡，一开始x的指数是n最大，这时y的指数是0最小，然后x的指数每减1，y的指数就加1，最后x的指数变成最小的0，y的指数是最大的n，要像这样思考，而k就是中间平衡的位置。

k＝0xxxxxx｜

k＝1xxxxx｜y

k＝2xxxx｜yy

k＝3xxx｜yyy

k＝4xx｜yyyy

k＝5x｜yyyyy

k＝6｜yyyyyy

「啊……从x到y慢慢地移动。」

没错，将全部n次方分配到x与y上，就像『平分』围巾一样。

「学、学长！你还记得这个话题啊……」

7．4于自家中解生成函数的积

夜深了，家人也都睡了，我独自在房间静下来思考。C<n>的递推公式已经完成了。

C<0>＝1

C<n＋1>＝C<k>C<n－k>(n≥0)

而我接下来想尝试一样东西，那就是生成函数的解法。

米尔迦和我曾寻找过斐波那契数列的一般项，那时候她将数列与生成函数做了对应，我们在两个国度——『数列之国』与『生成函数之国』中环绕。

我打开笔记本，一边搜寻记忆一边开始写下。

当得到数列a<0>，a<1>，a<2>，……，a<n>……之后，就将数列各项的系数以a<0>＋a<1>x＋a<2>x<平方>＋……＋a<n>x<n次方>＋……形式的幂级数来表现，这就是生成函数，然后以下面的对应关系，将数列与生成函数视为一样的东西……

数列←→生成函数

a<0>，a<1>，a<2>，……，a<n>……←→a<0>＋a<1>x＋a<2>x<平方>＋……＋a<n>x<n次方>＋……

如此对应的话，就可以将无穷的数列以一个生成函数呈现，而且若是将生成函数以闭公式表现，就会得到数列一般项的闭公式这个令人赞叹的结果。

我和米尔迦使用生成函数求得斐波那契数列的一般项，就像原本捧在手上快要散落的数列，被名为生成函数的一条线串了起来，那真是一次难以言喻的经验。

我想用这种解法来解开这次的问题。

※※(求Cn闭公式的旅行地图)

数列C<n>→生成函数C(x)

↓

数列C<n>的闭公式←生成函数C(x)的闭公式

由n个加号构成的式子设成C<n>，则得数列C<0>，C<1>，C<2>，……，C<n>……。

再将此数列之生成函数设为C(x)，x是为了不让数列混乱的形式上变数，x<n次方>的指数n会与C<n>的n对应，则C(x)会如下所示。

C(x)＝C<0>＋C<1>x＋C<2>x<平方>＋……＋C<n>x<n次方>＋……

以上是生成函数的定义，到这里为止还不需要动脑筋，没错，要到生成函数的国度是很简单的。

要动脑的部分从现在才开始。

现在我手上拥有的武器只有C<n>的递推公式而已，下一步是要用递推公式求C(x)的闭公式，我想求出C(x)的『对x的闭公式』，而这个式子应该不会出现n。

不过，这次的递推公式不像斐波那契数列那时候一样单纯，那时候确实是在生成函数中乘上x，然后不断地『移动』系数，最后相加相减才将n消掉。

但是这次的递推公式C<n＋1>＝Σ<k=0到n,C<k>C<n－k>>相当麻烦，是在C<k>C<n－k>这个积上再加入了Σ，形成繁琐的『积的和』形式。

嗯？

「积的和」……吗？

而且是C<k>和C<n－k>这种「标记之和为n」的形式……吗？

原来如此。

我想起自己对蒂蒂说过的话了。

……不要将n－k和k分开思考，而是要想『和就是n』，然后在这个和中从0到n间取平衡……

这次的递推公式也很类似，C<k>和C<n－k>的标记之和为n，然后为了和的平衡，k会在0与n之间变动。

现在知道的递推公式C<n＋1>＝Σ<k=0到n,C<k>C<n－k>>是这样表现的，假如能好好运用Σ<k=0到n,C<k>C<n－k>>作成「积的和」的形式，就可以用这样比较单纯的项置换。

仔细想想，有哪些场合会出现「积的和」。

……将(x＋y)(x＋y)(x＋y)这种「和的积」变成x<立方>＋3x<平方>y＋3xy<平方>＋y<立方>这种「积的和」，这就是展开……

将「和的积」展开，就会变成「积的和」吗？

好。

关键似乎就是积了，试试看生成函数的积吧，动手算或许就能发现什么。

由于只有生成函数C(x)，所以先试试看平方会出现什么呢？生成函数如下。

C(x)＝C<0>＋C<1>x＋C<2>x<平方>＋……＋C<n>x<n次方>＋……

所以平方的话……会变成这样。

C(x)<平方>＝(C<0>C<0>)＋(C<0>C<1>＋C<1>C<0>)x＋(C<0>C<2>＋C<1>C<1>＋C<2>C<0>)x<平方>＋……

常数项是C<0>C<0>，x项系数是C<0>C<1>＋C<1>C<0>，x<平方>项系数是C<0>C<2>＋C<1>C<1>＋C<2>C<0>啊。

接着用广义化——我想起了蒂蒂那双大眼睛——表现C(x)<平方>的x<n次方>系数

宁静的空间中只剩下写字的沙沙声。

……完成了，这就是x<n次方>的系数。

C<0>C<n>＋C<1>C<n－1>＋……＋C<k>C<n－k>＋……＋C<n－1>C<1>＋C<n>C<0>

要注意标记的部分，而在C<k>C<n－k>中，左边的k渐渐变大，右边的n－k渐渐变小，k在0到n的范围内移动。

到这里为止写得相当冗长不容易懂，所以使用Σ，广义来说，x的系数就是

Σ<k=0到n,C<k>C<n－k>>

由于这是C(x)<平方>这个式子的「x<n次方>的系数」，所以C(x)<平方>这个式子就会变成二重和的形式……写成……

C(x)<平方>＝Σ<n=0到∞,Σ<k=0到n,C<k>C<n－k>>x<n次方>>