回 帖 发 新 帖 刷新版面

主题:[讨论]数学题

请教一个问题,是关于排列组合的。

有一个n位长的字符串,其中每个字符可能是某字符集的一个,该字符集共有m种基本字符(设m>=n),那么这样的字符串的可能排列是m的n次方,没有一个字符重复这样的字符串共有m!/(m-n)!个,这都对吧?

我的问题是,如果把aaab和aaba,abaa,baaa看作是重复的字符串,但这样的字符串允许单个字符的重复,比如有两个以上的a,就象aaab一样是允许的,去除掉我所说的重复字符串之后应该有多少种组合呢?好象不是再除以n这么简单。
再比如1112,1121,1211,2111这四种是重复的,只算任一种即可,
1122,1212,2112,1221,2121,2211这六种也是重复的。

[fly]谢谢![/fly]

回复列表 (共2个回复)

沙发

我知道了,答案是C(m+n-1,n),找了本信息学奥赛的书找到了答案,这门学科好难啊.

板凳

其实:
有m个数:x1+x2+x3+......+xm=n的非负整数解的个数
x1+x2+......+xn=m的非负整数解==x1+x2+......+xn=m+n的整数解
再不明白联系我EMAIL

我来回复

您尚未登录,请登录后再回复。点此登录或注册