概率 n 选择 k

Question

我尝试解决这个 TopCoder 问题:http://community.topcoder.com/stat?c=problem_statement&pm=10863&rd=14150

但是，我的解决方案不好，我不明白为什么。

我理解那里给出的解决方案(下页:查找 LotteryPyaterochka):http://apps.topcoder.com/wiki/display/tc/SRM+466

所以，总结一下我的问题:

我们正在玩一种特殊的彩票:

此彩票中的每张彩票都是一个 N 行 5 列的矩形网格，其中每个单元格包含 1 到 5*N 之间的整数(含 1 和 5*N)。一张票中的所有整数都是不同的。

抽奖组织者随机选择 5 个不同的整数，每个整数在 1 到 5*N 之间(含)。 5 个整数的每个可能子集被选择的概率相同。这些整数称为中奖号码。当且仅当彩票的行中包含至少 3 个中奖号码时，该彩票才被视为中奖者。

我们想知道中奖彩票的数量(因此，同一行中至少有 3 个中奖号码)

所以，我坚持以下步骤:

选择“中奖行”中出现的 5 个号码的方式数。

topCoder 解决方案说:

(#ways of choosing the 5 numbers which appear in the 'winning row') =

(#ways of choosing the x winning numbers which appear in the 'winning row') * (#ways of choosing 5-x 'non-winning numbers') =

(5 choose x) * ((5N-5) choose (5-x))

Since the number of winning numbers in this row is at least 3, x can be 3 or 4 or 5. So, we have (#ways of choosing the 5 numbers which appear in the 'winning row') =

(5 choose 3) * ((5N-5) choose 2) + (5 choose 4) * ((5N-5) choose 1) + (5 choose 5) * ((5N-5) choose 0))

我说的是:

(#ways of choosing the 5 numbers which appear in the 'winning row') =

(3 number among the 5 winning number) * (2 numbers to complete the row to choose among the 5N-5 non winning number + 2 winning number non chosen before) =

(5N choose 3) * ((5N-3)choose 2)

对于 N = 10，我的方法给出:(5 选择 3)*(47 选择 2) = 10810

topcoder 方法给出:((5 选择 3)(45 选择 2) + (5 选择 4)(45 选择 1) + (5 选择 5)*(45 选择 0) ) = 10126

为什么我的方法不对？

谢谢

Answer 1

假设中奖号码是 1、2、3、4 和 5。现在让我们看看包含中奖行中所有五个号码的彩票。

您的方法会对该票进行多次计数，因为它包含在以下计数中:

1 2 3 + two other numbers
1 2 4 + two other numbers
1 2 5 + two other numbers
1 3 4 + two other numbers
...

同样的情况也会发生在有四个中奖号码的彩票上。

这就是为什么这些案例需要单独统计的原因。