Здравствуйте! Подскажите решение:
Найти число разложений n различных шаров по k различным ящикам при условии того, что ящики не могут быть пустыми.
Я посчитал число разложений для ситуации когда возможно существование пустых ящиков. Считал так:
первый шар может попасть в любой из k ящиков, второй шар также в любой из k ящиков и т.д. По
правилу умножения имеем
k*k*k*...*k и так n раз. Получаем k в степени n.
Но это число включает и все те случаи, когда один или несколько ящиков пусты.
Что делать? Считать все эти варианты вычитать их? А как это сделать?
Как быть? Подскажите..
Формула включения - исключения поможет: введите события A(i) = {i-й ящик пуст}. Их объединение есть событие A = A(1) U ... U A(k) = {хотя бы один ящик пуст}. Число слагаемых в объединении пересекающихся событий считается по формуле включения - исключения:
|A| = sum |A(i)| - sum |A(i)*A(j)| + sum |A(i)*A(j)*A(m)| - ... +(-1)^{k-1}*|A(1)*...*A(k)|,
где в первой сумме i=1..k, во второй 1 <= i < j <= k; в треьтей 1 <= i < j < m <= k и т.д.
Ну или с учётом того, что |A(i)| от i не зависит, |A(i)*A(j)| от i, j не зависит и т.д.,
|A| = k*|A(1)| - C(k,2)*|A(1)*A(2)| + C(k,3)*|A(1)*A(2)*A(3)| - ...
На всякий случай (лень - естественное качество человека): других способов решить это _нет_.
Спасибо! Воспользовался вашей подсказкой и решил задачу..
Русская версия Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)