Вероятность и статистика · объяснение и практика
Как включения и исключения считают распределения без пустых ящиков
Посчитайте размещения различимых объектов по подписанным ящикам без пустых: включения и исключения исправят многократное вычитание.

В теме Комбинаторика и пространство исходов · Учебная карта
Главная мысль
Для n≥1 различимых объектов и m≥1 подписанных ящиков число размещений без пустых равно Σ от j=0 до m величин (−1)ʲC(m,j)(m−j)ⁿ. При независимом равномерном выборе ящика вероятность — это число, делённое на mⁿ.
Объявите, что различимо
Каждый из n объектов выбирает ровно один из m подписанных ящиков. В ящике разрешено любое количество объектов, порядок внутри не важен. Всего функций размещения mⁿ: для каждого объекта есть m вариантов. Подписи ящиков и различимость объектов важны; для одинаковых предметов или неподписанных ящиков общий счёт был бы другим.
Нужны размещения, в которых каждый ящик непуст. Если объектов меньше ящиков, таких размещений нет по принципу ящиков. Но при достаточном числе объектов простая формула сочетаний с повторениями не подходит: она описывает другие объекты и не учитывает, какой конкретно различимый предмет куда попал.
Пустые ящики образуют пересекающиеся события
Для одного заранее названного пустого ящика все объекты выбирают из m−1 оставшихся, то есть имеется (m−1)ⁿ вариантов. Таких ящиков m. Однако размещение с двумя пустыми было бы вычтено дважды, поэтому парные пересечения надо добавить. При j выбранных пустых ящиках остаётся (m−j)ⁿ размещений, а выбрать их можно C(m,j) способами.
Для четырёх объектов и трёх ящиков получается 3⁴−3·2⁴+3·1⁴=36. Если каждый объект независимо выбирает ящик равновероятно, общий счёт 81 и вероятность равна 4/9. Это не требование одинакового числа объектов в ящиках: составы два, один, один подходят в любом разрешённом порядке объектов.
Пример
Пять различимых объектов независимо выбирают один из трёх подписанных ящиков равновероятно. Найдите вероятность отсутствия пустых.
Число подходящих размещений 3⁵−3·2⁵+3=150. Делим на 243 и получаем 50/81. Различные размещения одинаковых численностей всё ещё различаются по составу объектов.
Формула счёта не заменяет вероятности при иных весах
Если ящики выбираются с разными вероятностями, размещения не равновероятны, поэтому деление количества на mⁿ уже неверно. Принцип включений и исключений сохраняется для вероятностей событий, но вклад конкретного набора пустых ящиков выражается через сумму вероятностей остальных. Нужно заново учесть веса, а не только число доступных ящиков.
Ограничение вместимости также меняет задачу. Наша модель допускает, что все объекты оказались в одном ящике, и исключает этот исход только условием непустоты остальных. Для ящиков с максимумом один предмет требуются инъекции, а не текущая формула. Поэтому перед подсчётом записывают, разрешены ли повторы выбора и какие размещения считаются различными.
От чтения к действию
А теперь — вы
Частые вопросы
Можно ли использовать формулу для одинаковых объектов?
Нет без переосмысления. Здесь каждый объект различим, и функция его назначения ящику задаёт отдельное размещение.
Непустые ящики означают поровну объектов?
Нет. В каждом должен быть хотя бы один, но численности могут различаться. Равномерность выбора не означает равенства итоговых количеств.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Как посчитать перестановки без единого совпадения с исходным местом
Посчитайте перестановки, в которых ни один различимый предмет не остаётся на своём месте, и не путайте их с одним общим циклическим сдвигом.
Открыть темуКак считать состав независимых исходов трёх категорий
Посчитайте состав трёх категорий в независимых испытаниях: отделите вероятность одной упорядоченной строки от числа таких строк.
Открыть тему