Задача по комбинаторике

muran

Чего-то совсем забылась эта тема. :( Задача следующая.
Есть N корзин, в которые забрасывают M шариков. Необходимо найти вероятность того, что в не менее, чем n корзин попадет не меньше m шариков (т.е в каждой из m или более корзин окажется n или больше шариков).

griz_a

А есть уверенность, что ответ в этой задаче имеет разумное выражение?
Или, наоборот, есть готовность встретить громоздкий ответ?

muran

Есть готовность встретить громоздкий ответ.

griz_a

Тогда как-то так:
Пусть число раскладов, в которых в первых k ящиках по m или более шариков, а в остальных менее m равно [math]$a_k$[/math], [math]$b_k=a_k/(N-k)!$[/math]
Тогда нас интересует число [math]$\sum\limits_{k=n}^{N} C^k_N a_k=N! \sum\limits_{k=n}^{N}  b_k/k!$[/math]
Как найти [math]$b_k$[/math]
Число раскладов, где в первых k ящиках по m шариков,а в остальных сколько угодно, посчитать легко, это [math]$C^{M-1}_{N-km+M-1}$[/math].
С другой стороны, это [math]$\sum\limits_{i=0}^{N-k} C^i_{N-k} a_{k+i}=(N-k)!\sum\limits_{i=0}^{N-k} b_{k+i}/i!$[/math]
вводя [math]$c_k=C^{M-1}_{M-km+N-1}/(N-k)!$[/math], получаем:
[math]$b_N=c_N, b_{N-1}=c_{N-1}-b_{N}, b_{N-2}=c_{N-2}-b_{N}/2-b_{N-1}..$[/math]
Громозека та еще, но сильно проще ничего в голову не пришло.

muran

Спасибо! Уже что-то. На явную формулу надежд мало?

griz_a

одну явную формулу очевидно можно написать:
[math]$\sum\limits_{i_1+...+i_N=M, i_{(N-n+1)}>m} \frac{M!}{i_1! i_2!...i_N!}$[/math] :)
Только радости мало.
Какую-то явную приличную можно я думаю, даже из того, что я написал. Но вот прямо в число - не очень верится

muran

Да, крутая формула)

amarchenkov


Есть N корзин, в которые забрасывают M шариков. Необходимо найти вероятность того, что в не менее, чем n корзин попадет не меньше m шариков
Считаем, что корзины разные, а шарики одинаковые.
Сначала выбираем n корзин из N: [math]$C^n_N$[/math], и наполняем каждую из них m шариками.
Затем оставшиеся M-nm шариков рассыпаем во все N корзин: [math]$C_{M-nm+N-1}^{M-nm}$[/math] *.
Общее число случаев — рассыпать M шариков по N корзинам: [math]$C_{M+N-1}^M$[/math] *.
Ответ:
[math]$C_N^n \cdot C_{M-nm+N-1}^{M-nm}/C_{M+N-1}^M$[/math]
* (могу объяснить, откуда эта формула, если решение правильное) :grin:

Niklz

Если делать тупо, то раскладывание M шариков по N корзинам соответствует перемножению всех скобок в [math]$(z_1+z_2+\dots+z_N)^M$[/math], здесь переменные [math]$z_i$[/math] соответствуют корзинам. Приводя слагаемые имеем коэффициент при отдельном слагаемом - мультиномиальный коэффициент [math]$\binom{M}{k_1, k_2,\dots,k_N}$[/math] - число вариантов разложить шарики по корзинам так, чтобы в первой оказалось [math]$k_1$[/math] шариков, во второй [math]$k_2$[/math] и т.д. Число раскладов, которые тебя интересуют - сумма мультиномиальныхх коэффициентов по таким наборам [math]$(k_1, k_2,\dots,k_N)$[/math] которые удовлетворяют твоему условию. Общее число всех возможных раскладов [math]$N^M$[/math] (получаем подставив [math]$1$[/math] вместо переменных [math]$z$[/math]). Деля число твоих раскладов на общее число раскладов имеем вероятность :)
Кажется, в статфизике это называлось распределение Максвелла-Больцмана и для него выводилась простая асимптотическая (при больших [math]$N, M$[/math]) формула с экспонентами..

griz_a

неправильное. если были n+1 корзина с m шарами, то мы этот расклад два раза считали.
если их было n+2, то - 6 раз
И так далее
to :
Я уже писал формулу с полиномиальными коэффициентами, толку от нее немного.
как могут экспоненты возникнуть - я не понимаю, все параметры обозримые алгебраические, а ответ должен быть рационален, это немного затрудняет использование экспонент.
статфизические распределения, афаик, это пределы при большом числе частиц, а человек хочет ответ, а не предел.
Я думаю, что эту задачу можно какими-нибудь производящими функциями раскрутить, если правильные выбрать, но мне пока не очень досуг

Niklz

Да, не заметил.
А какой тебе еще нужен толк? Это ответ в замкнутом виде - формула по которой считается вероятность.
Фактически, топикстартер хочет посчитать верхний "хвост"(заданной формы) у N-мерного дискретного распределения вероятностей с функцией вероятности
 [math]$P_M(k_1,\dots,k_N) = N^{-M}\binom{M}{k_1,\dots,k_N}$[/math]. Суммирует, получает.
Приближенное выражение для функции распределения при больших [math]$N, M$[/math] будет попроще.
Экспоненты возникнут из-за того, что все комбинаторные величины типа факториала и биномиальных коэффициентов имеют аппроксимации с экспонентами(типа формулы Стирлинга).

griz_a

во-первых, метод в лоб почти всегда неудобен. формула в любом случае упрощается по сравнению с тем, что в лоб написано.
во-вторых, человек, наверное, сам решит, что ему надо. пока про асимптотику, приближение и т.п. не было ни слова
Оставить комментарий
Имя или ник:
Комментарий: