Catalan数

缘起

BAT面试中的算法中经常考察Catalan数. 下面研究一下

分析

catalan数诞生的背景有如下两个

  1. 凸多边形的三角形分割问题,即一个由n+1条边组成的凸n+1边形P(必须是凸的,否则如果是凹的话,连线都在P的外面),n-2条不相交的对角线将把P分成n-1个三角形,问不同的分割方式有多少种?算法是添加两条辅助线,设v0,…,vn是P的n+1个顶点,则对于k=1,…,n-1,添加v0vk与vnvk两条边,则P被分成P1(凸k+1边形),P2(凸n-k+1边形)以及一个三角形,则根据加法原理,设hn是P(凸n+1边形)的划分方法(n>=2),则hn=\Sigma_{k=1}^{k=n-1}hk*h_{n-k}(n>=2),其中h1=1(虽然h1对应与2边形没意义,但是规定h1=1可以导出正确的h2=1),构造母函数,g(x)=h1x+h2x^2+h3x^3+…(无穷级数)则g^2(x)=g(x)-x,则解出g(x)再泰勒展开,便可以得到hn=C_{n-1}
  2. n个1与n个-1组成的序列a1…,a_{2n},则满足其部分和序列全部非负的排列数目是Cn,经典的题目就是电影院找零问题.算法是反射原理,设An是满足条件的排列种数,Un是不满足条件的排列种数,则An+Un=C(n,2n),则计算Un是关键,对于不满足条件的一个序列,一定存在第一个k使得a1+..+ak=0,但是a_{k+1}=-1,那么我们就将a1,…,a_{k+1}中的-1变成1,1变成-1,但是a_{k+2},…,an不变.则序列就变成了一个含有n+1个1,n-1个-1的序列,并且这种变换是单射.反之,对于每个含有n+1个1,n-1个-1的序列,一定存在某个k使得前k个元素和为0,但是第k+1个元素是1,则将前k+1个元素-1变1,1变-1,而之后的元素不变,则得到的序列就是含有n个1,n个-1的序列,但是不满足要求.则Un=C(n+1,2n),从而An=C(n,2n)-Un=Cn.

其中背景2是高中数学在排列组合那一章学过的著名的”电影院排队买票找零”问题. 而且它极容易变形为进栈出栈问题——n次push、n次pop，操作，没有任何一次非法. 问有几种可能.

知道了catalan数的计算公式，求解就极为简单了——使用递推公式即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <vector>
#pragma warning(disable:4996)

//#define LOCAL
using namespace std;
typedef long long LL;

LL catalan(int n) // 计算n阶catalan数
{
	LL ret = 1;
	int i = 1;
	while(i<=n)
	{
		ret = (4*i-2)*ret/(i+1);
		i++;
	}
	return ret;
}

int main()
{
#ifdef LOCAL
	ifstream fin("d:\\data.in");
	cin.rdbuf(fin.rdbuf());
#endif
	// 3814986502092304
	printf("%lld\n", catalan(30));
	return 0;
}