?

?

? ?

?

?

?

??

???我們結合一個題目具體看看Catalan數的應用。(Pr0blem source:hdu2067)? ?

?

Problem Description 小兔的叔叔從外面旅游回來給她帶來了一個禮物，小兔高興地跑回自己的房間，拆開一看是一個棋盤，小兔有所失望。不過沒過幾天發現了棋盤的好玩之處。從起點(0，0)走到終點(n,n)的最短路徑數是C(2n,n),現在小兔又想如果不穿越對角線(但可接觸對角線上的格點)，這樣的路徑數有多少?小兔想了很長時間都沒想出來，現在想請你幫助小兔解決這個問題，對于你來說應該不難吧!
Q3:1~n按照次序進棧，那么有多少種不同的出棧方案？ 這里我們用二進制的思維去看這個問題。n個數字中，每個數字對應兩種操作，入棧(記為1)，出棧(記為0)，那么所有的情況可以看成n個1和n個0的排列情況，即往2n位的二進制數中填充1、0，我們可以得到總方案數——C(2n,n),但是考慮到每個數字必須先入棧后出棧，勢必存在不符合情況的組合，現在我們就要找到不符合情況的數量，然后再用總數量C(2n,n)減掉即可。 在不符合先入后出條件的情況中，勢必會在二進制數的某個奇數位前(包含該奇數位)，出現了m+1個0和m個1，此時該奇數位后(不包含該奇數位)，有n-m-1個0和n-m個1。 ? 此時我們再想這樣一個模型，2n位二進制數含有n+1個0和n-1個1，由于這個2n位二進制數必定存在偶數位前(包含該偶數位)，0比1多2，呢么就必定存在奇數位前(包含該奇數位)，出現了m+1個0，m個1，這與上面的情況是對應的。而在這種情況下，該奇數位以后(不含該奇數位)有n-m-1個1和n-m個0，這里將1和0對調，剛好個上面的情況吻合起來，而方案數卻沒有改變，因此我們得出結論——不符合的方案數是C(2n,n-1)。 ? 通過化簡整理，出棧的總順序為C(2n,n) - C(2n,n-1) = (1/n+1)*C(2n,n)，這同時也是Catalan數遞推式的解。
???不妨來看一道關于出入棧方案數的題目(Problem source:hdu1023) ? Problem Description As we all know the Train Problem I, the boss of the Ignatius Train Station want to know if all the trains come in strict-increasing order, how many orders that all the trains can get out of the railway.
??? 題目大意：就是n輛貨車，他們進棧的順序有多少種。 ?? 數理分析：這里軌道只有一條，這條軌道就模擬了Q3模型中的棧，而這里想求的其實就是一個順序入棧而后不同次序出棧的方案數。 ? 編程實現：組合數學中給出的計數公式隨著n的擴大，數值一般會爆掉c/c++中的數據類型，于是這里為了解決大數問題，我們用JAVA的寫法來實現。 參考代碼如下。? import java.io.*; import java.util.*; import java.math.BigInteger;public class Main {public static void main(String args[]){ BigInteger[] a = new BigInteger[101];a[0] = BigInteger.ZERO;a[1] = BigInteger.valueOf(1);for(int i = 2; i <= 100; ++i)a[i] = a[i - 1].multiply(BigInteger.valueOf(4 * i - 2)).divide(BigInteger.valueOf(i+1));Scanner in = new Scanner(System.in);int n;while(in.hasNext()){n = in.nextInt();System.out.println(a[n]);}} }

?

?

?

????Q4:給定一個數n，在一個圓上我們找到2n個點，然后成對的連接兩個點，我們可以得到多少種方案數？ 既然在圓上有2n個點，那么我們可以找到一條直線將圓分成兩部分A、B，這兩各區域上面分別有n個點，我們任選一個區域A，任選一個點i，然后連接點i和區域B中的任意一個點j，此時圓又被分成區域C和區域D，我們這里就可以得到Q1中的遞推式——h(n) = ∑h(k)h(n-k)。也就是說，對于2n個點在圓上兩兩連接，形成不相交線段的方案數，等于凸n+1邊形分割成三角形的方案數，都是第n個Catalan數(根據其定義，Catalan數是有第0個的，即C[0] = 0)。 知道了這個模型本質上也是求解Catalan數，我們就來看一個相關的問題。(Problem source:hdu1134) Problem Description This is a small but ancient game. You are supposed to write down the numbers 1, 2, 3, ... , 2n - 1, 2n consecutively in clockwise order on the ground to form a circle, and then, to draw some straight line segments to connect them into number pairs. Every number must be connected to exactly one another. And, no two segments are allowed to intersect.
It's still a simple game, isn't it? But after you've written down the 2n numbers, can you tell me in how many different ways can you connect the numbers into pairs? Life is harder, right? ??可以看到，這里的問題是和Q4一模一樣的問題，這里只需編程實現Catalan數即可。 參考代碼在上面給出代碼的基礎上進行稍稍的改動即可。
? Q5：給點節點數n，我們用這n個節點能夠生成多少個二叉樹？ ??針對這個問題，我們還是基于上文一開始給出Catalan數的思維角度(Q1分割n邊形的問題)，同樣，為了記數的方便和最終結論的他統一，這里我們來分析n+1個節點能夠生成多少個二叉樹。 ??既然是生成二叉樹，其必含有根節點、左子樹、右子樹。這里除去根節點，左子樹和右子樹一共還有n個節點，我們假設左子樹有k個節點，那么右子樹就有n-k個節點，這里我們再假設h(n)表示n各節點對應的方案數，那么這種情況下二叉樹不同的種類就有h(k) * h(n - k)，那么再依次遍歷k的值進行累加，我們就得到了遞推式——h(n+1) = ∑h(k)h(n-k)，這里k的范圍是[0,n]。 ? ? 這其實又回到了Q1所進行的推導。 ? 最終我們可以得出結論，凸n+1邊形分隔成三角形且對角線不相交的方案數，和n+1個節點形成二叉樹的種類數是一樣的，都對應第n個Catalan數。
???讓我們找一道相關的題目實踐一下我們的結論。(Problem source:hdu1130)? Problem Description A binary search tree is a binary tree with root k such that any node v reachable from its left has label (v) <label (k) and any node w reachable from its right has label (w) > label (k). It is a search structure which can find a node with label x in O(n log n) average time, where n is the size of the tree (number of vertices).
Given a number n, can you tell how many different binary search trees may be constructed with a set of numbers of size n such that each element of the set will be associated to the label of exactly one node in a binary search tree? 可以看到，這里的問題是和Q5一模一樣的問題，這里只需編程實現Catalan數即可。 參考代碼在上面給出代碼是一致的。
? ? Q6：小明住在市中心北n個街區，東n個街區，那么小明要穿越街區到市中心上班，有多少條路可以走？ 仔細的讀者可能已經發現，這道問題是和Q1下給出的問題是一模一樣的，在上文中我們用動態規劃的思想來找到二者的聯系，而在這里，我們再用組合思維來分析它。 前奏一樣，我們依然通過一條對角線將整個矩形劃分成對稱的了兩塊。這里我們把向左走記為+1，向下走記為-1，并且選擇矩形的左上半區域。問題轉換成n個+1和n個-1能夠形成多少種序列。 ? 由于不能越過對角線，即在滿足要求的序列a1a2a3……ai……an中，必須有任意的k∈[1,n]，是的a1+a2+a3……+ak >= 0。 ? 至此我們發現，問題其實回到了出入棧順序的問題，為了語言的簡潔，這里不再重復證明。?? 那么讓我們結合一個具體的問題。(Problem source : hdu 4165)??? Problem Description Aunt Lizzie takes half a pill of a certain medicine every day. She starts with a bottle that contains N pills.
On the first day, she removes a random pill, breaks it in two halves, takes one half and puts the other half back into the bottle.
On subsequent days, she removes a random piece (which can be either a whole pill or half a pill) from the bottle. If it is half a pill, she takes it. If it is a whole pill, she takes one half and puts the other half back into the bottle.
In how many ways can she empty the bottle? We represent the sequence of pills removed from the bottle in the course of 2N days as a string, where the i-th character is W if a whole pill was chosen on the i-th day, and H if a half pill was chosen (0 <= i < 2N). How many different valid strings are there that empty the bottle? 題目大意：一個藥罐子里有n片藥，現在你從中取藥，拿到整片(記作W)，掰成兩半，一半放回去，如果拿到半片(記作H)，直接拿出來，需要我們計算的是直到把藥罐里的藥片全部拿走，有多少種方案。 ? 數理分析：經過對題意的抽象，我們很容易認識到，實際上題目就是給出n個W和n個H，讓我們計算長度為2n的可行序列數。 ? 這里就回到了Q6的模型，或者說是出入棧順序的模型，這里便不再累述。 參考代碼也是同上然后做一點小小改動即可。
??我們再來看一道關于Catalan數變形應用的問題。(Problem source : hdu 3723)??? Problem Description A delta wave is a high amplitude brain wave in humans with a frequency of 1 – 4 hertz which can be recorded with an electroencephalogram (EEG) and is usually associated with slow-wave sleep (SWS). -- from Wikipedia
The researchers have discovered a new kind of species called "otaku", whose brain waves are rather strange. The delta wave of an otaku's brain can be approximated by a polygonal line in the 2D coordinate system. The line is a route from point (0, 0) to (N, 0), and it is allowed to move only to the right (up, down or straight) at every step. And during the whole moving, it is not allowed to dip below the y = 0 axis.
For example, there are the 9 kinds of delta waves for N = 4:Given N, you are requested to find out how many kinds of different delta waves of otaku. 題目大意：在如圖所示的坐標紙當中，給定一個數字n，問你從(0,0)到達(n,0)有多少條路可以走，每次移動x必須+1，y可以選擇+1、-1、0。 數理分析：可以看到，這道題終點是(n,0)，這就表明這n次操作中，對y的+1和-1操作數量是相同的，這就讓我們聯想到了上文中關于Catalan數的模型，無論是穿越街區、還是出入棧順序的問題，都可以拿過來盡心對比。 ? 但是僅僅知道了和Catalan數有關還是不行的，假設+1有k個，那么我們首先要做的就是在n步操作中選出2k個位置以填充+1和-1，我們這里假設序列T[n]是記錄答案的序列，這里T[n] = C(n,2k) * Catalan[k]。考慮到n的取值，我們不好單獨計算前面的組合數，所以我們將T[n]看成一個整體，通過數學推導看是否能得出新的齊次遞推式子。 推導如下。 ?

? ? 通過推導我們可以看到，我們得到了新的齊次遞推式 import java.math.BigInteger; import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);BigInteger mod = BigInteger.TEN.pow(100);BigInteger sum = new BigInteger("0");BigInteger t = new BigInteger("0");while (sc.hasNext()) {int n = sc.nextInt();sum = BigInteger.ONE;t = BigInteger.ONE;for(int k = 1; k + k <= n; k++) {t = t.multiply(BigInteger.valueOf((n-2*k+1)*(n-2*k+2))).divide(BigInteger.valueOf(k*(k+1)));sum = sum.add(t);}System.out.println(sum.mod(mod));}} }

?

??我們繼續來看一道有關Catalan數的問題(Prblem sourece:hdu 1133) Problem Description The "Harry Potter and the Goblet of Fire" will be on show in the next few days. As a crazy fan of Harry Potter, you will go to the cinema and have the first sight, won’t you?
Suppose the cinema only has one ticket-office and the price for per-ticket is 50 dollars. The queue for buying the tickets is consisted of m + n persons (m persons each only has the 50-dollar bill and n persons each only has the 100-dollar bill).
Now the problem for you is to calculate the number of different ways of the queue that the buying process won't be stopped from the first person till the last person. Note: initially the ticket-office has no money.
The buying process will be stopped on the occasion that the ticket-office has no 50-dollar bill but the first person of the queue only has the 100-dollar bill.
??題目大意：就是有m個人拿50元，n個人拿100元，他們通過自動取票機買一張50元的票，但是你這個取票機是空的，問你有多少種方案，是的這m+n個人可以都得到票。 ? ? 數理分析：如果m<n,是沒有符合要求的方案數的，這顯而易見。如果這里是2n個人，n個50塊n個100塊，那么這就是很典型誒對Catalan數的模型了，它的分析思路很類似關于出入棧順序的模型。但是這里，還是有一定的區別的，但是我們可以用相同的思想進行分析。 這里我們依然往出入棧順序的那個模型上靠攏。我們是用間接法，符合要求的方案數= 總方案數量 - 不符要求方案數。 這里對于總方案數很好說，C(m+n,m)orC(m+n,n)都是可以的。 ? 對于不符合要求的方案數，我們就采取和分析出入棧順序一樣的方法(詳情可以往上翻)，我們將50元和100元分別轉化成1、0，這樣我們就相當于計算不同種數的01序列，那么在m+n位的01序列中，我們分析不符合要求的情況，其一定在k位，之前出現了r位1和r+1位0，那么在剩下的m+n-k位中，則有m-r個1和n-r-1個0，這里我們將m+n-k位中的0換成1,1換成0，則相當于在m+n位二進制數中填充m+1個0，這種情況下的方案數是等價于變化(后m+n-k位的0->1,1->0)之前的方案數，即不符合要求的方案數。 考慮到實際情況，每個人是不同的，所以需要在分別再乘以m和n的階乘。 ? 通過以上分析，我們得知，符合方案數的的計算公式——(C(m+n,m) - C(m+n,m+1))*m!*n!。 ? 接下來便是推導出便于編程實現的式子(展開組合公式)。 ? 化簡的最終結果——（m+n）！*（m-n+1）/（m+1）。 參考代碼如下。?? import java.util.*; import java.math.BigInteger; public class Main{public static void main(String[] args){int a,b;Scanner in=new Scanner(System.in);int cnt=0;while(in.hasNext()){cnt++;a=in.nextInt();b=in.nextInt();BigInteger ans=BigInteger.ONE;if(a==0&&b==0)break;if(a<b) ans=BigInteger.ZERO;else {for(int i=1;i<=a+b;i++){ans=ans.multiply(BigInteger.valueOf(i));}int mpl=(a-b+1);int dvd=(a+1);ans=ans.multiply(BigInteger.valueOf(mpl));ans=ans.divide(BigInteger.valueOf(dvd));}System.out.println("Test #"+cnt+":");System.out.println(ans);}} }

?

參考系：《組合數學》Richard?

轉載于:https://www.cnblogs.com/rhythmic/p/5472575.html

總結

以上是生活随笔為你收集整理的《组合数学》——卡特兰数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。