Корзины и шары

[Padawan]

В $n$ корзин случайным образом кидаются шары. Кидаются до тех пор, пока в одной из корзин не станет $m$ шаров. Сколько в среднем шаров придется бросить?

[PAV]

Ну, без особого труда можно выписать ее в виде набора вложенных сумм, но можно ли их свернуть во что-то красивое - не знаю.

Может быть, будут полезны такие замечания. Задачу можно инвертировать так, что изначально в каждой корзине лежат по $m$ шаров, и на каждом шаге из случайной корзины шар извлекается. А это уже очень похоже на известную задачу Банаха о спичечных коробках (только там их всего 2).

-- Сб янв 07, 2012 23:10:29 --

Самая внутренняя из этих сумм имеет вид

$$ \sum_{x=0}^{m-1}(a+x)\frac{(a+x)!}{a!x!}\left(\frac1n\right)^x $$

Если с ней можно что-то хорошее сделать, тогда возможно что-то получится.
Или какой-нибудь трюк надо искать.

[Padawan]

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

[PAV]

Если не наврал, то вроде так:

$$ \sum_{t=1}^n\sum_{k_1=0}^{m-1}\cdots\sum_{k_{n-1}=0}^{m-1}(m+k_1+\cdots+k_{n-1})\frac{(m+k_1+\cdots+k_{n-1})!}{m!k_1!\cdots k_{n-1}!} \left(\frac1n\right)^{(m+k_1+\cdots+k_{n-1})} $$

[--mS--]

Посмотрите вот эту статью http://www.mathnet.ru/php/archive.phtml ... n_lang=rus

[PAV]

Точно, это похоже ровно то, что нужно.

[Padawan]

--mS--, PAV

Спасибо!