-
Есть шарики 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 равна нулю,
> насколько бы эти числа не отличались)
Будет время, сделаю. Все же "завело" меня то, что из количественного численного анализа можно получить качественный вывод.
Чувствуешь себя ученым))) Гипотезы и т.д.
|
Есть новые 
Нет новых [118410 +25][b:0][p:0.003]