組合數(shù)學-catlan數(shù)課件

§2.11Catalan數(shù)這一節(jié)討論Catalan數(shù),其遞推關系是非線性的,許多有意義的計數(shù)問題都導致這樣的遞推關系.本節(jié)將舉出一些,后面還將見到.一個凸n邊形,通過不相交于n邊形的對角線,把n邊形拆分成若干三角形,不同拆分的數(shù)目用表之.

§2.11Catalan數(shù)這一節(jié)討論Ca1§2.11Catalan數(shù)例如五邊形有如下五種拆分方案，故圖2-11-1§2.11Catalan數(shù)例如五邊形有如下五種拆分方案2§2.11Catalan數(shù)1.遞推關系定理：§2.11Catalan數(shù)1.遞推關系3§2.11Catalan數(shù)證明：的證明：如圖所示，以作為一個邊的三角形，將凸邊形分割成兩部分，一部分是邊形，圖2-11-2§2.11Catalan數(shù)證明：的證明：圖4§2.11Catalan數(shù)另一部分是邊形，即點可以是點中任意一點。依據(jù)加法法則有§2.11Catalan數(shù)另一部分是5§2.11Catalan數(shù)的證明：如圖所示，從點向其它個頂點可引出條對角線。對角線把邊形分割成兩個部分，因此圖2-11-3§2.11Catalan數(shù)的證明：圖2-6§2.11Catalan數(shù)以對角線作為拆分線的方案數(shù)為可以是中任一點，對所有這些點求和得以取代點也有類似的結果。但考慮到對角線有兩個頂點，同一對角線在兩個頂點分別計算了一次，§2.11Catalan數(shù)以對角線作為拆分線7§2.11Catalan數(shù)作式并不就給出剖分數(shù)，無疑其中是有重復的。其重復度是由于一個凸邊形的剖分有條對角線，而對其每一條邊計數(shù)時該剖分都計數(shù)了一次，故重復了次即式給出的結果是的倍?！?.11Catalan數(shù)作8§2.11Catalan數(shù)式和式都是非線性的遞推關系?！?.11Catalan數(shù)9§2.11Catalan數(shù)2.Catalan數(shù)計算公式由式及,故得§2.11Catalan數(shù)2.Catalan數(shù)計算公10§2.11Catalan數(shù)由整理得令§2.11Catalan數(shù)由整理得令11§2.11Catalan數(shù)即§2.11Catalan數(shù)即12§2.11Catalan數(shù)§2.11Catalan數(shù)13§2.11Catalan數(shù)例1.,見圖例2.為n個數(shù)的乘積,依據(jù)乘法的結合率,不改變其順序,只用括號表示成對的乘積.試問有幾種不同的乘法方案?§2.11Catalan數(shù)例1.14§2.11Catalan數(shù)令表示n個數(shù)乘積的對括號插入的不同方案數(shù).令故得而且故即為Catalan數(shù)§2.11Catalan數(shù)令表示n個數(shù)乘積的15§2.11Catalan數(shù)以為例

Catalan數(shù)，下面建立式中不同的乘法順序和一個5邊形不同拆分的一一對應關系，如圖§2.11Catalan數(shù)以為例16§2.11Catalan數(shù)§2.11Catalan數(shù)17§2.11Catalan數(shù)§2.11Catalan數(shù)18§2.11Catalan數(shù)圖2-11-6§2.11Catalan數(shù)圖2-11-619§2.11Catalan數(shù)

運算用二分樹表示，兩片葉子分別表乘數(shù)和被乘數(shù)，分支點為運算符，如圖圖2-11-5§2.11Catalan數(shù)運算用20§2.11Catalan數(shù)例3.

n個1和n個0組成一2n位的2進制數(shù)，要求從左到右掃描，1的累計數(shù)不小于0的累計數(shù)，試求滿足這條件的數(shù)有多少？

下面介紹兩種算法。解法1.設為這樣所得的數(shù)的個數(shù)。在2n位上填入n個1的方案數(shù)為，不填1的其余§2.11Catalan數(shù)例3.n個1和n個0組成一21§2.11Catalan數(shù)n位自動填以數(shù)0。從中減去不符合要求的方案數(shù)即為所求。不合要求的數(shù)指的是從左而右掃描，出現(xiàn)0的累計數(shù)超過1的累計數(shù)的數(shù)。不合要求的數(shù)的特征是從左而右掃描時，必然在某一奇數(shù)位上首先出現(xiàn)§2.11Catalan數(shù)n位自動填以數(shù)0。從22§2.11Catalan數(shù)個0的累計數(shù)，和m個1的累計數(shù)。此后的位上有個1，個0。如若把后面這部分位，0與1交換，使之成為個0，個1，結果得1個由個0和個1組成的2n位數(shù)，即一個不合要求的數(shù)對應于一個由個0和個1組成的一個排列?！?.11Catalan數(shù)個0的累計數(shù)，和m個1的累計23§2.11Catalan數(shù)反過來，任何一個由個0，個1組成的2n位數(shù)，由于0的個數(shù)多2個，2n是偶數(shù)，故必在某一個奇數(shù)位上出現(xiàn)0的累計數(shù)超過1的累計數(shù)。同樣在后面的部分，令0和1互換，使之成為由n個0和n個1組成的2n位數(shù)。即個0和個1組成的2n位數(shù)，必對應于一個不合要求的數(shù)。§2.11Catalan數(shù)反過來，任何一個由24§2.11Catalan數(shù)用上述方法建立了由個0和個1組成的2n位數(shù)，與由n個0和n個1組成的2n位數(shù)中從左向右掃描出現(xiàn)0的累計數(shù)超過1的累計數(shù)的數(shù)一一對應。例如是由4個0和4個1組成的8位2進制數(shù)。但從左而右掃描在第5位（打*號）出現(xiàn)0的累計數(shù)3超過1的累計數(shù)2，它對應于§2.11Catalan數(shù)用上述方法建立了由25§2.11Catalan數(shù)由3個1，5個0組成的。反過來對應于。因而不合要求的2n位數(shù)與個0，個1組成的排列一一對應，故有§2.11Catalan數(shù)由3個1，5個0組成的26§2.11Catalan數(shù)§2.11Catalan數(shù)27§2.11Catalan數(shù)例4.由n個1，n個0組成的2n位二進制數(shù)，要求從左向右掃描前位時1的累計數(shù)大于0的累計數(shù)，求滿足這樣條件的數(shù)的個數(shù)。此問題可歸結為圖中從點出發(fā)只經(jīng)過對角線上方的點抵達點，求這樣的路徑數(shù)。相當于求從點不經(jīng)過對角線，抵達點的路徑數(shù)，于是便轉換為§2.11Catalan數(shù)例4.由n個1，n個0組成28§2.11Catalan數(shù)例3的問題。根據(jù)例3的結果。從點通過的點，以及上方的點到達的路徑數(shù)為§2.11Catalan數(shù)例3的問題。29§2.11Catalan數(shù)§2.11Catalan數(shù)30§2.11Catalan數(shù)這一節(jié)討論Catalan數(shù),其遞推關系是非線性的,許多有意義的計數(shù)問題都導致這樣的遞推關系.本節(jié)將舉出一些,后面還將見到.一個凸n邊形,通過不相交于n邊形的對角線,把n邊形拆分成若干三角形,不同拆分的數(shù)目用表之.

§2.11Catalan數(shù)這一節(jié)討論Ca31§2.11Catalan數(shù)例如五邊形有如下五種拆分方案，故圖2-11-1§2.11Catalan數(shù)例如五邊形有如下五種拆分方案32§2.11Catalan數(shù)1.遞推關系定理：§2.11Catalan數(shù)1.遞推關系33§2.11Catalan數(shù)證明：的證明：如圖所示，以作為一個邊的三角形，將凸邊形分割成兩部分，一部分是邊形，圖2-11-2§2.11Catalan數(shù)證明：的證明：圖34§2.11Catalan數(shù)另一部分是邊形，即點可以是點中任意一點。依據(jù)加法法則有§2.11Catalan數(shù)另一部分是35§2.11Catalan數(shù)的證明：如圖所示，從點向其它個頂點可引出條對角線。對角線把邊形分割成兩個部分，因此圖2-11-3§2.11Catalan數(shù)的證明：圖2-36§2.11Catalan數(shù)以對角線作為拆分線的方案數(shù)為可以是中任一點，對所有這些點求和得以取代點也有類似的結果。但考慮到對角線有兩個頂點，同一對角線在兩個頂點分別計算了一次，§2.11Catalan數(shù)以對角線作為拆分線37§2.11Catalan數(shù)作式并不就給出剖分數(shù)，無疑其中是有重復的。其重復度是由于一個凸邊形的剖分有條對角線，而對其每一條邊計數(shù)時該剖分都計數(shù)了一次，故重復了次即式給出的結果是的倍?！?.11Catalan數(shù)作38§2.11Catalan數(shù)式和式都是非線性的遞推關系?！?.11Catalan數(shù)39§2.11Catalan數(shù)2.Catalan數(shù)計算公式由式及,故得§2.11Catalan數(shù)2.Catalan數(shù)計算公40§2.11Catalan數(shù)由整理得令§2.11Catalan數(shù)由整理得令41§2.11Catalan數(shù)即§2.11Catalan數(shù)即42§2.11Catalan數(shù)§2.11Catalan數(shù)43§2.11Catalan數(shù)例1.,見圖例2.為n個數(shù)的乘積,依據(jù)乘法的結合率,不改變其順序,只用括號表示成對的乘積.試問有幾種不同的乘法方案?§2.11Catalan數(shù)例1.44§2.11Catalan數(shù)令表示n個數(shù)乘積的對括號插入的不同方案數(shù).令故得而且故即為Catalan數(shù)§2.11Catalan數(shù)令表示n個數(shù)乘積的45§2.11Catalan數(shù)以為例

Catalan數(shù)，下面建立式中不同的乘法順序和一個5邊形不同拆分的一一對應關系，如圖§2.11Catalan數(shù)以為例46§2.11Catalan數(shù)§2.11Catalan數(shù)47§2.11Catalan數(shù)§2.11Catalan數(shù)48§2.11Catalan數(shù)圖2-11-6§2.11Catalan數(shù)圖2-11-649§2.11Catalan數(shù)

運算用二分樹表示，兩片葉子分別表乘數(shù)和被乘數(shù)，分支點為運算符，如圖圖2-11-5§2.11Catalan數(shù)運算用50§2.11Catalan數(shù)例3.

n個1和n個0組成一2n位的2進制數(shù)，要求從左到右掃描，1的累計數(shù)不小于0的累計數(shù)，試求滿足這條件的數(shù)有多少？

下面介紹兩種算法。解法1.設為這樣所得的數(shù)的個數(shù)。在2n位上填入n個1的方案數(shù)為，不填1的其余§2.11Catalan數(shù)例3.n個1和n個0組成一51§2.11Catalan數(shù)n位自動填以數(shù)0。從中減去不符合要求的方案數(shù)即為所求。不合要求的數(shù)指的是從左而右掃描，出現(xiàn)0的累計數(shù)超過1的累計數(shù)的數(shù)。不合要求的數(shù)的特征是從左而右掃描時，必然在某一奇數(shù)位上首先出現(xiàn)§2.11Catalan數(shù)n位自動填以數(shù)0。從52§2.11Catalan數(shù)個0的累計數(shù)，和m個1的累計數(shù)。此后的位上有個1，個0。如若把后面這部分位，0與1交換，使之成為個0，個1，結果得1個由個0和個1組成的2n位數(shù)，即一個不合要求的數(shù)對應于一個由個0和個1組成的一個排列。§2.11Catalan數(shù)個0的累計數(shù)，和m個1的累計53§2.11Catalan數(shù)反過來，任何一個由個0，個1組成的2n位數(shù)，由于0的個數(shù)多2個，2n是偶數(shù)，故必在某一個奇數(shù)位上出現(xiàn)0的累計數(shù)超過1的累計數(shù)。同樣在后面的部分，令0和1互換，使之成為由n個0和n個1組成的2n位數(shù)。即個0和個1組成的2n位數(shù)，必對應于一個不合要求的數(shù)。§2.11Catalan數(shù)反過來，任何一個由54§2.11Catalan數(shù)用上述方法建立了由個0