好久沒更新了啊。給兄弟們整個(gè)新活。今兒探討的問題是關(guān)于排列組合的。(別問我為啥現(xiàn)在才更新，蟹蟹)

1.引例

直接上干貨了。

這是一個(gè)較為復(fù)雜的計(jì)數(shù)問題。 你或許沒看懂。我簡(jiǎn)單解釋一下題目。 假設(shè)道路左側(cè)有三輛車編號(hào)為a,b,c。 這三輛車必須先開進(jìn)檢查站然后從右側(cè)離開。 (檢查站里可以停無數(shù)輛車) 假如a先進(jìn)檢查站然后出站。 然后b進(jìn)檢查站，c跟著進(jìn)檢查站。 此時(shí)b被c擋住了，因此只能c先出站然后b再出站。 那么三輛車出站的順序就是a,c,b了。 這題就是要計(jì)算總共有幾種可能的出站順序。 為了不讓你直接空手枚舉出答案，題目假定一開始有161616輛車。我倒覺得不如直接變成n輛車。

2.特點(diǎn)概括

咱們先對(duì)這一類問題做一個(gè)特點(diǎn)概括。 這類問題的關(guān)鍵點(diǎn)是那個(gè)檢查站。

1.

所有元素必須先進(jìn)入檢查站然后離開檢查站。

2.

檢查站只允許最后一個(gè)進(jìn)站的車離開即

先進(jìn)后出

。

熟悉計(jì)算機(jī)科學(xué)的應(yīng)該會(huì)知道，這恰好是計(jì)算機(jī)科學(xué)中

棧

這個(gè)數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)。

好吧，那我簡(jiǎn)單科普一下，畢竟這玩意生活中很常見。 比如說咱們洗碗，每洗一個(gè)碗就把它疊到已經(jīng)洗好的碗堆上。這樣的一疊碗，如果你要拿出其中的一只碗是不是只能從頂上拿。如果你不動(dòng)整疊碗，那你想放新碗也只能在頂上放。所有的碗將來也都要放到那個(gè)碗堆里吧。 在計(jì)算機(jī)科學(xué)里，如果我們要模擬這堆碗的情況，是不是也就需要類似的結(jié)構(gòu)了。 因此，計(jì)算機(jī)科學(xué)中定義了一類專門的數(shù)據(jù)結(jié)構(gòu)稱為棧也具有類似的特性。 碗堆有兩頭，一頭可以放和拿新碗，對(duì)應(yīng)棧頂(top)。 另一頭不可以，對(duì)應(yīng)棧底(bottom)。 放新碗稱作壓棧(push)。 把碗拿走稱為出棧(pop)。 只能對(duì)最上面的碗進(jìn)行操作對(duì)應(yīng)只能對(duì)棧頂數(shù)據(jù)操作。 先放的碗反而要后拿就是先進(jìn)后出了。

3.圖解

好了，回歸正題。畢竟你們是來看這類問題怎么解的而不是來看什么棧的。 這類問題我們是可以利用一張圖來解決的。(這種離散問題的圖解你是不是在數(shù)列里看到過呢？蛛網(wǎng)圖對(duì)吧) 我們用橫坐標(biāo)x表示曾經(jīng)或正在站內(nèi)的車的數(shù)量。 用縱坐標(biāo)y表示已經(jīng)出站的車的數(shù)量。 那么一開始所有車都沒進(jìn)出站，因此對(duì)應(yīng)(0，0)點(diǎn)。 最后所有車都進(jìn)站然后出站了，對(duì)應(yīng)(n，n)點(diǎn)。 每次我們的操作都是讓一輛車進(jìn)站或者出站。也就是讓橫坐標(biāo)或者縱坐標(biāo)+1。 因此總的實(shí)現(xiàn)路徑就是一條沿著格點(diǎn)從(0，0)到(n，n)的折線。 比如這樣，

然而，有一條紅線不能碰。 如果檢查站里已經(jīng)沒有車了那么我們就不能繼續(xù)執(zhí)行讓一輛車離開的操作了。 這樣的路徑是

非法

的。 那，哪些路徑是非法的呢？ 咱們往前邁一步。 讓沒有車的檢查站繼續(xù)出車的前一步是不是檢查站沒有車啊。 那檢查站沒有車的時(shí)候，橫縱坐標(biāo)是不是相等的啊。 因此，臨界線就是y=x。 越過y=x的路徑就是非法路徑。或者說，我們要時(shí)刻保持y≤x。 額，你還沒想明白嗎？ 那就正著想。 每次出車前需要先保證檢查站有車。 那么曾經(jīng)和現(xiàn)在入站的車的數(shù)目x 就必須大于等于 已經(jīng)出站的車的數(shù)目y。 也就是x≥y。 那么非法路徑就經(jīng)過了y=x上方的區(qū)域。 或者說非法路徑觸碰了y=x+1這條線。 如果我們排除了所有非法路徑那就能計(jì)算出合法路徑的數(shù)目了。 當(dāng)然，前提是我們要先算出所有路徑(包括合法與非法的) 這個(gè)非常簡(jiǎn)單。 從(0，0)到(n，n)總共需要走2n步，其中你需要選擇n步往右，剩余的n步自然就是往左了。 因此總的方法數(shù)的C(2n n) 接著只要算出所有非法的路徑的個(gè)數(shù)即可。 這個(gè)其實(shí)也很簡(jiǎn)單。 非法路徑走的時(shí)候必然遇到y(tǒng)=x+1這條線，這時(shí)我們做前一部分路徑關(guān)于y=x的的對(duì)稱路徑。 得到一條從(-1，1)到(n，n)的路徑。 這條路徑的總個(gè)數(shù)和非法路徑的總個(gè)數(shù)是相等的。(證明就交給你嘍，之后我會(huì)稍微給你個(gè)提示) 從(-1，1)到(n，n)總共需要(n-(-1))+(n-1)=2n步，其中n+1步向左，n-1步向上。 因此路徑總數(shù)為C(2n n-1)。 二者相減就是本專欄探討的問題的解答了。

4.雜談

在本專欄的第三部分我們用圖解的方式解決了這個(gè)問題。實(shí)際上，這張圖被稱作惠特沃斯（Whitworth）線。 而問題的答案C(2n n)-C(2n n-1)被稱作卡特蘭數(shù)。 不過你看到的卡特蘭數(shù)公式應(yīng)該不是這樣的。 利用組合數(shù)公式 C(2n n)-C(2n n-1)=C(2n,n)/(n+1) (n=0,1,2,...) 后者是更常見的卡特蘭數(shù)公式。 至于前面提到的提示嘛。 既然是提示我就不能說得太明顯了，給你大致指?jìng)€(gè)方向。 你想想，怎么證明兩個(gè)集合所含元素?cái)?shù)相等？ 最簡(jiǎn)單的辦法當(dāng)然是把兩個(gè)集合所含元素個(gè)數(shù)數(shù)出來比較嘍。 但我們就是為了求元素個(gè)數(shù)，因此不能用這個(gè)方法。 想一想，如果你拿了一箱蘋果要分給班里的同學(xué)們，你怎么在不數(shù)你帶了幾個(gè)蘋果的情況下知道同學(xué)多還是蘋果多呢？ 直接分一分唄。 給每個(gè)同學(xué)一個(gè)蘋果，如果每個(gè)同學(xué)都分到了一個(gè)而且沒有多余的蘋果(這一半你也可以認(rèn)為是在給蘋果找主人，每個(gè)蘋果都有一個(gè)主人)就說明蘋果和同學(xué)數(shù)目一樣。 如果我們抽象到純數(shù)學(xué)領(lǐng)域上就是建立蘋果和同學(xué)的映射關(guān)系滿足， 每個(gè)蘋果都有唯一確定的同學(xué)與之對(duì)應(yīng)。(構(gòu)成蘋果到同學(xué)的映射f) 每一個(gè)同學(xué)都有至少一個(gè)蘋果(f是滿射) 不同的蘋果有不同的主人。(f是單射) 如果一個(gè)映射既是單射又是滿射，那么這個(gè)映射就是雙射。 因此要比較兩個(gè)集合所含元素的多少可以通過建立映射關(guān)系來實(shí)現(xiàn)。 一般地，如果我們能建立集合A到集合B的雙射f，那么集合A與集合B所含元素的個(gè)數(shù)相等。 特殊地，這條對(duì)含有無窮多個(gè)元素的集合也成立。(這個(gè)涉及到實(shí)變了，我就不多展開了。有興趣的話可以自己去網(wǎng)上查閱資料)