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

В теме Доказательства и комбинаторные модели · Учебная карта
В маршруте Счёт через устройство объектов · 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. Обычная формула включает и запрещённые превышения. Их можно исключить дополнительным подсчётом либо использовать порождающее произведение с конечным числом разрешённых степеней.
Не менее важно различать одинаковые жетоны и разные карточки. Здесь учитывается только количество в каждой коробке, а не личность предметов. Для различимых объектов каждая численная тройка могла бы соответствовать нескольким распределениям. Неподписанные коробки тоже меняют задачу: перестановка количеств между ними перестаёт создавать новый вариант и требует иной модели.
От чтения к действию
А теперь — вы
Частые вопросы
Почему коробки должны быть подписанными?
Координаты x₁,…,xₖ различают коробки. Если перестановка коробок не меняет распределение, формула звёзд и перегородок считает лишние варианты.
Нужен ли отдельный разбор остатка ноль?
Он полезен как проверка: формула даёт один вариант, и это ровно обязательные минимумы во всех коробках.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Как взаимно однозначное соответствие доказывает равенство количеств
Как доказать равенство количеств без прямого перечисления, построить обратное соответствие и заметить потерянные или склеенные объекты при кодировании.
Открыть темуКак коэффициент произведения кодирует набор допустимых выборов
Как степени переменной кодируют разрешённые количества, а коэффициент произведения считает сочетания с фиксированной суммой без перебора всех полных распределений.
Открыть тему