stars and bars


所有跟贴·加跟贴·新语丝读书论坛

送交者: jhuang 于 2013-05-09, 21:52:42:

回答: 也出一道排列组合题 由 whoami 于 2013-05-09, 16:21:33:

此类问题叫做stars and bars http://en.wikipedia.org/wiki/Stars_and_bars_%28combinatorics%29

假设7只球颜色分别是Blue,Yellow,Red,Orange,Green,Indigo,Violet。将球拿回来一次,再放回去可以等价于你站在7只装满同一种颜色球的桶前面,拿三次球。从Blue的球桶开始算起,你要么拿球,要么走到下一个(Yellow)的桶前面:

B B B M M M M M M --- 全部拿蓝色的球
M Y M R R M M M M --- 拿一黄俩红的球

M表示走到一只桶。

因为桶是按照顺序排列的,任何一种不考虑次序的允许重复的拿3次球的取法唯一对应上面一种颜色和M的组合。彩球用C来表示,那么 C C C M M M M M M,或者其它任意一种3个C和6个M的组合也唯一对应一种不考虑次序并且允许重复的拿3次球的取法。所以两种问题取法上完全等价,后面一种组合数为C(9,3)。




所有跟贴:


加跟贴

笔名: 密码: 注册笔名请按这里

标题:

内容: (BBCode使用说明