尔迦嘟起嘴抱怨：「我还没说完啊。」

◎◎◎

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

当加号数量超过括号数量的时候，就会像你说的一样，也就是上图中通过◎的状况，不通过◎而从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>＝－

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

C<n>＝<2n,n＋1>

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

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

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

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

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

＝<n次递降阶乘>×

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

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

＝×<n次递降阶乘>

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

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

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

＝)×/n<n次递降阶乘>)整理

＝)×<n,k>

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

C<n>＝)×()<2n,n>

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

◎◎◎

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

C<1>＝)××＝1

C<2>＝)××/)＝2

C<3>＝)××/)＝5

C<4>＝)××/)＝14

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

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

※※解答7－1

C<n>＝)×()<2n,n>

「那这次换你了。」

7．5．2面对生成函数

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

有点不甘心。

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

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

非常地不甘心。；

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