Задача про вероятность совпадения

[kuraga]

Задается $n\in\mathbb N$ машинных слов из алфавита мощности $p$ со случайно выбранными длинами $l_1,\dots,l_n$, причем каждая буква слова также выбирается случайно и $\sum_{k=1}^n l_k = L, \quad 1\leq l_k\leq l_\text{max}\leq L$. Найти вероятность того, что в тексте найдется хотя бы одна пара равных слов.

Помогите пжл, я только начал изучать тервер, а нахождение ответа к этой задаче есть иллюстрация к задаче по программированию. Если длины равны, то более менее ясно. А так - мне нет. Какую тему глянуть?

[Хорхе]

Задача скорее не по ТВ, а по комбинаторике.

Я правильно понимаю задачу: сначала случайно выбирается набор длин $l_1,\dots,l_n$ из наборов, удовлетворяющих выписанному ограничению, а затем для каждой длины $l_k$ случайно выбирается слово такой длины?

Если так, то задача довольно-таки убойная. На красивый ответ никакой надежды, разве что могу выписать производящую функцию, но тоже приятного мало (там будет фигурировать экспонента Пойя).

[maxal]

Если проигнорировать $l_{max}$, то всего различных текстов из $n$ слов общей длины $L$ равно $\binom{L+n-1}{n-1} p^L$. Ну а количество таковых без одинаковых слов можно найти с помощью принципа включения-исключения.

[Circiter]

2kuraga
Вы пробовали как-нибудь задействовать марковские цепочки?

[kuraga]

Я не знаю еще ничего Я ж и хочу узнать, на какую тему эта задача. Скорее всего, я вернусь к ней позже, под изучение этой темы.