catalan数证明
定理：n个1 和n个-1 构成的2n项a1,a2….a2n ,其部分和
满足a1 + a2 + …aK >= 0 (k = 1 2 …2n ) 这个的条件的个数 为
证明：令An 为其中可以接受的系列Bn 为不可接受的系列
那么An + Bn = ![clip_image002[4]](http://up.2cto.com/2011/0723/20110723023413362.gif "clip_image002[4]"){kind=small}
.An 是我们要求的，我们可以通过求出Bn来得到An 。
我们假设存在 一个最小的K 使得a1 + a2 +…+ak 为负，那么 可以肯定a1+…+ak-1 = 0,且ak = -1.k 为奇整数。
对于每一种不符合条件的序列a1 + a2 +…+ak +…+a2n 将a1 a2 ak 都用-a1 –a2 –ak 代替，那么新的数列
a1’a2’ …a2n’ 就有n+1 个+1 和n-1 个 –1 。即每一种 不符合条件的 数列经过上述过程都将变为
n+1 个+1 和n-1 个 –1 的排列 。那么现在要证明n+1 个+1 和n-1 个 –1 的排列数== Bn
n+1 个+1 和n-1 个 –1 的排列 肯定存在一个 最小的k 使得a1 + a2 + …aK < 0 而将这部分也用-a1 –a2 –ak 代替 ，也就成为了n个1 和n个-1 构成的2n项a1,a2….a2n 而Bn的排列就好求了
![clip_image002[6]](http://up.2cto.com/2011/0723/20110723023414630.gif "clip_image002[6]"){kind=small}
==》![clip_image002[8]](http://up.2cto.com/2011/0723/20110723023414641.gif "clip_image002[8]"){kind=small}
应用： 有2n个人要去剧场，入场5角，有n个人有1元，n个人有5角，剧场的卖票处刚开始没有零钱，那么存在多少种队列方式。
粗体的证明 ，我感觉有些牵强，呵呵 大家有好的方法，请指正。
- 上一篇：如何修改WAMP中mysql默认空密码
- 下一篇：JAVA常见异常
相关文章
图文推荐
- 文章
- 推荐
- 热门新闻