亚马逊校园招聘在线笔试题（三）-卡特兰数

问题描述：

  12个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种?

问题分析:

  我们先把这12个人从低到高排列,然后,选择6个人排在第一排,那么剩下的6个肯定是在第二排.用0表示对应的人在第一排,用1表示对应的人在第二排,那么含有6个0,6个1的序列,就对应一种方案.比如000000111111就对应着，第一排:0 1 2 3 4 5，第二排:6 7 8 9 10 11。010101010101就对应着，第一排:0 2 4 6 8 10，第二排:1 3 5 7 9 11问题转换为,这样的满足条件的01序列有多少个。
  观察1的出现,我们考虑这一个出现能不能放在第二排,显然,在这个1之前出现的那些0,1对应的人，要么是在这个1左边,要么是在这个1前面.而肯定要有一个0的,在这个1前面,统计在这个1之前的0和1的个数.也就是要求,0的个数大于1的个数.如果把0看成入栈操作,1看成出栈操作,就是说给定6个元素,合法的入栈出栈序列有多少个.其通项是c(2n, n)/(n+1)。

原理

  令h(0)=1,h(1)=1，catalan数满足递推式[1]：

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

  递推关系的解为：

  h(n)=C(2n,n)/(n+1) (n=0,1,2,...)

卡特兰数的应用

  实质上都是递推等式的应用