组合计数谜题：掷 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 个相同值的骰子的方法数（即，对于所有骰子值）。 注意：如果我只是天真地使用上面的第一个答案并乘以 bt 8，我会得到大量的重复计算？

  我知道我可以解决每种情况 (5 1's)、(5, 2's)、(5, 3's)、... (5's, 8) 将它们相加（更简单地说 8*(5 1's) ）。 然后减去重叠数的总和 (5 1's) 和 (5 2's)、(5 1's) 和 (5 3's)... (5 1's) 和 (5, 2's) 以及 ... 和 (5, 8's)但这看起来非常混乱。 我会以一种扩展到大量样本和大量类的方式对此进行概括。

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

  所以 111110000000000000000 或 11110100000000000002 或 11111100000001110000 或 11011211222222223333，但不是 00001111222233334444 或 00051 1512252363347744.

我正在寻找解释数学或指向支持此功能的库（尤其是 python 模块）的答案。 细节和例子加分。

Answer 1

我建议您花一点时间编写蒙特卡罗模拟，并让它运行，同时您手工计算数学。 希望蒙特卡洛模拟能够在您完成数学计算之前收敛，并且您将能够检查您的解决方案。

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

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)) 证明其源代码本身更加困难。

Answer 3

i 个 s 面骰子之和的精确概率分布 Fs,i 可以通过单骰子概率分布与其自身的重复卷积来计算。

其中 对于所有 ，否则为 0。

http://en.wikipedia.org/wiki/Dice

Answer 4

如果你必须概括它（得到精确的公式），这个问题真的很难。

但无论如何，让我解释一下算法。
如果你想知道

恰好得到 5 的方法数
相同值的骰子

您必须重新表述之前的问题，如

计算获得的方法数
正好 5 个骰子的值是 3 AND 否
其他值可以精确重复 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 次。 总共 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)是在没有其他骰子重复5次的情况下，在10次投掷中获得5个值为2的骰子的方法数。
F(10,6,5,2) = (1-F(5,5,5)/5^5) * 6^10 = (1-1/5^4) * 6^10

嗯...我认为它在某些部分可能不正确，但无论如何，你明白了。 我希望我能让算法易于理解。

编辑：
我做了一些检查，我意识到当你得到多个值重复恰好 5 次时，你必须添加一些情况。 你没有时间解决那部分......

Answer 5

这就是我的想法……

如果你只有 5 个骰子，你就只有 8 种方法来得到你想要的东西。

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

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

（至少 5 的答案是相同的。）

Answer 6

我相信你可以使用 n 个事件中 x 次出现的公式为：

P = 概率^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) );
    }
  }

Answer 7

递归解法：

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