深夜。家人都已經入睡，家中很安靜。我一個人在自己房間裡，毫無顧忌地思考問題。
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) 的有限項代數式。
剩下只需把有限項代數式的冪級數展開就可以了。