2個數字 1 種

(a+b)3個數字 2 種((a+b)+c)(a+(b+c))

那麼n個數字加括弧的方法有多少種呢？謝謝。

這種問題肯定是早就已經被前人研究透徹了的，本來想隨便找本書抄一抄就完了……

結果，尼瑪好死不死翻出來的居然是柯斯特利金的《代數學引論》（我明明記得這個問題它有過程的）……

【摘自第一卷——《代數學引論·基礎代數》（高教社版本）】。

結果記憶太模糊。。。又見「留作習題答案略，給了提示就不難」。。。喏～！思路作者給指出來了，中間過程自己腦補一下吧。。。喂喂這不賴我啊，我只是個抄書匠而已……書上就這麼寫的～

唉～算了，自己挖的坑還是自己填上吧……

以下列出所需的中間步驟並逐一補充細節。

一、「『顯然』的遞推關係 [公式] 」：

關於這一點，本題下 @qfzklm 的答案：

給n個數的加法加括弧的方法有多少種？?

www.zhihu.com圖標

已經寫得很清楚了，此處不贅。

二、 [公式]：

將遞推關係代入 [公式] 的冪級數表達式，得到—— [公式] 。

另一方面， [公式] 。

立刻得到 [公式]。

【解二次方程就算了吧啊……哎～！那個初中沒畢業的刷什麼知乎啊！好好做作業去！這個答案是第三級的，很黃很暴力，不適合未成年的你散了散了。。。】

三、「如果冪級數 [公式] 滿足 [公式] ， [公式] ，則 [公式] （姑且認為泰勒展開式存在）」：

若 [公式] ，則 [公式] ，將其展成麥克勞林級數： [公式]

。

四、「『簡單』的代換給出了最後的表達式」：

首先，驗證一個「醜陋」的公式……

引理： [公式] 。

證明：對 [公式] 進行歸納。初始情況應從 [公式] 開始，此時左邊等於 [公式] ，右邊等於 [公式] 。現歸納地假設公式對於 [公式] 成立，即 [公式] 。考慮 [公式] 的情形，此時左邊為： [公式] ，顯然等於右邊。歸納假設成立，引理得證。

其次，將 [公式] 代入三、之結論 [公式] ，得 [公式] ；而由於 [公式] ，作變數代換： [公式]

，則第 [公式] 項係數 [公式] ，依引理即有—— [公式] ，其中 [公式] 即是眾所周知的（第 [公式] 個）明安圖 — 歐拉 — 卡塔蘭數。

特喵的每一回抄書寫答案都跟不是抄的一樣……

聽說最近被吐槽「從數學答主變成了狗糧答主」, 決定來給自己正個名.

首先我們發現, 寫加法式子時, 只需要寫半個括弧就夠了. 例如 [公式] , [公式] , [公式] . 注意到加號總是連接兩個「括弧」(或者單個字母)的, 另一半括弧的位置唯一確定.

更簡潔一些, 我們固定 [公式] 個數的順序後, 只保留括弧和加號. 例如 [公式] 就可以簡記作 [公式] . 於是加括弧的方法就變成了找 [公式] 個括弧和 [公式] 個加號的排列. 但是, 為了讓這個排列能夠還原成加法式子, 我們需要做一點限制: 對於一切 [公式] , 在第 [公式] 個位置之前的括弧的個數不少於加號的個數.

(以下內容抄自Buraldi的Introdutory Combinatorics, 給老爺子打call)

現在我們將括弧寫成 [公式] , 加號寫成 [公式] , 問題變成了: 考慮 [公式] 個 [公式] 和 [公式] 個 [公式] 排成的序列, 使其部分和 [公式] 恆非負, 求滿足條件的序列的個數.

我們將滿足條件的序列稱作「可接受的」, 個數記作 [公式] , 不滿足條件的序列稱作「不可接受的」, 個數記作 [公式] . 那麼顯然 [公式].

我們先來計算 [公式] . 由於這樣的數列不滿足條件, 一定存在正整數 [公式] 使得部分和

[公式] ;

不妨取滿足條件的最小正整數 [公式] , 那麼一定有 [公式] , 且

[公式] .

進而 [公式] 是偶數, [公式] 是奇數.

下面我們同時改變序列的前 [公式] 項的符號, 其餘項不動, 設得到的序列為 [公式] . 由於前 [公式] 項中 [公式] 的個數比 [公式] 恰好多一個, 上面得到的序列由 [公式] 個 [公式] 和 [公式] 個 [公式]構成.

上述過程是可逆的. 對於給定的由 [公式] 個 [公式] 和 [公式] 個 [公式]構成的序列, 我們能夠找到一個位置, 在此位置之前的 [公式] 的個數第一次超過了 [公式] 的個數. 改變此位置之前的 [公式] 的符號, 我們恰好得到一個不可接受的序列. 於是 [公式] . 故

[公式]

這裡 [公式] 就是通常所說的Catalan數. 題主要的答案是 [公式] .

這個問題有不少有趣的組合模型. 例如:

有 [公式] 個人去劇場看戲, 票價為5元, 這 [公式] 個人中有 [公式] 個人拿著10元紙幣, 另外 [公式] 個人拿著5元紙幣. 問有多少種排隊的方法使得售票員不需要準備零錢就可以滿足大家的購票需求?

一個律師的工作地點是在自己家往北 [公式] 個街區再往東 [公式] 個街區, 但沿他家到事務所的對角線剛好是一條沒有橋的河, 那麼這名律師從家到事務所有多少種不同的走法?

這兩個模型裏賦值 [公式] 的方法都很顯然, 提供給大家娛樂一下 */ω＼*)

答案就是Catalan數，其他答案裏是有提到為什麼滿足那個遞推關係的，我這裡就不贅述了

如果我們令數列 [公式] ， [公式]

滿足遞推關係：

[公式]

則可得 [公式]

這就是Catalan數的遞推公式和通項公式

一般書上給出的通項公式的證法多數是構造各種組合數學的模型，或者使用母函數法

我補充個只依賴數學歸納法的純粹初等證法：

它等價於證明恆等式

[公式]

（ [公式] ， [公式] ）

注意 [公式]

由對稱性，顯然

[公式]

[公式]

於是它等價於證明恆等式

[公式]

（ [公式] ， [公式] ）

[公式] 時顯然它是成立的

假設 [公式] 時它也成立，即

[公式] [公式]

注意：

[公式]

這樣可得

[公式]

便由數學歸納法證明瞭

[公式]

也即

[公式]

（ [公式] ， [公式] ）

記n個數的加法加括弧的方法有[公式] 種，當我們把最外層的括弧剝開時，剩下的是被兩組括弧分成的兩個部分，每個部分都分別有[公式] 和[公式] 種加括弧的方法，所以我們有遞推關係：

[公式]

其中，記[公式]，則[公式] ，[公式] ，[公式] 等等。。

上述遞推關係給出的是卡特蘭數Catalan number - Wikipedia。

【附註】

原先認定加括弧的行為和標記加號運算次序的想法是不對的，因為我們總是有一個默認的順序，即從左到右，這一點導致[公式] 的值是5而不是6。例如評論中的例子，((a+b)+(c+d))，我們不能先計算(c+d)而是要先計算(a+b)。

【原答案】

n個數字，一共有n-1個加號，加括弧的行為就是給這n-1個加號標註計算順序，先計算哪個加號，再計算哪個加號，等等。。

所以每個加號頭上都被標記了從1一直排到n-1的數，表示某個加號在第幾次被計算。。

所以最終，一共有(n-1)!種計算方式，也就是(n-1)!種加括弧的方式。。

我在寫這篇回答時，這個問題的答案已經很明確了，是第n-1項卡特蘭數，有好幾位答主給出了正確答案，其中最高贊給出了詳細的推導過程，但是用到的工具比較高等，普通初中生根本看不懂（原答主自己說的(＊／ω＼＊)），為了照顧小朋友，我在這裡補上一個初等的證明，各位初中的小數學愛好者們儘管放一百個心，保證不含任何微積分，不含任何無窮級數，請放心食用（致 死 量）

證明過程主要用到演算法和歸納，從另一個角度來刻畫它的遞推關係。

這裡先重新給你們捋一遍這個加括弧的過程啊~啊你看這個括弧它又大又圓。。。。拿錯書了（摔

首先我們都知道什麼是加法結合律吧，就是

[公式]

對於小學生來說，做加法運算時，他們算到最後一定會有一個最終結果，不然考試是要被數學老師罵的→_→

這一點在這裡很關鍵，我是說認真的，因為這裡涉及到一個哲學真理，叫萬事皆有果，因為有這個真理的存在，我們才能讓小學生擁有了選擇不被數學老師罵的權力，大家忍住不要笑，我是認真的（噗~哈哈哈哈

那又是什麼確保了這一點呢？是人性的扭曲還是道德的淪喪？！拿錯劇本了(ノ｀Д)ノ

引理1（xjbls lemma）數學上叫表法唯一性，若不然現實世界就會出現矛盾！為了禁止矛盾的出現，這是必然遵守的。

有了這個引理我們就可以愉快地進行下一步的討論了，希望上面那段瞎扯廢話能成功地吸引到你的注意力2333333333

定理1（feihua theorem）對於若干項的數值相加，由x-lemma可知，表達式的項數必然隨著加法運算符的縮並不斷減少，而在只有兩項的表達式中一個運算符的縮並能減少一項，兩個項之間不能並列相排，中間必然隔著一個運算符，所以又由歸納原理可知：

（i）在任意項的表達式中，一個運算符只能消掉一項

（ii）n項的表達式必有n-1個運算符。

（iii）n項的表達式最多能進行n-1次運算。

這三個結論是等價的。

現在我們進行加括弧的工作，我們進行以下約定：

定義1 定義符號「（）」為括弧，「（」為其左部，「）」為其右部。

定義2 定義括弧位「 [公式] 」和「 [公式] 」，其中 [公式] 為表達式

[公式]

定義3 括弧有縮並運算，運演算法則為從內到外，且括弧之間不能內外交換（兩括弧間的交叉穿越）。

這意味著不同括弧間的左部和右部不能同時插在相同的括弧位上，否則會造成兩個括弧同時對一個運算符做縮並，這使得最後的表達式不能縮並為一項。這導致了以下引理的產生。

引理2（括弧對應引理）每個括弧對應縮並一個運算符。這是顯然的。

引理3 （這個定理的重要性都不如其他的以至於我都沒有給它想好名字φ(&>ω&因此我們只需要考慮n-2個括弧的插入情形。

定義4 我們對每一個括弧按照從外到內的順序進行編號，稱其為括弧序。具體表示為 [公式] ，其中i為 [公式] 的正整數。

結合定義3可以得知，每個括弧有其唯一的括弧序而且還有確定的活動區域。下面的定理就給出了這個區域。

定理2 （賽堡定理）對於括弧類 [公式] ，其對應的活動空間為 [公式] 。

這是數學家賽堡.T.瑪德在喫海底撈時靈光一閃。。。。wbbxql總之就是塞爆→_→

這個定理很深刻（迫真），反映了括弧具有得天獨厚的對稱性，我們可以通過控制在括弧的一邊的位置來決定另一邊的位置選取，而這個選取在定義3的「合法」操作中是唯一的，這意味著我們可以只關心括弧的左部而不用關心右部！實際上由於定理2，在最後一個括弧 [公式] 到達終點 [公式] 時，前面的括弧間至少兩兩相隔一項，否則與定理2矛盾。於是由歸納法則得到定理4。

有了這些鋪墊，我們就可以對縮並方法進行計數了。

於是方法數為

[公式]

（註：此處累乘表示累加符號的並列， [公式]符號用作指標以方便作對應）

這樣演算法解就弄出來了，會編程的中學生可以試試遞歸演算法把它實現。但是這離我們想要的的封閉解卡特蘭數還差點距離，繼續處理~

這裡就不得不提一下有限微積分的技術了，這真的不是微積分啊，離散空間的事能叫連續嗎？（霧

其實就是一套關於數列求和的技巧，在高德納的《具體數學》裏有完整的介紹，極力推薦你看這本書，這真的只是初等範疇的技巧。

在瞭解了相關技術後，就好辦了

[公式]

emmmm。。。。。好的，能拿去辟邪了2333333

其中 [公式] 為指標變換，表示從順序累加轉換成逆序累加，總和不變，最後引入差分變數 [公式] 讓其與有限微積分的技術適配。

然後定義運算元[公式] ，於是式子就簡化成[公式] 。

keep going~

[公式]

為觀察其遞歸關係，引入指標k，生成如下恆等式列表

[公式]

其中 [公式]分別為第k次求和的上限和下限， [公式]則分別為第k次求和的上限和下限的函數值。由於下限值必為常數，由求和分離定理可知

[公式]

直接令k=n-2，即得

[公式]

到此為止，我們就找到了這個數列的遞歸關係，而這正是卡特蘭數的遞歸式。

百無聊賴，僅為博君一笑(o°ω°o)

這裡這裡附上遞歸演算法的實現代碼：

#include&
int D(int,int,int);
int D(int);

int main()
{
using namespace std;
cout&3)
for(int i=d;i&<=u;i++) D(n-1,i,u+1); else for(int i=d;i&<=u;i++) s++; return s; }

然後還有改良後的多項式時間複雜度的演算法：

#include&
bool logic(int*,int);
int D(int);

int main()
{
using namespace std;
cout&ar[n-3])
ar[n-3]++;
else
for(int i=n-3;i&>=1;i--){
if(i+2==ar[i]ar[i-1]&

親測有效，值都為第n-1項卡特蘭數。

推薦閱讀：
相關文章