Catalan 卡特蘭數

卡特蘭數又稱卡塔蘭數，英文名Catalan number，是組合數學中一個常出現在各種計數問題中出現的數列。以比利時的數學家歐仁·查理·卡塔蘭 (1814–1894)的名字來命名，其前幾項為 : 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, …

Catalan的遞推關系

令 h ( 0 ) = 1 , h ( 1 ) = 1 h(0)=1,h(1)=1 h(0)=1,h(1)=1，catalan數滿足遞推式

h ( n ) = h ( 0 ) ∗ h ( n − 1 ) + h ( 1 ) ∗ h ( n − 2 ) + . . . + h ( n − 1 ) ∗ h ( 0 ) ( n > = 2 ) h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)*h(0) (n>=2) h(n)=h(0)∗h(n−1)+h(1)∗h(n−2)+...+h(n−1)∗h(0)(n>=2)

cat[0]=cat[1]=1;
for(int i=2;i<=n;++i)
for(int j=0;j<i;++j)
cat[i]+=cat[j]*cat[i-j-1];
           

遞推複雜度為 O ( n 2 ) O(n^2) O(n2)

令 h ( 0 ) = 1 , h ( 1 ) = 1 h(0)=1,h(1)=1 h(0)=1,h(1)=1

則有 h ( n ) = h ( n − 1 ) ∗ ( 4 ∗ n − 2 ) / ( n + 1 ) h(n)=h(n-1)*(4*n-2)/(n+1) h(n)=h(n−1)∗(4∗n−2)/(n+1)

cat[0]=cat[1]=1;
for(int i=2;i<=n;++i)
cat[i]=cat[i-1]*(4*i-2)/(i+1);
           

遞推複雜度為 O ( n ) O(n) O(n)

h ( n ) = C 2 n n / ( n + 1 ) h(n)=C_{2n}^n/(n+1) h(n)=C2nn​/(n+1)

或

h ( n ) = C 2 n n − C 2 n n − 1 h(n)=C_{2n}^n-C_{2n}^{n-1} h(n)=C2nn​−C2nn−1​

代碼就不填了= =

Catalan的應用

入棧出棧

Q：給定n個數，進棧的序列是1,2,3,4,……n，有多少個不同的出棧次序

A：

h(n)表示個數為n的序列的出棧次序種數

假設最後出棧的元素是k

在k入棧前k前面的元素都出棧，是以有 h ( k − 1 ) h(k-1) h(k−1)種

k後面的元素在k之前出棧，是以有 h ( n − k ) h(n-k) h(n−k)種

運用乘法原理有 h ( n ) = h ( k − 1 ) ∗ h ( n − k ) h(n)=h(k-1)*h(n-k) h(n)=h(k−1)∗h(n−k)

由于k可以取1到n，根據加法原理得

h ( n ) = h ( 0 ) ∗ h ( n − 1 ) + h ( 1 ) ∗ h ( n − 2 ) + . . . + h ( n − 1 ) ∗ h ( 0 ) ( n > = 2 ) h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)*h(0) (n>=2) h(n)=h(0)∗h(n−1)+h(1)∗h(n−2)+...+h(n−1)∗h(0)(n>=2)

也就是卡特蘭數得遞推式

平衡括号

Q：有n個左括号，n個右括号，總共2*n個括号，有多少種合法比對方式，

A:

将左括号視為入棧，右括号視為出棧

那麼這個問題就轉化成了将n個左括号入棧，有多少種合法出棧次序得問題

也就是上面的出棧入棧問題，答案就是 h ( n ) h(n) h(n)

二叉樹的形态

Q：有n個結點得二叉樹，可以有多少種不同形态

A:

以h(n)表示有n個節點的二叉樹可以有得不同形态數

假設其根得左子樹有k個節點

那麼其左子樹有 h ( k ) h(k) h(k)個不同形态，右子樹有 h ( n − k − 1 ) h(n-k-1) h(n−k−1)個不同形态

根據乘法原理 h ( n ) = h ( k ) ∗ h ( n − k − 1 ) h(n)=h(k)*h(n-k-1) h(n)=h(k)∗h(n−k−1)

k可以取0-n

則有 h ( n ) = h ( 0 ) ∗ h ( n − 1 ) + h ( 1 ) ∗ h ( n − 2 ) + . . . + h ( n − 1 ) ∗ h ( 0 ) ( n > = 2 ) h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)*h(0) (n>=2) h(n)=h(0)∗h(n−1)+h(1)∗h(n−2)+...+h(n−1)∗h(0)(n>=2)

滿足卡特蘭數遞推式

走方格

Q：一個 n*n 的方格，從左下角走到右上角，隻能向右和向上走，但是不能繞過左下角和右上角确定的對角線，問有多少種走法？

A：

要走到右上角，需要向右走n布，向上走n步

向右走看作進棧，向左走看作出棧，本質就是n個數出棧次序的問題

還有很多應用

待更。。。。

Catalan數例題

題目背景

盛況空前的足球賽即将舉行。球賽門票售票處排起了球迷購票長龍。

按售票處規定，每位購票者限購一張門票，且每張票售價為50元。在排成長龍的球迷中有N個人手持面值50元的錢币，另有N個人手持面值100元的錢币。假設售票處在開始售票時沒有零錢。試問這2N個球迷有多少種排隊方式可使售票處不緻出現找不出錢的尴尬局面。

題目描述

例如當n=2是，用A表示手持50元面值的球迷，用B表示手持100元錢的球迷。則最多可以得到以下兩組不同的排隊方式，使售票員不至于找不出錢。

第一種:A A B B

第二種:A B A B

對于給定的n (0≤n≤20),計算2N個球迷有多少種排隊方式，可以使售票處不至于找不出錢。

輸入格式：

一個整數，代表N的值

輸出格式：

一個整數，表示方案數

分析

一個A買票後售票處就積累50元錢

一個B買票需要售票處找零50元錢

說明在一個B買票前至少需要一個A買過票

那麼我們就可以将A看作左括号，B看作右括号

問題就是要求合法得括号比對，即Catalan數

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
typedef long long ll;

int n;
ll cat[50];

int main()
{
    scanf("%d",&n);
    cat[0]=cat[1]=1;
    
    for(int i=2;i<=n;++i)
    cat[i]=cat[i-1]*(4*i-2)/(i+1);
    
    cout<<cat[n];
    return 0;
}