今天我要讲的东西是关于排队的问题,实际上这个问题是算法课的老师给我们出的问题,到时候会有测验。问题是这样的,有2n个人,排两排,从矮到高,第二排的要比第一排所对应的那个人高,问有多少种排列方式?...以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)的名字来命名,其前几项为(从第零项开始) : 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796,...(S的个数为n)显然有c(2n, n)个含S,X各n个的序列,剩下的是计算不允许的序列数(它包含正确个数的S和X,但是违背其它条件)。...在任何不允许的序列中,定出使得X的个数超过S的个数的第一个X的位置。然后在导致并包括这个X的部分序列中,以S代替所有的X并以X代表所有的S。结果是一个有n+1个S和n-1个X的序列。...反过来,对后一种类型的每个序列,我们都能逆转这个过程,而且找出导致它的前一种类型的不允许序列。例如XXSXSSSXXSSS必然来自SSXSXXXXXSSS。