Случайный выбор с возвращением

[everdien]

На остановку прибывают автобусы маршрутов 1,2,...,k. Номер маршрута прибывающего автобуса не зависит от номеров других автобусов и может быть любым с одинаковой вероятностью 1/k. Найдите вероятность того, что до появления автобуса маршрута 1 ни на одном из остальных маршрутов не придет более одного автобуса. Найти минимальное значение k, при котором эта вероятность меньше 1/2.

Решение "в лоб": $\dfrac{1}{k} (1 + \dfrac{k-1}{k} + \dfrac{(k-1)(k-2)}{k^{2}} + ... + \dfrac{(k-1)!}{k^{k-1}})$, $k_{\min} = 6$ найти перебором (предварительно показав, что вероятность убывает с ростом k?).

Можно ли записать красивую формулу и/или найти явное выражение?

[svv]

Нет, красивой формулы нет.
Из Вашей формулы видно, что если вероятность для $k$ маршрутов домножить на $k^k$, получится целое число. Для $k=1,2,...$ эти числа образуют последовательность $1, 3, 17, 142, 1569, 21576, ...$.

Я нашёл эту последовательность в OEIS, это A001865. Комментарий показал, что всё сделано правильно:

Цитата:

If one randomly selects a ball from an urn containing n different balls, with replacement, until exactly one ball has been selected twice, the probability that that ball was also the first ball selected once is a(n)/n^n.

Это небольшая переформулировка Вашей задачи — вместо того, чтобы ожидать маршрут №1, мы ждём, пока какой-то маршрут придёт второй раз, с надеждой, что это будет тот же маршрут, что пришёл первым.

В пункте FORMULA приводятся различные формулы, задающие эту последовательность, и наверняка была бы явная формула, если бы она была известна. Но — нет. Всё же Вас могут заинтересовать какие-либо ссылки на результаты, относящиеся к последовательности, посмотрите.