前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >卡特兰数扩展

卡特兰数扩展

作者头像
Gxjun
发布2018-03-21 12:40:19
5970
发布2018-03-21 12:40:19
举报
文章被收录于专栏:ml

对于排队买票问题的一些说法.....

  假若有M+ N人去买票,n人手持5元,m人手持10元,而售货阿姨没有零钱,问有多少种方法能使大家都买到票。

其中m<=n.M+N<=10;(初次在HBUOJ上看到.....)

    (1) 有已知条件 m<=n; 我们就不需要去考虑m>n时的情况啦!但是即便去考虑的话,这种情况依旧为零.

因为m>n时,你不管这么排列都是不可能找开的...m*10-n*5>m*5----所以这个条件只是为我们减少了一小部分的时间.

    (2) m<=n时,我们发现对于随意的第K个位置出现的10多余5的时候不可能的情况 我们都可以找到

 对应的可以满足的情况 。

  比如  10 5 10 10 5  5  我们只需将后面的10 和5 换一下就行, 5 10 5 5 10 10 。

再比如 10 5 10 5 5 我们只需将  5 10 5 5 10 (m<=n)

       那,我们总的分配情况为C(m+n,m) ,然后不能的情况为C(m+n,n+1)(m+1>n)

 最后加上分配排列就是(C(m+n,m)-C(m+n,n+1))*m!*n! 

化解之后为: (m+1-n)*(m+n)!/(m+1);

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2013-08-04 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档