卡特兰数背后的思考

我们从一道面试题引入：

题目：
题目： 有20个人去看电影，电影票50元。其中只有10个人有50元钱，另外10个人都只有一张面值100元的纸币，电影院没有其他钞票可以找零，问有多少种找零的方法？

解析：
这20个人不是一起的
所以第一个人必须是50元
要想后续每次都找的开，那么在每一次收钱的时候，收银员已经收过的50元的个数要大于已经收过的100元的个数。

从(0,0)开始记录收银员已经收银的状态，左边代表50元的个数，右边代表100元的个数，用**（a,b）记录，则a>=b**

第一次必须为(1,0)
第二次可以为(2,0)也可以为(1,1)
第三次：(3,0) 或者 (2,1)
以此类推，我们可以用画图的方法来表示：

这里以5个50，5个100举例：

用数字将到达每一种状态时的可能性标出，则最后可以看出，有42种可能到达的方法。

然后我们发现1,2，5,14，。。。是卡特兰数

卡特兰数：
1—>1
2—>2
3—>5
4—>14
5—>42
6—>132
7—>429
8—>1430
9—>4862
10—>16796

公式:C(2n,n)/(n+1)=C(10,20)/11=16796