该递推关系的解为:
常见公式:
卡特兰数列(下标从
开始):
2n
个人排成一行进入剧场。入场费 5 元。其中只有n
个人有一张 5 元钞票,另外n
人只有 10 元钞票,剧院无其它钞票,问有多少中方法使得只要有 10 元的人买票,售票处就有 5 元的钞票找零?n
个街区和以东n
个街区处工作。每天她走2n
个街区去上班。如果他从不穿越(但可以碰到)从家到办公室的对角线,那么有多少条可能的道路?2n
个点,将这些点成对连接起来使得所得到的n
条线段不相交的方法数?1,2,3, \cdots ,n
有多少个不同的出栈序列?n
个结点可够造多少个不同的二叉树?n
个不同的数依次进栈,求不同的出栈结果的种数?n
个+1
和n
个-1
构成2n
项a_1,a_2, \cdots ,a_{2n}
,其部分和满足a_1+a_2+ \cdots +a_k \geq 0(k=1,2,3, \cdots ,2n)
对与n
该数列为?非降路径是指只能向上或向右走的路径。
从
到
的非降路径数等于
个
和
个
的排列数,即
。
从
到
的除端点外不接触直线
的非降路径数:
先考虑
下方的路径,都是从
出发,经过
及
到
,可以看做是
到
不接触
的非降路径数。
所有的的非降路径有
条。对于这里面任意一条接触了
的路径,可以把它最后离开这条线的点到
之间的部分关于
对称变换,就得到从
到
的一条非降路径。反之也成立。从而
下方的非降路径数是
。根据对称性可知所求答案为
。
从
到
的除端点外不穿过直线
的非降路径数:
用类似的方法可以得到: