卡特蘭數

卡特蘭數：他是一串數列

來歷：只能往右走或往上走，從左下走到右上（正方形），不能超過對角線的種類數。 

遞迴式：CAT n+1 = SUM ( i = from 0 to n ) CAT i * CAT n-i

一般式：CAT n = 1/(n+1) * (C 2n取n)

帥氣遞迴式：CAT n+1 = (4n+2)/(n+2) * CAT n

要說的是他的應用和廣義的卡特蘭數：（這完全是我胡亂思想出來的，有錯請跟我說）

1.n*n正方形，不超過對角線的走法種類（基本）

2. n對括號可以產生的正確匹配方式種類數（簡單）

『解說：（ 是往右走，）是往上走，其他跟 (1) 一模一樣』

3. n個節點產生的二元樹種類數（困難，請大神不要嗆我X{）

『解說：首先要先知道n個節點完整的二元樹會有n+1個空位（空位定義：上方有節點但此地無節點），pf: n=1，有兩個空位，每增一個節點，會多一個空位，故得證。接下來要靠想像力了，我有解說啦，可是沒有圖，真可惜～』

詳細講解：

        有一個空圖。放一個節點＝往右走，放一個空位＝往上走。

        pf: 如果放的空位比節點多，這個圖就會是一個『完整』（ != 完全 ）的二元樹，也就是無法在繼續放點了（看我前面的pf吧），所以不能超過對角線，這樣就對應到 (1) 啦～開心XDDDD

好，再來就要說今天比賽中的三元樹了，其實網路上真的沒什麼廣義卡特蘭數的講解，所以一切都是從我小小的大腦胡亂思考而成的，請不要把我嗆爆XD

廣義卡特蘭數：原本是『向上走的<=向右走的』，但這裡乘上一個可愛的常數 k （好啦，他不可愛）變成『向上走的<=向右走的*k』，所以本來的正方形也變成矩形了，很棒吧～XD

一般式：CAT n (k) = 1/( (k-1)n+1 ) C kn 取 n

神奇遞迴式：自己不會算喔！

應用：n個節點可產生的k元樹個數。

『解說：跟剛剛的二元樹情況其實很像，只是節點數 n 的k元樹，空位數為 kn+1，證明方式依然相同，而且想法其實也是一模一樣的（事實上，我是為了想這題，才會想剛剛那樣的解釋方式）』