disccusion of 组合题 from WXC

QFT · 发表于 2005-11-28 06:13:11

original question is as following,

"问题是有多少可能的组合。

如果我们有30个人, 我们要分成10个小组, 各个小组有至少2个人"

As constant said "好象只能递推"

我们来考虑一般的情况：N 个人分成 M 组，每组至少 L 个人。假设有 T(N, M; L) 种可能的组合。

有如下的递推关系式,

T(N+1, M; L) = M * T(N, M; L) + C(N, L-1) * T(N+1-L, M-1; L)

C(N, L-1) 代表组合数.

第一项 M * T(N, M; L) 表示一个给定的人所在的组不少于 N+1 个人的可能组合个数.

第二项 C(N, L-1) * T(N+1-L, M-1; L) 表示这个给定的人所在的组正好 N 个人的可能组合个数.

对于 L=1, 我们有 T(N+1, M) = M * T(N, M) + T(N, M-1) .

对于这种情况, 我们利用容斥原理可以得到一个级数表示.

先假定这M各组是可分辨的, 依次记为第一组, 第二组, 等等.

那么

第一组至少有一个人的可能组合有 M^N - (M-1)^N, 记为 S(1)

第一或第二组至少有一个人的可能组合有 M^N - (M-2)^N, 记为 S(2)

明显 S(K) = M^N - (M-K)^N

容斥原理给出

U(N, M) = M * S(1) - C(M, 2) * S(2) + C(M, 3) * S(3) + ... + (-1)^(M+1) * S(M)

稍加整理得到

U(N, M) = sum (-1)^K * C(M, K) * (M-K)^N, K = 0 .. M-1

如果考虑这M各组是不可分辨的, 需要除以 M!

这样 T(N, M) = U(N, M)/M!

可以验证T(N, M)满足前面的递推关系.

如果L>=2, 需要利用前面的递推关系, 编程计算.

寒潭清 · 发表于 2005-11-28 15:57:37

谢谢QFT,请接受我的花

QFT · 发表于 2005-11-28 21:32:13

谢谢清儿的花

大头羊 · 发表于 2005-11-30 00:53:10

这些小组有序还是无序？

QFT · 发表于 2005-11-30 05:08:37

这些小组是无序的。

对于每个小组至少有一个人这种情况，我们使用容斥原理可以得到一个级数表达式。

但要想利用容斥原理，我们考虑小组是有序的情形比较方便。除以N!就可以得到所要得结果。

如果小组可以是空的，而且空的小组不少于二个，不能简单地除以N!。因为空集是不可分的。

寒潭清 · 发表于 2005-11-30 14:42:53

		自动登录	找回密码
密码			立即注册

动态微博