组合计数谜题：掷20个8面骰子，至少得到5个相同点数的骰子的概率是多少？

Question

假设有一个游戏，需要掷20个8面骰子，总共可能出现8的20次方种结果。为了计算某个特定事件发生的概率，我们需要将该事件发生的方式数量除以8的20次方。

可以计算出恰好获得5个值为3的骰子的方式数。通过(20选5)可以得到3的数量，7的15次方可以得到在15次掷骰中没有获得值为3的骰子的方式数。

number of ways to get exactly 5, 3's = (20 choose 5)*7^15.

答案也可以看作是如何重新排列字符串3,3,3,3,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0（20选5）乘以我们的零值的总数（假设有7个合法值）7^15（这正确吗）。

问题1：如何计算获得恰好5个相同值的骰子的方法数量（即，对于所有骰子值）。 注意：如果我只是朴素地使用上面的第一个答案并乘以8，则会得到大量重复计数吗？

我明白我可以解决每种情况（5个1），（5个2），（5个3），...（5个8），将它们相加（更简单的是8 *（5个1））。然后减去重叠数量的总和（5 1）和（5 2），（5 1）和（5 3）...（5 1）和（5,2）和...和（5,8），但这似乎非常混乱。我需要一种通用化的方法，以便在样本数量和类别数量很大时进行扩展。

如何计算至少获得5个相同值的骰子的方法数量？

因此，111110000000000000000或11110100000000000002或11111100000001110000或11011211222222223333，但不是00001111222233334444或000511512252363347744。

我正在寻找解释数学的答案或指向支持此的库（尤其是Python模块）。有详细和示例的额外积分。

- Ethan Heilman

---

相关链接：https://dev59.com/oUbRa4cB1Zd3GeqPz2Mz - Robert Harvey

Answer 1

我建议你花点时间写一个蒙特卡罗模拟程序，并让它在你手工计算时运行。希望蒙特卡罗模拟能在你完成手工计算之前收敛，这样你就可以检查你的解决方案了。

一个稍微更快的选择可能涉及创建一个数学问题的SO克隆。

- David Locke

---

+1 我希望还有其他人能看到你回答中的幽默 :) - Robert Harvey

+1，有趣，以及数学中的克隆。我尝试这样做是为了双重检查我编写的程序生成蒙特卡罗模拟结果的准确性。=) - Ethan Heilman

Answer 2

使用包含/排除原理可以解决重复计数的问题。

我猜测应该是这样的：

Choose(8,1)*P(one set of 5 Xs) 
- Choose(8,2)*P(a set of 5 Xs and a set of 5 Ys) 
+ Choose(8,3)*P(5 Xs, 5 Ys, 5 Zs) 
- Choose(8,4)*P(5 Xs, 5 Ys, 5 Zs, 5 As)

P(set of 5 Xs) = 20 Choose 5 * 7^15 / 8^20
P(5 Xs, 5 Ys) = 20 Choose 5,5 * 6^10 / 8^20

等等。这并没有直接解决“超过5个相同数字”的问题，因为如果您只是对应于5、6、7..20应用此操作的结果进行求和，则会过多计算例如10个1和5个8的情况。

您可能可以再次应用包含排除来得出第二个答案；因此，P(至少5)=P(一个20的集合)+ ... + (P(一个15的集合) - 7*P(从5个骰子中取得一个5的集合)) + ((P(一个14的集合) - 7*P(从6个中取得一个5的集合) - 7*P(从6个中取得一个6的集合))。编写该代码源正在变得更加困难。

- CoderTao

Answer 3

如果你需要概括这个问题（得到确切的公式），那么这个问题确实很难。

但是，让我来解释一下算法。如果你想知道“恰好得到5个相同点数骰子”的方法数量，你必须重新表述你之前的问题，如下所示：“计算得到恰好5个点数为3的骰子的方式数量，并且没有其他值可以重复出现5次。”

为了简单起见，我们将函数F（20,8,5）（5个骰子，所有值）称为第一个答案，将F（20,8,5,3）（5个骰子，值为3）称为第二个答案。我们有F（20,8,5）= F（20,8,5,3）* 8 +（重复出现多个值5次的情况）。

因此，如果我们可以得到F（20,8,5,3），那么它应该很简单，不是吗？嗯...并不完全是这样...

首先，让我们定义一些变量：X1，X2，X3...，Xi，其中Xi = 我们得到骰子i的次数。

然后：

F(20,8,5)/20^8 = P(X1=5 or X2=5 or ... or X8=5, with R=20(rolls) and N=8(dice number))

, P（陈述）是编写概率的标准方式。

我们继续：

F(20,8,5,3)/20^8 = P(X3=5 and X1<>5 and ... and X8<>5, R=20, N=8) 
F(20,8,5,3)/20^8 = 1 - P(X1=5 or X2=5 or X4=5 or X5=5 or X6=5 or X7=5 or X8=5, R=15, N=7)  
F(20,8,5,3)/20^8 = 1 - F(15,7,5)/7^15

递归地：

F(15,8,5) = F(15,7,5,1) * 7  
P(X1=5 or X2=5 or X4=5 or X5=5 or X6=5 or X7=5 or X8=5, R=15, N=7) = P(X1=5 and X2<>5 and X4<>5 and .. and X8<>5. R=15, N=7) * 7

---

F(15,7,5,1)/7^15 = 1 - F(10,6,5)/6^10 F(10,6,5) = F(10,6,5,2) * 6

---

F(10,6,5,2)/6^10 = 1 - F(5,5,5)/5^5
F(5,5,5) = F(5,5,5,4) * 5

好的...F(5,5,5,4)表示在5次掷骰子中，恰好有5个值为4的骰子，没有其他骰子重复5次的方式总共有1种。这相当于5^5中的1种可能性。因此概率为1/5^5。

F(5,5,5)表示在5次掷骰子中，恰好有5个骰子的任意值（5个值中的任意一个）的方式总共有5种。因此其概率为5/5^5=1/5^4。

F(10,6,5,2)表示在10次掷骰子中，恰好有5个值为2的骰子，没有其他骰子重复5次的方式总共有多少种。 F(10,6,5,2) = (1-F(5,5,5)/5^5) * 6^10 = (1-1/5^4) * 6^10。

我认为某些部分可能不正确，但总体来说，您应该能够理解算法。

- Francisco

---

+1，针对第一个问题的回答。您对第二个问题有任何想法吗？<>符号是什么意思？ - Ethan Heilman

Answer 4

一组i个s面骰子的精确概率分布Fs，i可以通过将单个骰子的概率分布与自身重复卷积来计算。 其中对于所有的n∈[1,s]，，否则为0。 http://en.wikipedia.org/wiki/Dice

- Robert Harvey

---

+1 不错的链接。不幸的是，我不是在寻找骰子的总和，而是相邻骰子投掷中数值重复的次数。也就是说，我掷10次骰子，并且想知道得到至少3个价值为5的骰子的概率。 - Ethan Heilman

Answer 5

递归解决方案：

Prob_same_value(n) = Prob_same_value(n-1) * (1 - Prob_noone_rolling_that_value(N-(n-1)))

- mbeckish

---

递归很好，但常常让我困惑。我不确定我理解你的算法是如何工作的，n是什么？Prob_same_value(2)提供了什么？1/8？ - Ethan Heilman

是的，我只是随便提出了这个想法，没有太多细节。基本上，我的意思是，为了获得至少五个相同的值，你需要获得四个相同的值，并且你不能让其他骰子都不匹配这四个值。 - mbeckish

不计算顺序混乱的序列。因此，它会计算(11111000000000000000、11111000000000000002、11111000000000000003、... 11111888888888888888、22222000000000000000、22222000000000000002、... 22222888888888888888)这样的序列，但会忽略像(00111110000000000000、00001100100110000000、02020202020000000000)这样的序列。 - Ethan Heilman

好的，我把这个问题和其他问题搞混了，让我们再想一想。 - Ethan Heilman

@mbeckish - 我再仔细想了一下你的答案，现在我理解你的直觉了，而且我要说这真的相当聪明。这种递归很适合动态规划解决方案（效率高）和/或内存折衷。我不确定Prob_noone_rolling_that_value(N-(n-1))是怎么回事？N与n的关系是什么？是打字错误吗？对于所有n，(n-(n-1))不应该等于1吗？N是n的初始值而不是递归值吗？你是不是指的是(n!-(n-1))? 无论如何，非常好的答案，如果我有超过一个投票权就好了。 - Ethan Heilman

Answer 6

我相信你可以使用“x次事件发生在n次机会中”的公式：

P = probability^n * (n!/((n - x)!x!))

因此，最终结果将是从0到n的结果之和。

我真的看不出有什么简单的方法可以将其合并为一个步骤，这样会更清晰。通过这种方式，您还可以在代码中拼写出公式。但是，您可能需要编写自己的阶乘方法。

  float calculateProbability(int tosses, int atLeastNumber) {
    float atLeastProbability = 0;
    float eventProbability = Math.pow( 1.0/8.0, tosses);
    int nFactorial = factorial(tosses);

    for ( i = 1; i <= atLeastNumber; i++) {
      atLeastProbability += eventProbability * (nFactorial / (factorial(tosses - i) * factorial(i) );
    }
  }

- JonBWalsh

---

+1 数学，细节和源代码。你的解决方案不起作用，因为只有像11111000000000000和111000000001100这样的序列才会被计算。也就是说，11111000000000000和11111000000000002是不同的序列，需要分别计算。例如，如果你进行40次采样（掷骰子），你必须至少有一个重复出现5次（最坏情况）。你使用的公式没有显示这一点。 - Ethan Heilman

我不认为我理解你的评论。1/8的权重对于一个积极事件（掷出特定数字）已经覆盖了这一点。在可能结果A的两种情况下： 1 2 3 4 5 6和 1 0 0 0 0 0如果我们不关心“非1”值，它们在功能上是相同的。此外，我不认为OP正在询问至少有X个骰子具有与任何值相同的概率（这是不同的）。我的理解是他想知道至少有x个骰子具有y值的概率。 - JonBWalsh

哈哈，我知道你就是楼主。如果你的意思是想问：“至少有X个骰子有相同数字的概率是多少”，那么你可能需要重新表述原问题，因为它并不清晰。由于你一开始谈论的是至少含有5个三的组合数量，这让人们认为你在讨论X个骰子的某个值的概率。 - JonBWalsh

@JonBWalsh，你说得很好。我在问题中澄清了。对于混淆感到抱歉。 - Ethan Heilman

Answer 7

这是我在考虑的内容...

如果你只有5个骰子，你只有八种方法可以得到你想要的。

对于这八种方法中的每一种，其他15个骰子的所有可能组合都可以奏效。

所以- 我认为答案是：(8 * 815) / 820

(至少有5个相同的情况下的答案。)

- Anon

---

它不计算顺序混乱的序列，所以它会计算（11111000000000000000、11111000000000000002、11111000000000000003、... 11111888888888888888、22222000000000000000、22222000000000000002、... 22222888888888888888）, 但是会错过类似（00111110000000000000、00001100100110000000、02020202020000000000）的序列。此外，请注意随着样本大小的增加，碰撞的概率保持不变（(8 * (8^15)) / (8^20) = 0.000244140625，(8 * (8^25)) / (8^30) = 0.000244140625，(8 * (8^95)) / (8^100) = 0.000244140625）。 - Ethan Heilman

@e5：我同意我的分子没有考虑不同的排列顺序-但是您确定您的分母考虑了吗？考虑两个骰子掷出而不是20。如果您想要计算顺序，应该是8 ** 2还是（2 * 8 ** 2）以考虑[red_die, blue_die]与[blue_die，red_die]之间的区别？ - Anon

@Anon，有趣的观点。我认为我应该没问题，因为我按顺序识别我的骰子，所以红色骰子总是先被掷出，蓝色骰子第二个，依此类推。 - Ethan Heilman

@e5: 不管怎样，你的样本大小观察证明了我的答案是错误的。投掷33个八面体骰子意味着至少会有5个相同的数字。 - Anon