Здравствуйте! Подскажите решение:

Найти число разложений 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)| - ...

На всякий случай (лень - естественное качество человека): других способов решить это _нет_.

Спасибо! Воспользовался вашей подсказкой и решил задачу..