1樓：
答案確實就是Catalan數，我簡單講一兩句吧
先考慮乙個問題：
乙個質點初始時刻位於原點，每一步向 軸正方向或負方向前進一步.
現在該質點第一步來到了點 ，並於 步後回到原點，在中途不觸碰原點，問該質點運動的可能的路徑數有多少.
顯然，這個質點第 步來到了點 1
而第 步也必然位於點1
從第 步到第 步這中間的 步，是從點 出發最後回到點
當然必然是其中 步沿著正方向， 步沿著負方向
先假設不考慮這 步不允許接觸原點的禁忌，那麼總共有 種走法
現在，只要從這 種走法中，把接觸到原點的走法全部刪了就行了
任意一種接觸到原點的走法，都可將其在第 步之前最後一次離開原點前的所有步驟關於原點作一次反射，變成從點 出發，經歷 步到達點
同樣，從點 出發，經歷 步到達點 的所有走法，也都可以在第 步之前最後一次穿越原點前的所有步驟關於原點作一次反射，變成從點 出發，中途穿過原點，最後再回到點
這樣，上述第 到 的 步，就等價於從點 出發，經歷 步到達點
必然是 步沿正方向， 步沿負方向
總共有 種走法
那麼可以得到，從點 出發， 步後回到點 的走法，一共有：
種不同走法
它的乙個等價問題是：
從原點到 點的除端點外不接觸直線 的單調路徑個數為
把上述質點移動問題的步驟數從 改成 的話，走法就是一共有 種
這也就是Catalan數
該質點移動的問題便等價於原問題，第k個盒子裡取到黑球認為是質點往正方向移動一步，反之取到白球認為是質點往負方向移動一步
為了更加便於理解，原問題也可以做個完全等價的小變化：
事先多放2個盒子，增加一黑一白兩個球，在第0個盒子裡放乙個黑球，第2n+1個盒子裡放乙個白球
原問題要求等價為任取前m（0≤m<2n+1）個盒子，其中黑球數目大於白球
在研究二項分布時，有類似這樣的題目：
甲、乙兩人賭博，每次賭博甲若輸了，支付給乙一塊錢，反之則乙付給甲一塊錢
每一次賭博二者勝負都是等可能的，假設第一次賭博甲贏了一塊錢，然後他們繼續賭博.
只要甲發現自己賭博總盈利開始變為0，就立刻收手
求賭博最終停止的概率.
它的某一種處理過程實質上也是與之等價的
如果我們令數列 ，
滿足遞推關係：
則可得這就是Catalan數的遞推公式
Catalan數可由很多其他的組合數學問題得到，最早是Euler在計算凸 邊形不同的三角形剖分個數時引入的
在乙個凸 邊形中，通過插入內部不相交的對角線將其分成一些三角形區域，有多少種不同分法？
由這個問題也可以直接推出Catalan數的通項公式
除了這個問題外，以下問題的答案也與Catalan數有關：
有 個葉子的完全二叉樹的個數為
某個不滿足結合律的乘法運算 ，對 任意加括號，能得到多少種不同的乘法方案？答案也是
最後，我試圖用一種完全初等的方法來推導一下Catalan數的通項公式
考慮證明恒等式
（ ， ）
注意由對稱性，顯然
於是它等價於證明恒等式
（ ， ）
時顯然它是成立的
假設 時它也成立，即
注意：這樣可得
便由數學歸納法證明了
也即（ ， ）
由Catalan數的遞推關係推導通項公式，還有很多其他推導方法，其中最常見的是母函式法，隨便翻閱一本組合數學或者離散數學教材，裡邊應該都有，我就不贅述了.
2樓：曾匯宛
通項公式是f(n)= ，即Catalan數列，證明如下：
先看個簡單的情況(路徑規劃)，如圖1所示，從A點到B點最短的路線有多少條？
圖11、標數法
要求最短路徑，那從A點開始只能向上走或向右走，從A點到達網格中任一點的方法只有兩類，如O點所示，從左到右到達O點或從下到上到達O點，從A點開始，每一點標上方法數，可求得答案(如圖2)。注意：標數法滿足(n, m)=(n-1, m)+(n, m-1),(n, m1)
圖22、排列組合
將問題轉化為乙個人從A點只能向上走3步和向右走3步，一共有幾種走法到達B點？ =20種。
回到本題中，以向上走為放黑球，向右走為放白球，在2n個順序擺放的盒子中填充n個白球和n個黑球的所有可能性，即隨機排列數g(n, n)= (對角線n=m)上，如圖3所示，且滿足g(n, m)=g(n-1, m)+g(n, m-1),(n, m 1)
圖3若沿著對角線畫一條虛線，取左上部分，滿足任取前m個盒子，其中黑球數目不少於白球。標數得圖4，滿足的排列方式有數列f(n)=1、2、5、14、42...(即catalan數列)
圖4隨機排列數與黑色數字作差，可得左上部分的增量h(n, m), (m 1,)m=0無增量，去掉黑色數字，剩下隨機排列數和增量，故Catalan數列f(n)＝g(n, n) - h(n, n),(n≥1)。
如圖5所示，基於標數法的原理增量仍滿足h(n, m)=h(n-1,m)+h(n,m-1),(m 2)。
圖5如圖5所示，由於第1行和第2列相等且為1，根據標數法原理(n, m)=(n-1, m)+(n, m-1),(n 1, m 2且nm-1)，第n+1列和第n行關於直線n=m-1(實對角線)對稱分布，因此對角虛線增量h(n, n)等於n=m-2(綠色虛線)上的隨機排列方法數g(n-1,n+1)，故增量h(n, n)=g(n-1,n+1)= =
，則catalan數列f(n)=g(n, n)- h(n, n)=-
= ，證畢。
3樓：
已經有回答給出:catalan number.
具體來說，數列是1,2,5,14,42,132,429,……
隨手畫個通俗、直觀的示意圖，數數路徑數目就知道。(不用真的「數」，下乙個節點的數值＝其左節點數值+其上節點數值)
4樓：「已登出」
高中遇見過這個題。這個題可以轉化成乙個路徑問題。可以畫乙個n×n的網格，排序問題可以轉化成從左下頂點，走到右上頂點一共有多少條路徑。
(向右走等價放黑，向上走等價放白)(只能向右走或向上走)滿足黑球數量大於等於白球，所以路徑必須在下半個等腰三角形中。。。圖中陰影部分
高中大概做得4×4，我考慮下通解…………如果想不出來額……就想不出來吧
乙個無論在哪接到球就能馬上投進的球員在NBA能有多大作為？
投的進球，你就是庫里或者湯普森，投不進球你就是老年的JR.這個主要看你的命中率，如果有37 以上就可以隨便投三分了！這個問題我不是才回答過，怎麼又出來了。如果乙個人投籃命中率為百分之百，在NBA能打出好成績嗎？投籃命中率百分百，出手就中，無視封蓋。這樣的人，要麼一切OK，要麼被別人KO。看看庫里和湯...
乙個正整數表示成n個自然數的和（無順序），有幾種分法
格羅卜學數學 首先我們要轉化一下問題.問題 乙個正整數 表示成 個非負整數的和 無順序 有幾種分法?容易看出這個問題與 問題 乙個正整數 表示成 個正整數的和 無順序 有幾種分法?答案 這裡的 表示分拆數.由後面給出的遞推公式容易進行計算.這個符號的具體說明我們慢慢道來.整數的部無序分拆 是整數.整...
荒野大鏢客2救贖中的聖丹尼斯城中的乙個npc（英國人）不停地找他的朋友加文，這是彩蛋嗎？
伊紅美男 很喜歡這個彩蛋，尋找加文就像等待戈多一樣，表現的是乙個什麼也沒有發生，誰也沒有來，誰也沒有去的戲劇。劇本所揭示的現代人的生存狀態，表現出現實世界的荒誕和無意義，深深地撥動了那個社會條件下人們的心弦。等待，象徵著沒有意義的生活。亞瑟和加文的朋友就像等待戈多裡的兩個人，他們尋找的都是乙個希望，...