Математическая задачка

tarasv> Есть генератор случайных числе который выдает цифры 1, 2 или 3. Какова вероятность того что в серии из K чисел будет N одинаковых, например 5 единиц из восьми. Тривиальный вариат понятен 8 из 8 будет с вероятностью 1/3^K. Для 7ми тоже понятно что 2 или 3 один раз может выпасть каждая в восьми разных местах, тосеть вероятность 8+8/3^8. Для 6 число размещений двойки и тройки 2*(8*7) т.е. 112. А вот на 5 и дальше меня заклинило - никак не могу сообразить как считается число размещений в таком случае.

Ну, сумма C(k,n) по каждому значению. C, а не A потому, что по фиг порядок, главное общее число.

В том числе для 7 будет (8+8+8)/3⁸ — три раза восьмёрка, т.к. может быть 1, 2, 3 в восьмой позиции. Только надо уточнить — а 8 единиц (двоек и троек) удовлетворяют условию или нет. Т.к. формулка для для формулировки "в точности N одинаковых. Если будет формулировка "хотя бы", то там надо добавлять сверху и с большим числом одинаковых. Хотя даже в точности надо решить вопросы, а будем ли считать (111,222,33) за нормальное явление или нет. Если будем, то там надо менять тоже немного. Ну и некоторые в варианты для формулировки "в точности" будут невозможны. Скажем, в точности две одинаковые цифры для 8 попыток.



C(k,n)=k!/(n!*(n-k)!) — сочетания.


PS A(k,n)=k!/(k-n)! — перестаноки.

tarasv> Есть генератор случайных числе который выдает цифры 1, 2 или 3. Какова вероятность того что в серии из K чисел будет N одинаковых, например 5 единиц из восьми. Тривиальный вариат понятен 8 из 8 будет с вероятностью 1/3^K. Для 7ми тоже понятно что 2 или 3 один раз может выпасть каждая в восьми разных местах, тосеть вероятность 8+8/3^8. Для 6 число размещений двойки и тройки 2*(8*7) т.е. 112. А вот на 5 и дальше меня заклинило - никак не могу сообразить как считается число размещений в таком случае.

Че-то я не понял. Че тут считать-то? У нас есть троичная система (будем считать не 1 2 3 а 0 1 2). Есть числа длиной К в этой троичной системе. Скока всего чисел? Вот скока: 3**К (от 0 до 3**K-1). Скока из них "благоприятных"? Для простоты будем считать повторяющимися нули. Сколько есть n-значных чисел, в которых ровно N нулей? Вернее, сколько есть чисел, в которых ровно К-N не нулей? Пусть N-K = M. Какими способами можно разместить 2 числа (1 и 2) на M позициях? Легко - это будет 2**M различных позиций. Сколькими способами можно "разбавить" каждое из этих М-позиционных чисел еще N нулями?


Пойдем по индукции. У нас M-позиционное поле, сколькими способами можно добавить 1 нуль? Легко видеть - M+1 способом. 2 нуля? (M+1)*(M+2) И т.п. Правда, это количество ПЕРЕСТАНОВОК, а нам нужны сочетания, так что уберем одинаковые наборы, получим

k!/(n! (k-n)!)

Т.е. для каждого из 2**M различных позиций умножаем на количество "разбавлений".

Это количество благоприятных исходов. Тогда вероятность

M = K-N
P = (2**M * k!/(n! (k-n)!) )/(3**k)

В частности, 8 из 8: (M=0):

P = 1/3**8

7 из 8 (M=1)
P = 2*8/(3**k)

ЗЫ Я не уверен, что я хорошо объясняю. Но результат, вроде, верен.

Сергей-4030> ЗЫ Я не уверен, что я хорошо объясняю. Но результат, вроде, верен.

Миша, Сергей спасибо! У меня похоже сегодня тяжелый день. Я считал C(k,n) смотрел на то что получилось и недоумевал что получилась фигня - т.е. я просто забыл умножать на степень двойки.

Сергей-4030> P = (2**M * k!/(n! (k-n)!) )/(3**k)

Серёг, тут осторожней надо, т.к. задача N одинаковых. Поэтому из 2^M надо вычесть некоторые, чтообы исключить двойной подсчёт. Особенно в случае, когда "только N одинаковых" — в эти 2^M, если N меньше, чем K/m (m — количество возможных значений). Скажем точно два одинаковых значения в кортеже длиной 8 из значений 1, 2, 3 точно не имеет решения, т.к. в оставшихся 6 и двух других значениях точно будет больше 2-х одинаковых.

Т.е. задачу надо уточнять, а то не хватает данных.

Сергей-4030>> P = (2**M * k!/(n! (k-n)!) )/(3**k)
Mishka> Серёг, тут осторожней надо, т.к. задача N одинаковых. Поэтому из 2^M надо вычесть

Из контекста, как я его понял (и вроде Тарас неявно подтвердил) имеется в виду "таких-то одинаковых", скажем, единиц.

Сергей-4030> Из контекста, как я его понял (и вроде Тарас неявно подтвердил) имеется в виду "таких-то одинаковых", скажем, единиц.

Не уловил. Вроде, как N одинаковых из K возможных.
Но всё равно остаётся вопрос, если 5 единиц, то это точно пять или пять достаточно.

В общем, Тарас, ау?

Mishka> Но всё равно остаётся вопрос, если 5 единиц, то это точно пять или пять достаточно.
Mishka> В общем, Тарас, ау?

По-моему, имеется в виду точно пять.

Написать прогу и посмотреть, че уж там..

TEvg> Написать прогу и посмотреть, че уж там..

Зачем? Если это хорошо известные вещи из комбинаторики.

Сергей-4030> По-моему, имеется в виду точно пять.

Да, N задано строго.

TEvg>> Написать прогу и посмотреть, че уж там..
Mishka> Зачем? Если это хорошо известные вещи из комбинаторики.

Программу я таки написал, когда ощутил что C(k,n) както маловато будет.