Математика · объяснение и практика

Как распределить одинаковые предметы с нижними границами

Как учесть разные минимальные количества в распределении одинаковых предметов, снять нижние границы заменой переменных и проверить невозможный остаток.

Синяя и оранжевая половины складываются в целый круг.

В теме Доказательства и комбинаторные модели · Учебная карта

В маршруте Счёт через устройство объектов · 10 тем

Главная мысль

Из каждой переменной вычитают её обязательный минимум. Оставшиеся неотрицательные количества суммируются в остаток N−Σlᵢ, который распределяют методом звёзд и перегородок.

Сначала обеспечить обязательные запасы

Пусть одинаковые жетоны распределяют по трём подписанным коробкам. В первой должно быть не меньше двух, во второй не меньше одного, в третьей не меньше трёх. Если всего десять жетонов, шесть уже заняты обязательными запасами. Остаётся свободно распределить четыре, и разрешено оставить любую коробку без дополнительных жетонов.

Введём y₁=x₁−2, y₂=x₂−1, y₃=x₃−3. Все новые переменные неотрицательны и имеют сумму четыре. Обратное преобразование возвращает минимумы, поэтому между допустимыми исходными распределениями и новыми тройками существует биекция. Мы не предполагаем равенства обязательных количеств и не заменяем разные ограничения одним общим.

От остатка к перегородкам

Неотрицательную тройку с суммой четыре можно изобразить четырьмя звёздами и двумя перегородками. Число звёзд до первой, между перегородками и после второй задаёт количества. Соседние перегородки разрешены: они означают ноль в соответствующей коробке. Поэтому способов C(4+3−1,3−1)=C(6,2)=15.

Для k подписанных коробок и остатка R≥0 формула становится C(R+k−1,k−1). При R=0 есть единственный вариант, когда все получают ровно минимумы. При отрицательном остатке вариантов нет: обязательные требования уже превышают имеющийся запас. Формулу с отрицательным аргументом в таком случае не применяют.

Пример

Двенадцать одинаковых карточек распределяют по четырём подписанным папкам с минимумами 1,2,0,3. Сколько распределений?

Минимумы занимают 6 карточек, остаток равен 6. Число неотрицательных четвёрок с суммой 6 равно C(9,3)=84. Возвращение минимумов однозначно восстанавливает исходный вариант.

Каких ограничений замена не снимает

Если у коробки есть ещё максимальная вместимость, после вычитания минимума верхняя граница остаётся. Например, исходное x₁≤5 при минимуме два превращается в y₁≤3. Обычная формула включает и запрещённые превышения. Их можно исключить дополнительным подсчётом либо использовать порождающее произведение с конечным числом разрешённых степеней.

Не менее важно различать одинаковые жетоны и разные карточки. Здесь учитывается только количество в каждой коробке, а не личность предметов. Для различимых объектов каждая численная тройка могла бы соответствовать нескольким распределениям. Неподписанные коробки тоже меняют задачу: перестановка количеств между ними перестаёт создавать новый вариант и требует иной модели.

От чтения к действию

А теперь — вы

Четырнадцать одинаковых жетонов распределяют по четырём подписанным коробкам с минимумами 2,1,2,1. Сколько вариантов без верхних границ?

Частые вопросы

Почему коробки должны быть подписанными?

Координаты x₁,…,xₖ различают коробки. Если перестановка коробок не меняет распределение, формула звёзд и перегородок считает лишние варианты.

Нужен ли отдельный разбор остатка ноль?

Он полезен как проверка: формула даёт один вариант, и это ровно обязательные минимумы во всех коробках.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться