Головоломка для подсчета Комбинаторики:Бросьте 20 8-гранных кубиков, какова вероятность выпадения как минимум 5 кубиков одинакового достоинства

Question

Предположим, что игра, в которой игрок бросает 20 8-гранных кубиков, составляет в общей сложности 8 ^ 20 возможных исходов.Чтобы вычислить вероятность наступления конкретного события, мы делим количество способов, которыми это событие может произойти, на 8 ^ 20.

Можно подсчитать количество способов получить ровно 5 кубиков со значением 3.(20 выбирают 5) дает нам количество заказов равное 3.7 ^ 15 дает нам количество способов, которыми мы не можем получить значение 3 для 15 бросков.

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 (20 выбирают 5), умноженное на общее количество значений, равное нулю (при условии, что 7 допустимых значений) 7 ^ 15 (правильно ли это).

• Вопрос 1:Как я могу вычислить количество способов получить ровно 5 кубиков одинакового значения (то есть для всех значений кубика).Примечание:если я просто наивно использую свой первый ответ выше и умножаю bt на 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).Дополнительные баллы за подробности и примеры.

Answer 1

Двойной подсчет может быть решен с помощью Принцип включения/Исключения

Я подозреваю, что это выходит к:

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 (один набор из 5 из 6) - 7 * P (один набор из 6 из 6)).Придумать исходный код для этого оказывается гораздо сложнее.

Answer 2

Я предлагаю вам потратить немного времени на написание симуляции по методу Монте-Карло и дать ей поработать, пока вы решаете математические задачи вручную.Надеюсь, моделирование методом Монте-Карло сойдется до того, как вы закончите с математикой, и вы сможете проверить свое решение.

Немного более быстрый вариант может включать создание SO-клона для вопросов по математике.

Answer 3

Точное распределение вероятностей Fs,i суммы i s-стороннего кубика может быть вычислено как повторная свертка распределения вероятностей одного кубика с самим собой.

где для всех и 0 в противном случае.

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

Answer 4

Эта проблема действительно сложна, если вам нужно ее обобщить (получить точную формулу).

Но в любом случае, позвольте мне объяснить алгоритм.Если ты хочешь знать

количество способов получить ровно 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 кубиков достоинством 4 за 5 бросков, таких как ни один другой кубик, который не повторяется 5 раз.Существует только 1 способ из общего числа 5 ^ 5.Тогда вероятность равна 1/5 ^ 5.

F (5,5,5) - количество способов получить 5 кубиков любого значения (из 5 значений) за 5 бросков.Очевидно, что это 5.Тогда вероятность равна 5/5 ^ 5 = 1/5 ^ 4.

F (10,6,5,2) - количество способов получить 5 кубиков достоинством 2 за 10 бросков, таких как ни один другой кубик, который не повторяется 5 раз.F(10,6,5,2) = (1-F(5,5,5)/5^5) * 6^10 = (1-1/5^4) * 6^10

Что ж...Я думаю, что в какой-то части это может быть неверно, но в любом случае, вы поняли идею.Я надеюсь, что смог бы сделать алгоритм понятным.

Редактировать: Я провел некоторые проверки и понял, что вам нужно добавить несколько случаев, когда вы получаете более одного значения, повторяющегося ровно 5 раз.У тебя нет времени решать эту часть...

Answer 5

Вот о чем я думаю...

Если бы у вас было всего 5 кубиков, у вас было бы только восемь способов получить то, что вы хотите.

Для каждого из этих восьми способов работают все возможные комбинации остальных 15 кубиков.

Итак, я думаю, что ответ таков:(8 * 815) / 820

(Ответ по крайней мере для 5 один и тот же.)

Answer 6

Я полагаю, что вы можете использовать формулу x вхождений в n событиях как:

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)))