关于catalan数，笔者有很多想说的，也筹划过一段时间了。

catalan数最常见的问题如以下几种：

1.出栈序列

栈作为计算机中一种数据结构，与队列不同，此处不做介绍。

有一进栈序列为1~n的正整数列，问其出栈序列有多少种。

2.whitworth路线

从原点(0,0)沿坐标网走到格点(n,n)的路线，不在直线y=x上方出现的路线称为whitworth路线，后文简称W线，问W线有多少种。

3.排序

在一串由n个0与n个1构成的序列中，前k项和≤k/2恒成立，问该类序列有多少种。

上述三中问题的答案均为标准的catalan数，在本文中以大写英文字母C来表示catalan数。

易得上述三个问题可以构成双射，此处不作赘述，先摆出答案。

斜线上的数均为标准catalan数，如上所述用C(n)来表示。格点上的数用C(i,j)（注意与组合数区分）来表示。定义如下：

C(n,0)=0, C(i,j)=C(i-1,j)+C(i,j-1) (i＞j＞0), C(n)=C(n,n)=C(n,n-1)

那C(i,j)的意义是什么呢，先给出结论，就是从原点(0,0)到格点(i,j)的W线数。

笔者提供一种常见证明如下：

该类问题还可以使用母函数

以下引用两例：

eg1.甲、乙打乒乓球，最后甲以11：6获胜，求在比赛过程中甲一直领先的比分序列的个数。

易证其为C(11,6)，过于简单，此处省略证明。

eg2.求1,2,⋯,n的排列(a₁,a₂,⋯,aₙ)的个数，使得不存在1≤i<j<k≤n，满足ai<aj<ak。

留给读者自行证明。