第7章折积.2

出来了。

求出来了！

求出漂亮的「积的和」Σ<k=0到n,C<k>C<n－k>>了，所以之后这个部分应该可以用递推公式简化，由递推公式得……

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

可以置换成以下这个单纯的项。

C<n＋1>

也就是说……

可以将生成函数C(x)的平方大幅简化了，将C<k>C<n－k>用C<n＋1>替换吧。

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

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

喔～～二重和变成一般的和了。

不过等一下，C<n＋1>的标记和x<n次方>的指数差了1。

嗯～～啊，对了，消除差距的状况在斐波那契数列的时候也有过，只要将差距的部分乘上x就好，将两边乘x……

x×C(x)<平方>＝x×Σ<n=0到∞,C<n＋1>x<n次方>>

将右边的x加入∑中。

x×C(x)<平方>＝Σ<n=0到∞,C<n＋1>x<n＋1次方>>

将n＝0的部分视为n＋1＝1，这是为了配合标记与指数。

x×C(x)<平方>＝Σ<n＋1＝1到∞,C<n＋1>x<n＋1次方>>

然后将n＋1全部置换成n。

x×C(x)<平方>＝Σ<n＝1到∞,C<n>x<n次方>>

很好，这样右边的就几乎等于生成函数C(x)了，只需要将C<n>的部分减掉。

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

这样就把n消掉了！

x×C(x)<平方>＝C(x)－C<0>

用C<0>＝1代入，将式子作整理。

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

得出了C(x)的二次方程式，令x≠0然后求解舍得到下式。

C(x)＝(1±<根号1－4x>)/2x

嗯。

很顺利。

从生成函数的积做出漂亮的「积的和」，然后导出闭公式，没想到生成函数的积会这么有用。

不过我还不晓得为什么会有两个一正一负生成函数，而且<根号1－4x>的部分又是怎么回事？似乎还有很深的谜。

不过不管怎么说，n都已经消掉了。

我导出了生成函数C(x)的闭公式。

之后就是将这个闭公式以幂级数展开就好。

7．5图书室

7．5．1米尔迦的解

隔天放学后的图书室里，米尔迦坐在我的身旁。

「原本想用递推公式的……」米尔迦先开口：「……不过中途改变方针了。」

「咦？不用递推公式解吗？」

「我没有用递推公式来解，因为我找到了更好的对应。」

(更好的对应？)

我打开笔记本，米尔迦迅速地在上面写。

「以n＝4来举例。

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

仔细观察的话，即使『括号的后半』消掉了也可以复原。

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

能让括号可以复原的，就是『加号连结两个项』的限制。」

「原来如此，只要在即将出现的两个项时插入括号的后半就可以了。」我了一下回答她想，我虽然放弃了，但是没想到((A＋A)＋(A＋(A＋A)))可以更简化。

米尔迦的嘴唇微微上扬露出微笑。

「说得更明白一点，数字根本就不必要，可以直接变成……

（（＋＋（＋（＋

这是可以复原的，只要在加号的左侧填入数字，不过最后的4要写在右侧。」

「原来如此。」我说。

「简单来说括括号方法的总数就是『括号前半』与『加号』的排列组合，以n＝4来说，就是4个括号前半与4个加号的排列，假设以8个＊并排。

＊＊＊＊＊＊＊＊

然设将其中4个变成括号前半。

（（＊＊（＊（＊

然后再将剩下来的*自动变成加号。

（（＋＋（＋（＋

从8个符号里（括号与加号各4个），选出变为括号前半的4个演算组合就是()<8,4>，这是n＝4的情况，广义化则是从2n个文字中（括号与加号各n个)，选出变为括号前半的n个作组合，也就是()<2n,n>……像这样组合的话，也等同于下图中方格路径的最短路线，从左下的S开始，到右上的G，箭头指的道路对应（（＋＋（＋（＋的文字列。」

[插图：画一个4格×4格的表格，每格均为正方形。左下角一点为S，右上角一点为G。在最左一列的每格左侧写一个（，在最上一列的每格上方写一个＋。之后从左下角沿表格线描箭头：上上右右上右上右，从S点一直描到G点]

「那么，接下来……」

「等一下」……我打断了滔滔不绝的米尔迦。

「米尔迦，这里有点奇怪。因为这并不是在8个之中任意取4个，譬如说，就算将括号与加号各取4个也不能排成这样啊。

（（＋＋＋＋（（

将这个对应在你画的图上就知道了，这个图表不能经过有◎的地方再到达终点。」

[插图：画一个4格×4格的表格，每格均为正方形。左下角一点为S，右上角一点为G。在最左一列的每格左侧写一个（，在最上一列的每格上方写一个＋。之后从左下角沿表格线描箭头：上上右右上右上右，从S点一直描到G点。之后在S点右边一个格的交叉点处画◎，并在其右上方45度角的所有交叉点上画◎]

被打断话的米尔迦嘟起嘴抱怨：「我还没说完啊。」

◎◎◎

「我还没说完啊。在排列括号与加号时，有着加号数量不能超过括号数量的限制。

当加号数量超过括号数量的时候，就会像你说的一样，也就是上图中通过◎的状况，不通过◎而从S到G的方法数才会等于C<n>。

不考虑限制的话，从S到G的方法有()<2n,n>。」

那么，从S到G之间曾经通过◎一次以上的方法数又有多少呢？

将第一次碰到◎的地方设为P，在通过P之后将前进的方向政变，把斜虚线当成镜子，从P→G之间原本是→的话就改成↑，原本是↑的话，就改成→，也就是说终点不是G而是G’。

G’是G镜中的投影点，简单来说，就是将（（＋＋＋＋（（变成（（＋＋＋（＋＋。

这样思考的话，通过◎的方法数就会和从S到G’的方法数一对一对对应，从纵向横向都是2n的道路，变成横向n＋1的道路来算组合，也就是变成()<2n,n＋1>。

[插图：画一个4格×4格的表格，每格均为正方形。左下角一点为S，右上角一点为G。在最左一列的每格左侧写一个（，在最上一列的每格上方写一个＋。之后在S点右边一个格的交叉点处画◎，并向其右上方45度角引斜线，在斜线经过的的所有交叉点上画◎。之后，在表格右侧补一列格子，擦去最上面的一个，新补的格子中右上角的点为G’点。之后从左下角沿表格线描箭头：上上右右右上上右，从S点一直描到G’点。]

换句话说，下式会成立。

C<n>＝(从S到G的方法数)－(从S到G’的方法数)

接下来就是计算了，快点快点，彻底使用递降阶乘吧。

C<n>＝()<2n,n>－()<2n,n＋1>

＝2n<n次递降阶乘>/n<n次递降阶乘>－2n<n＋1次递降阶乘>/n＋1<n＋1次递降阶乘>使用()<n,k>=n<k次递降阶乘>/k<k次递降阶乘>

＝((n＋1)×2n<n次递降阶乘>)/((n＋1)×n<n次递降阶乘>)－(2n<n＋1次递降阶乘>×n)/(n＋1)n<n次递降阶乘>通分

这边的通分，尤其是第二项会有点难懂，虽然只要明白递降阶乘的含义就会很清楚。不过还是补充一下。

分子是这样变形的，是将(n)这个『尾巴』提出来。

(2n)<n＋1次递降阶乘>＝(2n)×(2n－1)(2n－2)……(n＋1)×(n)

＝(2n)<n次递降阶乘>×(n)

然后分母是这样变形的，这次是将(n＋1)这个『头』提出来。

(n＋1)<n＋1次递降阶乘>＝(n＋1)×(n)×(n－1)……2×1

＝(n＋1)×(n)<n次递降阶乘>

就是这样，继续计算C<n>吧，通分后……

C<n>＝(((n＋1)×2n<n次递降阶乘>)－(2n<n＋1次递降阶乘>×n))/((n＋1)×n<n次递降阶乘>)

＝(((n＋1)－n)×(2n)<n次递降阶乘>)/((n＋1)×n<n次递降阶乘>)分子用(2n)<n次递降阶乘>

＝(1/(n＋1))×(2n<n次递降阶乘>)/n<n次递降阶乘>)整理

＝(1/(n＋1))×()<2n,n>代入n<k次递降阶乘>/k<k次递降阶乘>＝()<n,k>

得到有n个加号的式子的括括号方式的总数如下。

C<n>＝(1/(n＋1))×()<2n,n>

好，这样就告一个段落了，来验算看看吧。」

◎◎◎

我一边为米尔迦的简单解法感到震惊，一边计算。

C<1>＝(1/(1＋1))×()<2,1>＝(1/2)×(2/1)＝1

C<2>＝(1/(2＋1))×()<4,2>＝(1/3)×((4×3)/(2×1))＝2

C<3>＝(1/(3＋1))×()<6,3>＝(1/4)×((6×5×4)/(3×2×1))＝5

C<4>＝(1/(4＋1))×()<8,4>＝(1/5)×((8×7×6×5)/(4×3×2×1))＝14

「好厉害……确实是1，2，5，14！」

米尔迦听到了我的话后露出微笑。

※※解答7－1

C<n>＝(1/(n＋1))×()<2n,n>

「那这次换你了。」

7．5．2面对生成函数

虽然是被米尔迦硬塞的作业，不过她优雅的解法还是很让我震惊，即使想以生成函数解答，可是我只做出繁琐的闭公式，也还没找到正确答案，我是不是挑战超过我能力的问题呢？我昨晚完成生成函数的积的感动已经烟消云散了。

有点不甘心。

米尔迦摆出有点困扰的表情催促我：「没关系，你就说说看吧，做出递推公式，然后呢？」

我说出了想尝试生成函数的解法，从做出生成函数的积，到「漂亮的积的和」，再到二次方程式，最后到达了生成函数的闭公式，虽然抵达生成函数的国度，却回不了数列的国度。

非常地不甘心。；

「是什么样的式子？」米尔迦问。

我没有说话。

「嗯？是什么式子？」她看着我的脸。

没办法的我只好在笔记本上写下式子。

C(x)＝(1±<根号1－4x>)/2x

「嗯，有两个难题，±的部分与<根号1－4x>的部分。」

「我也知道，就是卡在这里啊。」

米尔迦不理会我烦躁的语气继续说下去。

「先从±的部分思考看看。」

米尔迦看了一下算式之后闭上眼睛，似乎感觉到什么而将脸朝向上方，她将右手食指向上指，然后转圈，画着零、画着零，画出了无穷大，然后睁开眼睛。

「回到定义吧，生成函数C(x)是这个式子吧。」

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

「也就是说，当x＝0的时候，含有x的项会全部消失，变成C(0)＝0，此时再回到你发现的闭公式吧。」

C(x)＝(1±<根号1－4x>)/2x

「这里的C(0)会怎么样呢？」

「不行，因为0是除数。所以C(0)会变成无限大。」我回答，我已经冷静下来了，因为对米尔迦生气又能怎么样？闹脾气又能怎么样？

「不，不对。」米尔迦缓缓地摇头，「虽然有一边是无限大，但另一边是不固定的。C(x)的±里，正的设为C<＋>(x)，负的设为C<－>(x)……

C<＋>(x)＝(1＋<根号1－4x>)/2x

C<－>(x)＝(1－<根号1－4x>)/2x

……就会变成这样，为了不让零变成除数，就将分母移过去。」

2x×C<＋>(x)＝1＋<根号1－4x>

2x×C<－>(x)＝1－<根号1－4x>

「当x＝0的时候左边都会是0，而1＋<根号1－4x>会变成2，1－<根号1－4x>才会是0，所以这是怎么回事呢？」

「至少可以知道C<＋>(x)是不合的……」

「大概吧，虽然没有深入去学生成函数，没办法清楚地说明，至少没有必要再去管C<＋>(x)了，发现式子只要将注意集中在C<－>(x)就好，接下来你认为呢？」

「就是处理<根号1－4x>吧。」我说。

对着心情已经回复的我，米尔迦微微一笑。

※※生成函数C(x)的闭公式

C(x)＝(1－<根号1－4x>)/2x

7．5．3围巾

这时候我注意到蒂蒂站在图书室的入口，她正看着坐在一起的我和米尔迦，两手拿着纸袋摆在身体前方，她是从什么时候开始以这样姿势站着的呢？

我轻轻地向蒂蒂招招手，她和平常不同，不是蹦蹦跳跳地而是慢慢地走向这里，脸上还露出认真的神情。

「……学长，昨天真是谢谢你了。」

蒂蒂以平静的语调说着并敬了个礼，然后将纸袋交给我，里面有好的围巾。

「啊，嗯，不客气，没感冒吧。」

「嗯，没事，因为学长借了我围巾，又和我一起喝了热饮。」

蒂蒂边说边将视线转向米尔迦，我也跟着看过去，米尔迦拿着自动铅笔的手停了下来，抬起头的她往纸袋瞥了一眼后看向蒂蒂，两个女孩无言地对望。

没有任何人说话。

经过四秒。

蒂蒂「呼」地吐了一口气后重新面向我。

「今天就告辞了，之后也请继续教我数学。」蒂蒂行个礼，缓缓走出图书室，在入口的时候她又回过头，再次行礼。

这时的米尔迦已经重新面对纸张，准备继续计算。

「有想到什么吗？」我问，当然是关于的事。

米尔迦没有抬头，她一边写着式子一边回答。

「信。」

「咦？」

「……里面有信。」米尔迦仍旧没有停止计算。

我看了看袋子并伸手进去找，在围巾下似乎有什么东西，拿出来看才发现是张相当秀气的米白色卡片，为什么米尔迦会注意到有卡片呢？

上面有着蒂蒂留下的简短讯息。

谢谢你温暖的围巾。蒂德菈

P.S.要再约我去『Beans』喔！

7．5．4最后的关卡

我们回到问题上。

求出的生成函数C(x)的闭公式如下所示。

※※生成函数C(x)的闭公式

C(x)＝(1－<根号1－4x>)/2x

按下来的问题就是要怎么处理<根号1－4x>了。

「似乎找不到下一步要怎么做了，米尔迦，得到了C(x)的闭公式之后……我们求斐波那契一般项那时候是怎么做的？」

「C(x)的闭公式能做的只有找到x<n次方>的系数，简单地说，就是展开幂级数。」米尔迦如此回答。

「<根号1－4x>还真麻烦啊，话说回来要怎么处理<根号1－4x>呢？」我抱怨着。

「也只能展开幂级数了，假设将系数的数列设做K<n>，就可以像这样展开。」米尔迦写出式子。

＝K<0>＋K<1>x＋K<2>x<立方>＋……＋K<n>x<n次方>＋……

＝Σ<k=0到∞,K<k>x<k次方>>

「然后生成函数C(x)是这个式子。

C(x)＝(1－<根号1－4x>)/2x

所以将分母移项，变成下面的式子。

2x×C(x)＝1－<根号1－4x>

在这里置入C(x)＝Σ<k=0到∞,C<k>x<k次方>>及<根号1－4x>＝Σ<k=0到∞,K<k>x<k次方>>，就会变成……

2x×Σ<k=0到∞,C<k>x<k次方>>＝1－Σ<k=0到∞,K<k>x<k次方>>

将左边2x移到里面，右边的k＝0移项到外面。

Σ<k=0到∞,2C<k>x<k＋1次方>>＝1－K<0>－Σ<k=0到∞,K<k>x<k次方>>

将左边调整成从k＝1开始。

Σ<k=1到∞,2C<k－1>x<k次方>>＝1－K<0>－Σ<k=0到∞,K<k>x<k次方>>

将∑往左边集中。

Σ<k=1到∞,2C<k－1>x<k次方>>＋Σ<k=0到∞,K<k>x<k次方>>＝1－K<0>

这样就整理好∑了，由于是无穷级数，所以要改变和的顺序必须清楚说明条件，不过现在为了先找到式子就先省略。

Σ<k=1到∞,(2C<k－1>＋K<k>)x<k次方>>＝1－K<0>

由于上式是对x的恒等式，所以将两边的系数比较之后，就可以得到Kn与Cn的关系式。

0＝1－K<0>比较x<0次方>的系数

2C<0>＋K<1>＝0比较x<1次方>的系数

2C<1>＋K<2>＝0比较x2的系数

2C<n>＋K<n＋1>＝0比较xn的系数

将其整理之后得到

K<0>＝1

C<n>＝-K<n＋1>/2(n≥0)

也就是K<n>的话也会自动得到C<n>，而最后的关卡则是<根号1－4x>的展开了。

7．5．5陷落

米尔迦似乎等不及地说出：

「那么就来攻陷最后的关卡吧，现在令K(x)＝<根号1－4x>，然后目标是求……

K(x)＝Σ<k=0到∞,K<k>x<k次方>>

的(K<0>，K<1>，……，K<n>……)，从哪里开始好呢？」

「从最容易的地方开始吧。」我说。

「喔，那你知道要怎么做吗？」

「试试看x＝0吧。」我马上回答：「这样的话，Σ<k=0到∞,K<k>x<k次方>>除了常数项以外都会消掉，也就是会变成这样。」

K(0)＝K<0>

「没错，然后呢？」米尔迦问。

「是问x要怎么设吗？」我反问。

「不是，是要你赶快用解析函数的基本技术。」米尔迦有点不悦地回答。

「什么？」

「微分。把K(x)用x微分的话，数列就会变换，常数项会变成K1。

K(x)＝K0＋K1x<1次方>＋K2x2＋K3x3＋……＋Knxn＋……

↓↓ ↓ ↓

K’(x)＝1K<1>＋2K<2>x<1次方>＋3K<3>x<平方>＋……＋nK<n>x<n－1次方>＋……

所以……

K’(0)＝1K<1>

知道为什么要明白写出1了吧？因为微分会让指数下降，这是为了区别它的规律，到这里就轻松了，将K’(x)再微分会得到下列式子。

K’’(x)＝2×1K<2>＋3×2K<3>x<1次方>＋……＋n×(n－1)K<n>x<n－2次方>＋……

所以当x＝0时，会出现下面的式子。

K’’(0)＝2×1K<2>

之后就不断地重复，将K(x)微分n次以K<(n),>(x)表示的话，

K<(n),>(x)＝n(n－1)(n－2)……2×1K<n>＋(n＋1)n(n－1)(n－2)……真是麻烦……

因为太长了，就用递降阶乘书写。

K<(n),>(x)＝n<n次递降阶乘>K<n>

＋(n＋1)<n次递降阶乘>K<n>＋1x<1次方>

＋……

＋(n＋k)<n次递降阶乘>K<n＋k>x<k次方>

＋……

所以令x＝0会变成这个算式。

K<(n),>(0)＝n<n次递降阶乘>K<n>

也就是用K<(n),>(0)可以表示K<n>，简单地说就是泰勒展开式。

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

到这里告一段落。」

米尔迦喘了一口气。

「嗯，不过到这里就无法继续下去了，已经没路了。」我说。

「为什么这说呢？现在已经用幂级数捉住K(x)了，接下来就用普通的函数型式捕捉吧。」

「捕捉？」

「使用解析函数的基本技术，还是微分。」

说完话的米尔迦对我眨眨眼，这或许是她第一次有那纯真的表现。

「回想K(x)的定义……

K(x)＝<根号1－4x>

……也就是说，由于平方根是1/2次方，所以……

K(x)＝(1－4x)<1/2次方>

一边注意规律，一边反复地微分。

K(x)＝(1－4x)<1/2次方>

K’(x)＝2×(1－4x)<-1/2次方>

K’’(x)＝－2×2×(1－4x)<-3/2次方>

K’’’(x)＝－2×4×3×(1－4x)<-5/2次方>

K’’’’(x)＝－2×6×5×4×(1－4x)<-7/2次方>

K<(n),>(x)＝－2×(2n－2)<n－1次递降阶乘>×(1－4x)<-(2n－1)/2次方>

K<(n＋1),>(x)＝－2×(2n)<n次递降阶乘>×(1－4x)<-(2n＋1)/2次方>

将x＝0代入就形成最后的式子。

K<(n＋1),>(0)＝－2×(2n)<n次递降阶乘>

再把刚才用幂级数求得的式子，就是你说没办法继续下去的那个式子拿出来，用n＋1思考。

K<n＋1>＝K<(n＋1),>(0)/(n＋1)<n＋1次递降阶乘>

从这两个式子，可以得到下面的算式。

K<n＋1>＝(－2×(2n)<n次递降阶乘>)/(n＋1)<n＋1次递降阶乘>

这样就得到K<n＋1>了，完全不是死路，你还记得K<n>和C<n>的关系吗？

Cn＝-K<n＋1>/2

之后就是用手计算了。

Cn＝-K<n＋1>/2

＝(2n)<n次递降阶乘>/(n＋1)<n＋1次递降阶乘>

分母可以从(n＋1)<n＋1次递降阶乘>＝(n＋1)×n×(n－1)……1＝(n＋1)×n<n次递降阶乘>这样变形。

＝(2n)<n次递降阶乘>/(n＋1)<n＋1次递降阶乘>

＝(1/(n＋1))×((2n)<n次递降阶乘>/(n)<n次递降阶乘>)

＝(1/(n＋1))×()<2n,n>

就得到了C<n>。

C<n>＝(1/(n＋1))×()<2n,n>

好，这样就告一段落了，得到的是相同的式子，也就是从生成函数的国度回来了。」

米尔迦演算到这里，露出笑容对我说：

「欢迎回来。」（无名之声：接着是想问先吃饭？先洗澡？还是说……）

7．5．6半径为零的圆

「我回来了……应该要说谢谢才对。」我说。

「相当有趣，这是趟快乐的旅行。」她竖起食指。

我看着米尔迦，她这个人真是……虽然有点粗鲁却很善良，总是冷静地表现热情，我果然对米尔迦……

米尔迦稍微眯起眼睛并站起身。

「为了纪念……跳只舞吧。」

我也站了起来。

(什么意思？)

米尔迦率直地向我伸出左手，我伸出的右手像小鸟般轻轻地停在米尔迦纯白的指间。

(好温暖)

我们牵着手往书架前的空地移动。

米尔迦以画图的方式从我的周围慢慢地走过。

一步。

再一步。

混杂着轻快的脚步。

米尔迦像是跳舞般地走着。

放学后的图书室除了我们没有其它人。

只听得见她轻微的脚步声。

「米尔迦总是与我保持在相同距离的地方，就像是在圆周上，这单位圆吧？」

我到底在说什么啊。

米尔迦「嗯」了一声停下脚步，「我们两人的手长度加起来是1的话才算是单位圆。」她缓缓回答，然后闭上眼睛。

……就算无法在她的『最近距离』，也希望至少能在她的『最近间隔』……

我想起了曾经想过的事情。

米尔迦张开眼。

「即使半径是零……」话说到一半，米尔迦就用力地将我拉向她。

「即使半径是零……还是会分开吗？」

如此说着的米尔迦将她的脸渐渐靠近，直到与我的眼镜相碰的距雕。

我什么话也说不出来。

而米尔迦也没有再说什么。

即使半径是零，圆就是圆，不过是已经变成点的圆。

然后，我……

我们……

就这样无言地……

缓缓地将脸颊靠近……

「现在是闭校时间。」

瑞谷管理员的声音传来。

我们的距离从零一口气增加。

直到我们手长的和为止。

★★「我」的笔记本

我和米尔迦所导出的一般项数列C<n>＝1，1，2，5，14，……，被称为卡塔兰数(Catalannumber)(无名之声：也称卡特兰数)，而我思考出「漂亮的积的和」被称为折积(Convolution)(无名之声：也称褶积)。

将数列与生成函数对应的话，就能把『将数列折积的数列』和『乘上原本的生成函数而得到的函数』互相对应。也就是将数列a<n>与b<n>的折积以a<n>*b<n>表示的话，会形成以下对应。

数列←→生成函数

a<n>＝a<0>，a<1>，……，a<n>，……←→a(x)＝Σ<k=0到∞,a<k>x<k次方>>

b<n>＝b<0>，b<1>，……，b<n>，……←→b(x)＝Σ<k=0到∞,b<k>x<k次方>>

夜里，我在房间里兴奋地想着这个对应，『数列国度』的「折积」就是『生成函数国度』的「积」。

真是完美的对应。