卡特兰数

卡特兰数是在组合数学中常用到的知识点,应用也很广泛

公式

规定h(0) = 1,满足递推式$h(n) = h(0)*h(n-1)+h(1)*h(n-2)+\cdots+h(n-1)*h(0)\ \ (n>0)$

解为$h(n) = \frac{C_{2n}^n}{n+1}\ \ (n\geqslant 0)$

另类解$h(n)=C_{2n}^n-C_{2n}^{n+1}\ \ (n\geqslant 0)$

应用

括号匹配

卡特兰数往往应用于这样的场景:问题可以一分为二且两边所构成的子问题也满足原问题的要求,比如最常见的有效括号问题(左右括号构成一对有效括号),对于一个有效括号(共n个括号,n/2对),一定满足从某一个点i分开的两部分均构成的是有效括号,而第一部分的i/2对有效括号有h(i/2)种组合方式,第二部分的n/2-i/2-1对有h(n/2-i/2-1)种组合方式,如果令i = 2k,那么总组合数$S=h(k)*h(n/2-k-1)\ \ (k\in [0, n/2-1])$,易知,该数就是卡特兰数h(n/2)。

找零问题

有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票,另外n人只有10元钞票,剧院无其它钞票,问有多少中方法使得只要有10元的人买票,售票处就有5元的钞票找零?(将持5元者到达视作将5元入栈,持10元者到达视作使栈中某5元出栈)

其实等同于括号匹配的问题,一个有10元钞票的人前面必须要能匹配一个有5元钞票的人,即可看做左括号和右括号

出栈次序问题

一个栈(无穷大)的进栈序列为1,2,3,…,n,有多少个不同的出栈序列

卡特兰数h(n)

2n+1个节点构造满二叉树的方案数

卡特兰数h(n)

发表评论

电子邮件地址不会被公开。