• картман © (20.04.18 11:00) [0]
    Есть шарики k цветов. Вероятность выпадения шарика любого цвета - одинакова и со временем не меняется. Последовательно выбирается n шаров.
     Какова вероятность того, что в выборке присутствуют шары всех цветов?
  • Pavia © (20.04.18 18:56) [1]
    100 % так как хотя выпадают они случайно, но про выбираются ничего не сказано. Выбирающей может специально отбрасывать неподходящие.
  • kilkennycat © (20.04.18 21:18) [2]
    50% - либо присутствуют, либо нет.
  • SergP © (20.04.18 22:01) [3]
    если n<k то 0%
  • ухты © (20.04.18 23:51) [4]
    это какие шары, из ореха чтоли?
  • Тимохов Дима © (21.04.18 16:21) [5]
    для 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.
  • картман © (21.04.18 17:55) [6]

    > Ключевые слова - сочетание, перестановка, размещение.

    есть еще термин - ключевой-таки))
  • Тимохов Дима © (21.04.18 18:07) [7]
    Ну вообще задача сложная. Думал для фана сделать. Что-то не сдюжил.
    Могу только кодом экспериментальной проверки поделиться)))


    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;

  • Тимохов Дима © (21.04.18 18:16) [8]
    А тебе вообще зачем это?

    ЗЫ
    Тут понятно, как делать.
    Например, К=3, N = 4.
    Выписываешь все успешные комбинации из четырех шаров (из трех - понятно, это К!/К^К - кол-во успешных кобинаций это размещение от K, т.к. K!, 1/K - вероятность конкретного шара, 1/K^K - вероятность конкретной последовательности в одной успешной комбинации).

    1123
    1132
    1213
    1223
    1332
    1312
    21...
    22...
    23...
    31...
    32...
    33...

    Пытаешься понять, что тут за комбинаторика.
    Потом для N=5 и т.д.

    Думаю, мат индукцией тут что-то нарисуется.
    Но что-то не соображу на коленке, думать шибко нада....
  • картман © (21.04.18 20:31) [9]

    > А тебе вообще зачем это?

    пятничная задачка - я решил, по работе нужно было.
  • Mystic © (21.04.18 21:06) [10]
    Я бы рекуррентно решал.

    Пусть 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, упростить, ...
  • картман © (21.04.18 21:26) [11]

    > Но что-то не соображу на коленке, думать шибко нада....

    допустим, в группе из 100 человек 60 любят пиво, 40 - вино, 30 - водку. Пиво и вино любят 20 человек. Вино и водку - 15, пиво и водку - 10. Пиво, вино и водку - 10. Сколько трезвенников?

    n := 100 - 60  - 40 - 30.
    Но тут мы вычли по два раза тех, кто любит оба напитка, тогда нужно их прибавить:
    n := n + 20 + 15 + 10
    а теперь мы лишний раз приплюсовали любителей всего, значит:
    n := n - 10

    +-+-...
  • Тимохов Дима © (21.04.18 22:24) [12]

    > картман ©   (21.04.18 21:26) [11]

    Я пас)
    Будут формулы, поставлю в мой код выше. Проверим)
    Пока понаблюдаю.
  • Тимохов Дима © (21.04.18 22:35) [13]

    > картман ©   (21.04.18 21:26) [11]
    > допустим, в группе из 100 человек 60 любят пиво, 40 - вино,
    >  30 - водку. Пиво и вино любят 20 человек. Вино и водку
    > - 15, пиво и водку - 10. Пиво, вино и водку - 10. Сколько
    > трезвенников?

    Вроде 5.
    (наверное младенцы)
  • Тимохов Дима © (22.04.18 13:04) [14]

    > картман ©   (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 тоже можно подбором формулу увидеть. А потом по индукции доказать в общем случае.
  • картман © (22.04.18 16:25) [15]

    > 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 17:10) [16]

    > Це из ка по два.

    из ка плюс один
  • Тимохов Дима © (22.04.18 18:23) [17]

    > картман ©   (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.
  • картман © (22.04.18 20:54) [18]
    Шикарно)) осталось для любого случая(там, кстати, сумма с интересными свойствами получается: при к > n равна нулю, насколько бы эти числа не отличались)
  • Тимохов Дима © (22.04.18 20:56) [19]

    > картман ©   (22.04.18 20:54) [18]
    > Шикарно)) осталось для любого случая(там, кстати, сумма
    > с интересными свойствами получается: при к > n равна нулю,
    >  насколько бы эти числа не отличались)


    Будет время, сделаю. Все же "завело" меня то, что из количественного численного анализа можно получить качественный вывод.
    Чувствуешь себя ученым))) Гипотезы и т.д.
  • SergP © (23.04.18 01:12) [20]

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

    Вот только как теперь с него сделать общую формулу - пока не придумал.
  • SergP © (23.04.18 10:28) [21]
    В таком виде понятнее должно быть:
    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;
  • KSergey © (24.04.18 09:06) [22]
    Всегда было любопытно: почему большинство задач - про комбинаторику и т.п. тервер?
    у кого-то в жизни встречаются такого рода задачи? или это просто типичная тема для интеллектуалов, типа как шахматы?
    в самом деле интересно (про реальные задачи у вас на работе, связанные с этим)
  • картман © (24.04.18 11:41) [23]

    > в самом деле интересно (про реальные задачи у вас на работе,
    >  связанные с этим)



    > картман ©   (21.04.18 20:31) [9]
    >
    >
    > > А тебе вообще зачем это?
    >
    > пятничная задачка - я решил, по работе нужно было.
  • KSergey © (24.04.18 11:45) [24]
    В какой области жизнедеятельности применяется ваш софт?
  • картман © (24.04.18 12:34) [25]
    логистика
  • картман © (24.04.18 12:39) [26]
    в общем, такая вот формулка получается: https://yadi.sk/i/P2A-0_Zv3UiLtc
  • картман © (24.04.18 12:45) [27]
    интересно, что числитель при k>n равен нулю))
  • SergP © (24.04.18 13:04) [28]
    А можно интереса формулу сюда написать, или выложить на что-то более доступное? А то самому интересно, но яндекс у нас в/на Украине заблокирован, а искать какой-нить прокси-сервер или делать что-то другое для обхода - как-то лень.
  • xayam © (24.04.18 13:16) [29]

    > а искать какой-нить прокси-сервер или делать что-то другое
    > для обхода - как-то лень

    во времена, когда блокируют рутрекер и телеграм, прокси должны быть под рукой :)
  • SergP © (24.04.18 14:04) [30]

    > во времена, когда блокируют рутрекер и телеграм, прокси
    > должны быть под рукой :)


    Ок. ты меня убедил. Пришлось найти все-таки проксик. Посмотрел формулу.
  • Тимохов Дима © (24.04.18 15:00) [31]

    > картман ©   (24.04.18 12:39) [26]
    > в общем, такая вот формулка получается: https://yadi.sk/i/P2A-
    > 0_Zv3UiLtc

    C - это что?

    C(n,k) = n! * / (k!*(n-k)!)

    ?
  • KSergey © (24.04.18 15:42) [32]
    > SergP ©   (24.04.18 14:04) [30]
    > Ок. ты меня убедил. Пришлось найти все-таки проксик.

    Opera с её vpn
    Самое простое и готовое "из коробки"
    поражаюсь тому, что её не блокируют
  • SergP © (24.04.18 16:44) [33]

    > KSergey ©   (24.04.18 15:42) [32]


    Да просто не так часто и бывает необходимость лазить по яндексу, за время действия блокировки он мне первый раз понадобился... Ну и еще ранее один раз была необходимость зайти на сайт drweb.  Посему и не обзавелся чем-нить постоянным для обхода блокировки, оба раза просто искал прокси, находил и заходил через них. А что касается остального заблокированного, то вконтакте и одноклассники мне и не нужны (вообще не перевариваю такие вещи, как вконтакте, одноклассники, твиттер, фейсбук, телеграм, и прочие, т.е. все что называется "социальные сети"). А mail.ru - ИМХО вообще правильно сделали, что заблокировали (вот только потом его почему-то разблокировали), ибо это рассадник различной гадости, той что в инете люди называют "вирусы от mail.ru" (спутник, "браузер" Амиго и пр.). А все остальные российские сайты, которые бывают мне нужны нормально работают, их никто не блокировал.
  • картман © (24.04.18 16:56) [34]

    > C(n,k) = n! * / (k!*(n-k)!)

    да
  • Тимохов Дима © (24.04.18 17:38) [35]

    > картман ©   (24.04.18 16:56) [34]

    Да, все верно) Формулу не понял, но мой тестовый стенд показал правильность.
    Будет время своим способом попытаюсь вывести твою формулу.
  • Sha © (24.04.18 17:55) [36]
    >Тимохов Дима ©   (24.04.18 17:38) [35]
    >Будет время своим способом попытаюсь вывести твою формулу.

    гугли "формула включений-исключений"
  • Sha © (25.04.18 09:38) [37]
    Кроме прямого подсчета с раскрытием скобок методом включений-исключений, также легко получить результат по индукции.
  • Тимохов Дима © (25.04.18 11:11) [38]
    какие вы все умные))
    я вот только аналитически для N=K решил.
    и численно для N=K+1.
  • DayGaykin © (21.05.18 13:26) [39]

    > Sha ©   (25.04.18 09:38) [37]
    > Кроме прямого подсчета с раскрытием скобок методом включений-
    > исключений, также легко получить результат по индукции.

    Если не сложно, распиши, пожалуйста
  • Sha © (21.05.18 23:07) [40]
    >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 и меньшего числа цветов, поэтому надо компенсировать ошибку. Затем компенсировать ошибку компенсации, и т.д.

    Идею легче будет понять, если нарисовать овалы, как обычно это делают, изображая множества для иллюстрации включений-исключений.
  • aka © (22.05.18 20:10) [41]
    Вообще эта задача легко решается в 11-мерном многообразии методом Колывагина-Флаха
Есть новые Нет новых   [118236   +9][b:0][p:0.003]