Условие
Четыре различных задания распределяют между тремя различными исполнителями. Каждый исполнитель должен получить хотя бы одно задание. Сколько распределений?
Решение по шагам
Без ограничения каждый из четырёх объектов имеет три адресата: 3⁴=81. Если конкретный исполнитель пуст, остаётся 2⁴ способов. Вычитаем три таких случая. Распределение, в котором два исполнителя пусты, было вычтено дважды, поэтому прибавляем три выбора единственного исполнителя: 81−3·16+3=36.
Иной взгляд: размеры непустых групп обязательно равны 2,1,1. Выбираем пару заданий C(4,2)=6 способами, затем назначаем три группы исполнителям 3! способами.
Проверка результата
6·6=36; перебор всех 81 отображений с проверкой числа разных значений также оставляет 36.
Типичная ошибка
Задания и исполнители различимы. Если убрать различимость групп, получится число разбиений множества, которое здесь равно 6, а не 36.
Что даёт этот метод
Число сюръекций на k значений выражается суммой Σ(−1)ʲC(k,j)(k−j)ⁿ и равно k!·S(n,k), где S — число разбиений множества.
Дальше по теме
Комбинаторика и дискретная математика: другие задачи и разборы.
Учебное условие и объяснение сформулированы редакцией damirock.com. Это самостоятельный разбор, а не официальный билет или ключ экзамена. Числа относятся к модели задачи.