付翔的专栏
在鄙视中成长 记录成长的点滴
posts - 106,  comments - 32,  trackbacks - 0

定理:n个1 和n个-1 构成的2n项 a1,a2….a2n ,其部分和

满足 a1 + a2 + …aK >= 0 (k = 1 2 … 2n ) 这个的条件的个数 为

clip_image002

证明:令An 为其中可以接受的系列Bn 为不可接受的系列

那么 An + Bn = clip_image002[4] .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] 

==》clip_image002[8] 

应用: 有2n个人要去剧场,入场5角,有n个人有1元,n个人有5角,剧场的卖票处刚开始没有零钱,那么存在多少种队列方式。

粗体的证明 ,我感觉有些牵强,呵呵 大家有好的方法,请指正。

我独立博客地址 http://www.fuxiang90.me/?p=286

posted on 2011-07-22 18:05 付翔 阅读(2300) 评论(1)  编辑 收藏 引用 所属分类: ACM 数据结构

FeedBack:
# re: catalan 数 证明
2011-07-22 23:01 | 千暮(zblc)
Catalan似乎在《离散数学与组合数学》里面证明的很清楚了  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理



<2010年10月>
262728293012
3456789
10111213141516
17181920212223
24252627282930
31123456

常用链接

留言簿(2)

随笔分类

随笔档案

文章分类

文章档案

CSDN - 我的blog地址

博客

搜索

  •  

最新评论

阅读排行榜

评论排行榜