теория вероятности задача , сложная

В алфавите п букв.

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

имеется слово длиной п, каждая буква в нем появляется ровно один раз.

какова вероятность что стерев из х необходимое кол-во букв можно получить это слово.(буквы можно стирать любые)

не понял, почему стереть надо х букв, не сказано же, что 2х = п, надо, наверное, стереть (х - п)букв.
в этом предположении продолжаем.
1. всего возможных вариантов х^п. (1)
2. всего возможных благоприятных вариантов вот столько.
будем генерировать слово в из х букв в два подхода, сначала генерируются буквы нашего п-слова, а затем, все остальные буквы.
вероятность сгенерить нужное нам слово из п букв 1/п^п.
рассчитаем скольки способами мы можем получить возможный вариант дальнейшего получения. возьмем слово из п букв, которое нам надо.
нам надо добавить к нему х-п букв, чтобы получить слово длиной х букв.
всего возможных комбинаций, которые можно добавить (х-п)^п.
теперь надо расставить одну из таких комбинаций. мы можем ставить буквы этой комбинации между буквами нашего данного слова длиной х-п, до и после его букв, т.е. всего к = п + 1 место. а посчитать количество расставлений можно вот так. это все равно, что в к урн расложить м = х - п шаров. а разложить все равно, что в последовательности(т.е. где-то между или до или после можно несколько подряд) из м единиц поставить к - 1 палочеку |. это получается С(k + m - 1, к - 1) - Расстановки с повторениями,
т.е. в итоге всего способов
С(п + 1 + х - п - 1, п + 1 - 1)*(х-п)^п*р(сгенерить нужное нам слово из п букв) = С(х, п)*(х-п)^п/п^п. (1)
а потом делим (2) на (1)

вроде бы, когда п = 1, а х =2, то р = 1, что вроде как правильно. даже, если я где-то ошибку допустил, то все равно мне кажется можно до ума довести и получить правильный ответ.

Сообщение отредактировано: experimenter - 27.11.03, 04:56

Вообще-то, на мой взгляд, все что здесь написано - неверно(не совсем всё. Логика верна)
Во-первых, число возможных комбинаций не x^n, а n^x(разница существенна).
Во-вторых, всего возможных комбинаций, которые можно добавить не (x-n)^n,а n^(x-n)(такаяже ошибка).
Сочетать надо n элементов из x (C(x,n)),а можно (x-n) элементов из x т.е. (C(x,x-n)). Результат одинаков.
В итоге получаем следующее:

      x-n                     x-n
     n     *  C(x,x-n)       n     *  C(x,n)
P = -------------------  =  ----------------- ;
             x                      x
           n                      n
          
где
               x!
C(x,x-n)= --------------
           n! *  (x-n)!
          
               x!
C(x,n)= --------------
         (x-n)!  *  n!

вот, где-то так.


Можно и так посчитать.

          x!
P = ---------------
                 x
    (x-2)!  *  n

Но уж если говорить на чистоту, это тот же способ, только я сократил выражение, упростив его.

Цитата WargaL @ 04.08.07, 09:20

Можно и так посчитать.

          x!
P = ---------------
                 x
    (x-2)!  *  n

Нельзя так посчитать
Подставьте x=3, n=2
Этот случай легко проверить на бумажке - должна получиться вероятность 1/2
А по этой формуле получается 3/4

сорри. Я щас и сам заметил. Спасибо. При упрощении ошибся.
Тут такая бяка получается:

            x!
P = -------------------
                     n
     n! * (x-n)! * n

Сообщение отредактировано: WargaL - 04.08.07, 13:58

Так снова 3/4 получается

esperanto
нужна целочисленная формула или асимптотичеcкая зависимость при больших x?

Вы не забывайте, что вычеркивания можно производить по-разному.
так слово "ab" из слова "abb" можно получить двумя способами, вычеркнув вторую или третью букву.

а по описанному алгоритму получаются слова
aab, aab, aba
bab, abb, abb

Легко заметить, что первое и второе слова совпадают, также как и пятое-шестое. Отсюда и вероятность больше в полтора раза.
Увеличивая длину слов таким подсчетом можно, думаю, вообще получить вероятность больше 1.

---

В принципе можно считать что искомая строка - это просто все символы записанные подряд. На результат это не повлияет.

Пусть Pn(m,k) вероятность того, что из произвольной строки длиной k можно указанным способом выбрать m необходимых.
Тогда имеем:
Pn(m,k) = 0, для m > k
Pn(m,m) = 1/n^m, т.к. cуществует лишь одна строка необходимой длины из n^m возможных
P(m,k) = 1/n*Pn(m-1,k-1) + (n-1)/n*P(m,k-1) = (Pn(m-1,k-1) + (n-1)*P(m,k-1))/n
Либо первый символ строки можно принять, либо придется искать в укороченной строке

Существует достаточно эффективный алгоритм вычисления этой функции (типа треугольника Паскаля), сложности порядка O(m*k), требующий O(m) памяти.

Сообщение отредактировано: amk - 10.08.07, 12:03

Цитата amk @ 06.08.07, 11:53

Существует достаточно эффективный алгоритм вычисления этой функции (типа треугольника Паскаля), сложности порядка O(m*k), требующий min(m,k) памяти.

Сложность O(k-m+ln(n)), память O(1)

Го_
поделишься?

Из рекуррентной формулы следует
P(m,k)= сумма по i от 0 до k-m от C(k,i) * (n-1)^i /n^k