深夜。家人都已经入睡，家中很安静。我一个人在自己房间里，毫无顾忌地思考问题。
Cn 的推导公式已经求出，如下所示。
我准备接着思考另一个问题，关于如何解生成函数的问题。
米尔嘉曾经和我一起求过斐波那契数列。那时，米尔嘉把数列和生成函数对应起来进行了计算。我们在两个王国——“数列的王国”和“生成函数的王国”漫步穿梭。
我打开笔记本，一边回忆一边开始写。
当我们得到数列 这个条件时，我们将数列的各项变为函数的系数，得到了 这个形式，我们考虑的就是这种形式的幂级数。这就叫作生成函数。然后，我们考虑了以下的对应关系。
如果这样考虑对应关系的话，就可以只用一个生成函数来表示无限持续下去的数列。接着，如果将生成函数表示为有限项的式子，就可以得到数列的通项有限项公式。
米尔嘉和我运用生成函数求得了斐波那契数列的通项公式。我们亲手将支离破碎的数列用生成函数这条线串了起来。
我现在想用上次的解法来试着解这道题。
求 Cn 的有限项代数式的“旅行地图”
对于有 n 个加号的式子，假设为其添加括号的方式有 Cn 种，下面我们来考虑数列 。
然后，将这个数列的生成函数用 C(x) 来表示。为了不让数列变得混乱，我们引入 x 这个变量，xn 的指数 n 与 Cn 的下标 n 相对应，这样 C(x) 就可以用以下形式来表示。
以上就是生成函数的定义。到此为止，我自己还没有动过脑子。是啊，在生成函数的王国徘徊还是比较简单的。
真正要动脑子的是接下来的部分。
现在我手中的武器就只有 Cn 的推导公式。下一步就是运用推导公式求出 C(x) 的有限项代数式。那么，我来求一下 C(x) 的“关于 x 的有限项代数式”吧。这个式子中应该不会出现 n。
但是这次的推导公式并不像斐波那契数列的推导公式那样简单。在求斐波那契数列的推导公式时，我们把生成函数乘以 x 后，为了使上下式子 x 的次数对齐，将各项系数都向左或向右挪一格，然后只要进行加减运算，就能把 n 抵消。
但是，这次的推导公式 真是不好对付。 这个乘积形式前再加上 ，就是复杂的“先相乘后相加”的形式了。
嗯？
先相乘后相加…… 是这样说的吗？
还是说 Ck 和 的“下标和为 n”呢？
呵呵，我想起了自己对泰朵拉说的台词。
“不要把 n - k 和 k 分开来考虑，而是要把它们想成是‘它们的和为 n’。然后，这个和的平衡点由 0 到 n 进行变化。”
在这次的推导公式中出现的 和上次我对泰朵拉所说的情况很相似。Ck 和 的下标和为 n，然后 k 从 0 开始变化到 n，使这个和的平衡点发生变化。
我想起现在手上的推导公式 主要表示这样的意思：如果能够形成 这样的“先相乘后相加”的形式，那么这个式子就可以被 这个简单形式的项所代替。
什么情况下才能够形成“先相乘后相加”这个形式呢？
……( x + y)(x + y)(x + y) 这个“先相加再相乘”的形式可以变成 x3 + 3x2y + 3xy2 + y3 这个“先相乘后相加”的形式，也就是公式的展开……
也就是说，“先相加后相乘”的形式展开后可以变成“先相乘后相加”的形式。
好，题目的关键就是要形成乘积的形式。我来试着推导一下生成函数的乘积形式吧。自己亲自动手计算，一定能够发现什么。
因为生成函数只是 C(x)，所以将它平方后，可能会出现什么吧。生成函数是这样的。
将生成函数平方后得到这样的形式。
常数项为 C0C0，x 的系数为 C0C1 + C1C0，x2 的系数为 C0C2 + C1C1 + C2C0。
那么，进行一般化的话——我脑海中浮现出了泰朵拉那双大眼睛——先把 C(x)2 中 xn 的系数写出来吧。
写啊，写啊，写啊，只听得到自动铅笔在纸上的刷刷声。
啊，做出来了！这就是 xn 的系数。
我们来关注一下下标。随着 这个数字中左侧的下标 k 逐渐变大，右侧的下标 n - k 就逐渐变小。k 在 0 到 n 的范围内变化。
如果再逐项写出来的话，反而让人觉得难以理解。我们就用 来表示。写成一般化的式子的话，xn 的系数为
因为这是式子 C(x)2 中“xn 的系数”，所以式子 C(x)2 本身就变成了二重和的形式，是这么写的。
做出来了！
做出来了！
我终于做出了 这个“先相乘后相加”的形式。因为我求得了“先相乘后相加”的形式，余下部分如果利用推导公式，就应该能把公式变简单。推导公式为
这个推导公式能够被 这个简单的项所替换。
也就是说，将生成函数 C（x）平方后，式子能够变得非常简单。下面就将 用 来替换。
噢，二重和变成了一重和的形式了！
等一下， 的下标和 xn 的指数正好相差 1。
噢，对了，要去除这个偏差，我可以利用解斐波那契数列时的方法来解决，只要将相差 1 的部分乘以 x 就可以了。两边同时乘以 x。
将等式右边的 x 放入 的式子中。
为了让下标变成与指数相同的形式，将 n = 0 的部分看作 n + 1 = 1。
然后将所有 n + 1 的式子用 n 来替换。
好了，这下等式右边的 几乎和生成函数 C(x) 相等了，只剩下把 C0 这部分减去就好了。
这样一来，n 就消除了。
把 C0 = 1 代入上式并整理。
因此，我们得到了关于 C(x) 的二次方程式。假设 x 不等于 0，我们就可以求得方程的解。
嗯，完成得很顺利。
根据生成函数的“先相乘后相加”这个特点，我们推导出了有限项代数式。真没想到生成函数的乘积有这么大的作用啊！
我并不知道为什么生成函数 C(x) 会有带正负号的两个解，原本 的部分该如何我也不知道，我觉得这个题真是越来越深奥了。
不管怎么样，n 被抵消掉了。
我终于求出了生成函数 C(x) 的有限项代数式。
剩下只需把有限项代数式的幂级数展开就可以了。