Метод шаров и перегородок: формулы и примеры

Метод шаров и перегородок - способ посчитать, сколькими путями можно распределить одинаковые предметы по различимым ячейкам. Он переводит задачу в выбор позиций для разделителей в последовательности. Например, пять одинаковых шаров можно разложить по трём пронумерованным коробкам 21 способом, если пустые коробки допустимы, и шестью способами, если каждая должна получить шар. Эти ответы различаются из-за условия, а не из-за порядка вычислений. В калькуляторе можно менять числа и сравнить оба случая.
Как работает представление шарами
Пусть есть пять одинаковых шаров и три коробки: первая, вторая и третья. Выложим шары в ряд и поставим две перегородки. Шары до первой перегородки попадут в первую коробку, между перегородками - во вторую, а после второй - в третью. Так запись обозначает распределение .
Если перегородка стоит у начала или конца ряда, крайняя коробка пуста. Соседние перегородки означают пустую среднюю коробку: например, соответствует . Пустая коробка здесь не ошибка, пока условие её не запрещает.
Самое важное - взаимно однозначное соответствие. По последовательности легко восстановить количества в коробках. И наоборот, для любого набора количеств с суммой пять можно записать единственную последовательность: сначала нужное число шаров, затем разделитель, затем шары второй коробки и так далее. Поэтому подсчёт последовательностей даёт ровно число распределений: ни одно не пропущено и не посчитано дважды.
Формула для неотрицательных количеств
Пусть одинаковых шаров распределяют по различимым ячейкам, причём , , и оба числа целые. Для ячеек нужно перегородок. Всего в ряду позиций; достаточно выбрать из них места перегородок. Получаем число распределений:
Обе записи равны: можно выбирать позиции перегородок или оставшиеся позиции шаров. Это обычное сочетание: порядок выбранных позиций сам по себе не важен. Но порядок ячеек важен: и - разные результаты, потому что коробки различимы.
Для пяти шаров и трёх коробок в последовательности семь позиций, из которых две занимают перегородки. Значит, . При одной коробке перегородок нет и ответ всегда равен единице. При нуле шаров и разрешённых пустых коробках тоже ровно одно распределение: все количества равны нулю.

Если каждая ячейка должна быть непустой
Теперь требуем, чтобы в каждой коробке лежал хотя бы один шар. Если , это невозможно: ответ равен нулю. При сначала положим по одному шару в каждую коробку. Останется одинаковых шаров, которые можно распределять уже без ограничений на пустоту. Формула предыдущего раздела даёт
В примере после обязательной раздачи остаются два шара. Их распределяют по трём коробкам способами. После возврата обязательных шаров получаются тройки , , , , и .
Есть и второй взгляд: между пятью шарами имеются четыре внутренних промежутка. Если поставить две перегородки в разные промежутки, каждая коробка получит шар. Выбор двух промежутков из четырёх снова даёт . Ставить перегородки на концах или вместе в одном промежутке здесь нельзя: возникла бы пустая коробка.
Уравнения и нижние границы
Число распределений равно числу целочисленных решений уравнения при : переменная просто обозначает количество шаров в -й ячейке. Это позволяет перейти от рисунка к алгебре, не меняя сути задачи.
Если заданы нижние границы , где все целые, сделаем замену . Тогда , а их сумма равна . При решений нет; при их . Замена обратима: к каждому снова прибавляем соответствующее .
Например, для при , , сначала резервируем три единицы. Остаётся , поэтому ответ равен . Важно вычесть именно сумму обязательных минимумов, а не просто число переменных.
Верхние границы и неравенства
Обычная формула не учитывает вместимость коробок. Допустим, в примере с пятью шарами первая коробка вмещает не более двух. Из 21 распределения исключаем те, где в ней не меньше трёх. После резервирования трёх шаров в первой коробке остаются два свободных шара; запретных распределений . Значит, допустимых .
Если верхних границ несколько, простое вычитание каждого нарушения может дважды удалить распределения, нарушающие сразу два условия. Тогда нужен подсчёт пересечений, например принцип включений и исключений. Сначала полезно проверить маленький пример перебором: это выявляет ошибки в границах и повторном учёте.
Для неравенства с неотрицательными целыми переменными можно ввести остаток . Он показывает, сколько единиц не использовано. Получается равенство с переменными и ответ . Этот приём работает, когда остаток действительно может быть любым неотрицательным целым числом. Пример такой дополнительной ячейки приведён в решениях MIT.
Когда модель подходит в программировании
В задачах на алгоритмы переменные могут означать число одинаковых заданий в разных очередях, количество одинаковых единиц памяти по модулям или частоты символов. Если важны только количества, сумма фиксирована и дополнительные ограничения отсутствуют, метод сразу даёт число допустимых векторов. Его можно использовать и как проверку программы полного перебора: число сгенерированных векторов должно совпасть с формулой.
Но если задания различимы и важно, какое именно попало в какую очередь, модель меняется. Для каждого из различимых заданий выбирают одну из очередей, получая назначений при разрешённых пустых очередях. Такой подсчёт опирается на правило произведения. Одинаковые шары в исходной модели не имеют личных меток, и их перестановка внутри коробки нового результата не создаёт.
Связь с перестановками с повторениями тоже полезна: последовательность состоит из одинаковых шаров и одинаковых разделителей. Однако здесь смысл ответа задаёт соответствие с пронумерованными коробками. Если сами коробки неразличимы, перестановка их содержимого может не создавать нового распределения, и стандартная формула уже не подходит.
Как выбрать модель перед подсчётом
Перед расчётом полезно выписать результат в виде вектора и спросить, какие изменения делают его новым. Если имеет значение последовательность выбранных объектов, а не только их количества, рассмотрите размещения: там порядок может менять ответ. Для проверки модели возьмите крайний случай с одной ячейкой или без шаров и перечислите варианты вручную. Ещё один тест - убедиться, что сумма всех координат каждого вектора равна заданному числу. Формула удобна именно после такого перевода условий: она не заменяет анализ того, что считается различным исходом и какие ограничения действительно действуют.
Рассмотрим распределение четырёх одинаковых токенов между двумя процессами. Вектор означает, что первому процессу не досталось ни одного токена; вектор описывает другую ситуацию, так как процессы имеют разные роли. Всего возможны пять векторов: первая координата принимает значения от нуля до четырёх, а вторая определяется остатком. Формула даёт тот же ответ: . Если оба процесса должны получить токен, остаются три вектора, и ответ совпадает с .
Этот небольшой пример помогает заметить, откуда берётся каждая позиция в последовательности. Четыре позиции занимают токены, пятая - единственная перегородка. Её можно поставить перед всеми токенами, после них или в любой из трёх промежуточных точек. В непустом варианте крайние позиции исключаются. Для большого числа ячеек аналогичное перечисление становится громоздким, но выбор позиций перегородок по-прежнему однозначно определяет результат.
В программе удобно проверять границы до обращения к формуле: число ячеек должно быть положительным, число шаров - неотрицательным целым. При требовании непустоты отдельно обработайте случай, когда шаров меньше ячеек. Для больших параметров биномиальный коэффициент быстро растёт: практической реализации могут понадобиться целочисленная арифметика произвольной точности или вычисление по модулю. Округление чисел с плавающей точкой не обеспечивает точный ответ при сколь угодно больших входных данных.
Частые ошибки
- Использовать перегородок для коробок. В ряд нужны только внутренних разделителей.
- Запрещать соседние перегородки без основания. Они нужны для представления пустых внутренних коробок.
- Применять формулу непустых ячеек при . В этом случае ответ ноль; формулу с отрицательными верхними индексами использовать не нужно.
- Не проверить различимость предметов и ячеек. Различимые предметы или неразличимые коробки задают другую задачу.
- Игнорировать предел вместимости. Верхние границы требуют дополнительного подсчёта запрещённых вариантов.
FAQ
Почему перегородок на одну меньше, чем ячеек?
Два края ряда уже ограничивают крайние ячейки. Каждая внутренняя перегородка добавляет ещё одну ячейку: одна разделяет ряд на две части, две - на три.
Можно ли считать сочетания с повторениями?
Да. Выбор предметов из видов с повторениями и без учёта порядка задаётся количествами предметов каждого вида. Это те же неотрицательные решения с суммой , поэтому их число равно .
Все ли распределения одинаково вероятны?
Нет, формула считает варианты и сама по себе не задаёт вероятность. Если каждый различимый шар независимо попадает в случайную коробку, разные векторы количеств могут возникать разным числом назначений. Модель случайного выбора надо задать отдельно.
Коротко
Шары кодируют одинаковые предметы, а перегородок отделяют различимых ячеек. При разрешённых нулях ответ равен ; при положительных количествах и - . Перед вычислением проверьте различимость, допустимость пустых ячеек и все границы: именно они определяют модель.
Читайте также

Тождество Вандермонда: формула и доказательство
Тождество Вандермонда связывает сумму произведений биномиальных коэффициентов с одним сочетанием. Разбираем доказательства, пример и применение в вероятности.

Вероятность через сочетания: формула и разбор
Как считать вероятность через сочетания: классическая формула, число сочетаний в числителе и знаменателе, разбор задач про урну, лотерею и карты с пошаговым решением.

Числа Белла: разбиения множества и формула
Числа Белла считают разбиения множества на непустые группы. Разбираем подробные примеры, рекуррентную формулу, связь с числами Стирлинга и алгоритм вычисления.

Диаграммы Юнга: разбиения, таблицы и формула крюков
Диаграммы Юнга на примерах: как построить форму разбиения, получить сопряжённую диаграмму и посчитать стандартные таблицы с помощью формулы крюков на подробном примере.

Комбинаторика: размещения и формулы подсчёта
Размещения в комбинаторике: как учитывать порядок и повторения, вывести формулу, решить задачи с ограничениями и проверить ответ на конкретных примерах с разбором.

Мультимножество: кратности, операции и примеры
Мультимножество простыми словами: как считать кратности, отличать сумму от объединения, находить пересечение и разность, работать с повторами в Python и решать задачи.