-
Есть шарики k цветов. Вероятность выпадения шарика любого цвета - одинакова и со временем не меняется. Последовательно выбирается n шаров.
Какова вероятность того, что в выборке присутствуют шары всех цветов?
-
100 % так как хотя выпадают они случайно, но про выбираются ничего не сказано. Выбирающей может специально отбрасывать неподходящие.
-
50% - либо присутствуют, либо нет.
-
если n<k то 0%
-
это какие шары, из ореха чтоли?
-
для K = 2
K! / K^K * (1 / K ^ (N - K + 1) - 1) / (1 / K - 1)
Конечно, можно красивее записать (К на 2 заменить), но лень.
Для K > 2 надо думать, хотя логика понятна.
Могу сказать, как для K = 2 делал.
1. Обозначим P1 и P2 - вероятности первого и второго шарика. Они равны 1/К, но пусть будет с номерами.
2. N=K
Успех - P1,P2 или P2,P1. В итоге успех 1/(P1*P2)+1/(P2*P1). Или 2/K^K
3. N=K+1
Успех:
из пред. примера 2/K^K
плюс
P1,P1,P2 или P2,P2,P1.
В итоге
2/K^K + 2/K^(K+1)
и т.д.
Для K > 2 сложнее, ибо больше вариантов.
Например
P1P1P2P3
P1P1P3P2
P1P2P2P3
P1P2P1P3
и т.д. надо считать.
Ключевые слова - сочетание, перестановка, размещение.
Кстати для N=K будет K! / K^K.
-
> Ключевые слова - сочетание, перестановка, размещение.
есть еще термин - ключевой-таки))
-
Ну вообще задача сложная. Думал для фана сделать. Что-то не сдюжил. Могу только кодом экспериментальной проверки поделиться)))
procedure TForm1.Button1Click(Sender: TObject);
const
cSteps = 1000000;
cK = 2;
cN = 20;
function kFact(const aV: Integer): Integer;
begin
if aV < 1 then
Result := 0
else
if aV = 1 then
Result := 1
else
Result := aV * kFact(aV - 1);
end;
function kP(const aV, aP: Integer): Integer;
begin
if aP = 0 then
Result := 1
else
if aP = 1 then
Result := aV
else
Result := aV * kP(aV, aP-1);
end;
var
kI, kJ: Integer;
kF: array[0..cK-1] of Boolean;
kAll: Boolean;
kFound: Integer;
kExperiment, kFormula: Double;
begin
kFound := 0;
for kI := 1 to cSteps do
begin
FillChar(kF, SizeOf(kF), 0);
for kJ := 1 to cN do
begin
kF[Random(cK)] := True;
end;
kAll := True;
for kJ := 0 to High(kF) do
begin
if not kF[kJ] then
begin
kAll := False;
Break;
end;
end;
if kAll then
Inc(kFound);
end;
kExperiment := kFound / cSteps;
kFormula := kFact(cK) / kP(cK, cK) * (1 / kP(cK, cN-cK+1) - 1) / (1 / cK - 1);
Memo1.Lines.Add(Format('Опыт=%.6f Формула=%.6f Разница=%.6f', [kExperiment, kFormula, kExperiment-kFormula]));
end;
-
А тебе вообще зачем это?
ЗЫ
Тут понятно, как делать.
Например, К=3, N = 4.
Выписываешь все успешные комбинации из четырех шаров (из трех - понятно, это К!/К^К - кол-во успешных кобинаций это размещение от K, т.к. K!, 1/K - вероятность конкретного шара, 1/K^K - вероятность конкретной последовательности в одной успешной комбинации).
1123
1132
1213
1223
1332
1312
21...
22...
23...
31...
32...
33...
Пытаешься понять, что тут за комбинаторика.
Потом для N=5 и т.д.
Думаю, мат индукцией тут что-то нарисуется.
Но что-то не соображу на коленке, думать шибко нада....
-
> А тебе вообще зачем это?
пятничная задачка - я решил, по работе нужно было.
-
Я бы рекуррентно решал.
Пусть P(n, k) - вероятность того, что в выборке присутствуют шарики всех цветов. Пусть A(n, k) - вероятность того, что в выборке присутствует ровно k шариков заданного цвета.
Берём первый шарик. Пусть он цвета c. Тогда в оставшейся последовательности из n-1 шарика, шарик цвета c может появится 0, 1, ... n-1 раз. Это полная группа событий, вероятности этиз событий равны A(n-1, 0), A(n-1, 1), A(n-1, 2) ... A(n-1, n-1) соответственно.
В каждом из этих случаев надо умножить на верноятность присутствия k-1 шарика в оставшихся шариках, это будет P(n-1, k-1), P(n-2, k-1), P(n-3, k-1), ... P(0, k-1)
P(n, k) = P(n-1, k-1) * A(n-1, 0) + P(n-2, k-1) * A(n-1, 1) + ... A(n-1, n-1) * P(0, k-1)
Ну и теперь надо поднять формулы для A, упростить, ...
-
> Но что-то не соображу на коленке, думать шибко нада....
допустим, в группе из 100 человек 60 любят пиво, 40 - вино, 30 - водку. Пиво и вино любят 20 человек. Вино и водку - 15, пиво и водку - 10. Пиво, вино и водку - 10. Сколько трезвенников?
n := 100 - 60 - 40 - 30.
Но тут мы вычли по два раза тех, кто любит оба напитка, тогда нужно их прибавить:
n := n + 20 + 15 + 10
а теперь мы лишний раз приплюсовали любителей всего, значит:
n := n - 10
+-+-...
-
> картман © (21.04.18 21:26) [11]
Я пас)
Будут формулы, поставлю в мой код выше. Проверим)
Пока понаблюдаю.
-
> картман © (21.04.18 21:26) [11]
> допустим, в группе из 100 человек 60 любят пиво, 40 - вино,
> 30 - водку. Пиво и вино любят 20 человек. Вино и водку
> - 15, пиво и водку - 10. Пиво, вино и водку - 10. Сколько
> трезвенников?
Вроде 5.
(наверное младенцы)
-
> картман © (20.04.18 11:00)
Решил для случаев:
1. N=K
P(K,N) = K!/K^K
2. N=K+1
P(K,N) = K!/K^K + K! * K * (K-1) / 2 / K ^ (K+1)
И что интересно, первый раз в жизни подобную задачу решал численно. Хороший метод. Надо будет на будущее запомнить.
Вся проблема была в коэффициенте K! * K * (K-1) / 2 - т.е. сколько удачных успешных комбинаций из К+1 шаров. Исходя из моего кода выше подобрал коэффициент для K=2,3,4,5 (это 2,18, 144, 1200), увидел зависимость (K! * сумма арифм. прогрессии), вывел формулу. Проверил для для К до 15. Все сходится. Но объяснить K! * K * (K-1) / 2 не могу - мозгов не хватает.
3. Думаю для N=K+2 тоже можно подбором формулу увидеть. А потом по индукции доказать в общем случае.
-
> K! * K * (K-1) / 2
К! - ну, это кол-во перестановок
K * (K-1) / 2 - если привести к одному знаменателю ф-лу:
K!/K^K + K! * K * (K-1) / 2 / K ^ (K+1)
в числителе получится
К!* К(К+1)/2, второй множитель - кол-во вариантов выбрать два шарика одного цвета(при n = k+1 один из цветов же будет выбран дважды) и это не ариф.прогрессия, а Це из ка по два.
-
> Це из ка по два.
из ка плюс один
-
> картман © (22.04.18 16:25) [15]
Спасибо за разъяснения. Я пока не понял, но разберусь. Ибо интересно. Комбинаторика и вообще тервер не были моими любимыми. Учился на потоке матметодов - конкретно, выпуклая конечномерная оптимизация. Тем не менее, хочу пояснить про арифм. прогрессию. Решил то верно для N=K+1. И потом, считаю интересным, что из компьютерного моделирования можно сделать качественный вывод. Итак, было понятно, что д.б. K!/K^K+M/K^(K+1). Знаменатель степень 1/K, т.к. выборы независимы. А что с M? Экспериментально программой выше нашел, что: K N M
1 2 1
2 3 2 = 2! * 1 = 2! * (1)
3 4 18 = 3! * 3 = 3! * (1+2)
4 5 144 = 4! * 6 = 4! * (1+2+3)
5 6 1200 = 5! * 10 = 5! * (1+2+3+4) Из чего сделал предположение, что: K N M
6 7 10800 = 6! * 15 = 6! * (1+2+3+4+5)
7 8 105840 = 7! * 21 = 7! * (1+2+3+4+5+6)
8 9 1128960 = 8! * 28 = 8! * (1+2+3+4+5+6+7) И оказался прав - до K=15 проверил, все верно. Дальше дело техники получить M как K!*K*(K-1)/2, где K*(K-1)/2 - как раз сумма арфим. прогрессии от 1 до K-1.
-
Шикарно)) осталось для любого случая(там, кстати, сумма с интересными свойствами получается: при к > n равна нулю, насколько бы эти числа не отличались)
-
> картман © (22.04.18 20:54) [18]
> Шикарно)) осталось для любого случая(там, кстати, сумма
> с интересными свойствами получается: при к > n равна нулю,
> насколько бы эти числа не отличались)
Будет время, сделаю. Все же "завело" меня то, что из количественного численного анализа можно получить качественный вывод.
Чувствуешь себя ученым))) Гипотезы и т.д.
-
> Mystic © (21.04.18 21:06) [10]
Хм. Насчет рекурсии я думал так:
Пусть k - общее количество цветов, как в условии
n - длина последовательности
r - количество цветов в последовательности.
тогда:
function p(k,n,r:integer):extended;
begin
if r>n
then Result:=0
else if r=1
then Result:=1/power(k,n-1)
else result:=p(k,n-1,r-1)*(k-r+1)/k+p(k,n-1,r)*r/k;
end;
т.е. если например имеется 5 цветов и последовательность из 7 шариков то вызываем функцию так:
px:=p(5,7,5);
Вот только как теперь с него сделать общую формулу - пока не придумал.
-
В таком виде понятнее должно быть:
function P(k,n:integer):extended;
function SubP(n,r:integer):extended;
begin
if r>n then Result:=0
else if r=1 then Result:=1/power(k,n-1)
else Result:=((k-r+1)*SubP(n-1,r-1) + r*SubP(n-1,r))/k;
end;
begin
Result:=SubP(n,k);
end;
-
Всегда было любопытно: почему большинство задач - про комбинаторику и т.п. тервер?
у кого-то в жизни встречаются такого рода задачи? или это просто типичная тема для интеллектуалов, типа как шахматы?
в самом деле интересно (про реальные задачи у вас на работе, связанные с этим)
-
> в самом деле интересно (про реальные задачи у вас на работе,
> связанные с этим)
> картман © (21.04.18 20:31) [9]
>
>
> > А тебе вообще зачем это?
>
> пятничная задачка - я решил, по работе нужно было.
-
В какой области жизнедеятельности применяется ваш софт?
-
логистика
-
-
интересно, что числитель при k>n равен нулю))
-
А можно интереса формулу сюда написать, или выложить на что-то более доступное? А то самому интересно, но яндекс у нас в/на Украине заблокирован, а искать какой-нить прокси-сервер или делать что-то другое для обхода - как-то лень.
-
> а искать какой-нить прокси-сервер или делать что-то другое
> для обхода - как-то лень
во времена, когда блокируют рутрекер и телеграм, прокси должны быть под рукой :)
-
> во времена, когда блокируют рутрекер и телеграм, прокси
> должны быть под рукой :)
Ок. ты меня убедил. Пришлось найти все-таки проксик. Посмотрел формулу.
-
> картман © (24.04.18 12:39) [26]
> в общем, такая вот формулка получается: https://yadi.sk/i/P2A-
> 0_Zv3UiLtc
C - это что? C(n,k) = n! * / (k!*(n-k)!) ?
-
> SergP © (24.04.18 14:04) [30]
> Ок. ты меня убедил. Пришлось найти все-таки проксик.
Opera с её vpn
Самое простое и готовое "из коробки"
поражаюсь тому, что её не блокируют
-
> KSergey © (24.04.18 15:42) [32]
Да просто не так часто и бывает необходимость лазить по яндексу, за время действия блокировки он мне первый раз понадобился... Ну и еще ранее один раз была необходимость зайти на сайт drweb. Посему и не обзавелся чем-нить постоянным для обхода блокировки, оба раза просто искал прокси, находил и заходил через них. А что касается остального заблокированного, то вконтакте и одноклассники мне и не нужны (вообще не перевариваю такие вещи, как вконтакте, одноклассники, твиттер, фейсбук, телеграм, и прочие, т.е. все что называется "социальные сети"). А mail.ru - ИМХО вообще правильно сделали, что заблокировали (вот только потом его почему-то разблокировали), ибо это рассадник различной гадости, той что в инете люди называют "вирусы от mail.ru" (спутник, "браузер" Амиго и пр.). А все остальные российские сайты, которые бывают мне нужны нормально работают, их никто не блокировал.
-
> C(n,k) = n! * / (k!*(n-k)!)
да
-
> картман © (24.04.18 16:56) [34]
Да, все верно) Формулу не понял, но мой тестовый стенд показал правильность.
Будет время своим способом попытаюсь вывести твою формулу.
-
>Тимохов Дима © (24.04.18 17:38) [35]
>Будет время своим способом попытаюсь вывести твою формулу.
гугли "формула включений-исключений"
-
Кроме прямого подсчета с раскрытием скобок методом включений-исключений, также легко получить результат по индукции.
-
какие вы все умные))
я вот только аналитически для N=K решил.
и численно для N=K+1.
-
> Sha © (25.04.18 09:38) [37]
> Кроме прямого подсчета с раскрытием скобок методом включений-
> исключений, также легко получить результат по индукции.
Если не сложно, распиши, пожалуйста
-
>DayGaykin © (21.05.18 13:26) [39]
Шар одного из K цветов может оказаться на каждом из N мест. Поэтому имеем всего K^N различных исходов (это первое слагаемое).
Нас интересуют только исходы, использующие шары ровно K цветов. Поэтому из общего числа надо вычесть исходы, содержащие шары K-1 или менее цветов. Если просто вычесть C(K,K-1)*(K-1)^N (это второе слагаемое), то вместе с однократным вычитанием исходов для K-1 цветов мы ошибочно многократно вычтем исходы для K-2 и меньшего числа цветов, поэтому надо компенсировать ошибку. Затем компенсировать ошибку компенсации, и т.д.
Идею легче будет понять, если нарисовать овалы, как обычно это делают, изображая множества для иллюстрации включений-исключений.
-
Вообще эта задача легко решается в 11-мерном многообразии методом Колывагина-Флаха
|
Есть новые 
Нет новых [134427 +34][b:0.001][p:0.005]