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

В теме Доказательства и комбинаторные модели · Учебная карта
В маршруте Счёт через устройство объектов · 10 тем
Главная мысль
В разбиении числа перестановка положительных слагаемых не создаёт нового объекта. Для однозначной записи части располагают невозрастающе; одинаковые части при этом разрешены, если нет отдельного запрета.
Порядок убран, повторения сохранены
Число пять можно разбить как 5; 4+1; 3+2; 3+1+1; 2+2+1; 2+1+1+1; 1+1+1+1+1. Получается семь разбиений. Запись 1+4 не добавляет восьмого, потому что содержит те же части, что 4+1. Однако 3+1+1 и 2+2+1 различаются составом частей и остаются отдельными.
Если порядок слагаемых важен, речь идёт об упорядоченных суммах, или композициях. Они описывают другой объект: например, последовательность размеров этапов. Нельзя переходить между задачами только по внешнему знаку сложения. Сначала нужно понять, различаются ли переставленные части в исходном условии, а уже затем выбирать формулу или перебор.
Почему деление на факториал не работает всегда
У разбиения 3+2+1 шесть разных перестановок, у 2+2+2 — одна. Одинаковые части уменьшают число различных порядков. Поэтому общее количество композиций нельзя просто разделить на один факториал и получить число разбиений: разные исходные разбиения представлены в упорядоченном списке с разной кратностью.
Для систематического перечисления можно выбирать наибольшую часть, затем следующую не больше неё и продолжать до нулевого остатка. Неувеличение частей устраняет повторные перестановки. При ограничении «ровно k частей» нужно дополнительно следить за их числом. Нули в стандартное разбиение положительного числа не дописывают: иначе одна и та же сумма имела бы бесконечно много лишних записей.
Пример
Найдите разбиения числа семь ровно на три положительные части.
При невозрастающем порядке получаются 5+1+1; 4+2+1; 3+3+1; 3+2+2. Других нет: минимальная часть равна 1 или 2, и разбор этих двух случаев даёт перечисленные варианты.
Ограничения образуют новые задачи
Разбиения на различные части запрещают повторные единицы и другие повторы. Разбиения на нечётные части, наоборот, могут допускать повторы, но ограничивают размер каждой части. Эти условия независимы. Обнаруженное равенство количеств двух семейств требует доказательства, а не утверждения, что ограничения «примерно одинаковы».
Разбиение нуля обычно считают единственным пустым разбиением. Такая договорённость согласует рекурсии: когда остаток полностью распределён, найден один завершённый вариант. Отрицательный остаток вариантов не даёт. При программном или ручном переборе полезно записать эти окончания отдельно, чтобы не принять незавершённую ветвь за решение и не потерять вариант без оставшихся частей.
От чтения к действию
А теперь — вы
Частые вопросы
Могут ли в разбиении быть одинаковые части?
В обычном разбиении да. Запрет повторов является дополнительным условием и меняет ответ.
Почему пишут части невозрастающе?
Это соглашение выбирает одну запись из всех перестановок одного состава и предотвращает повторный подсчёт.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Как распределить одинаковые предметы с нижними границами
Как учесть разные минимальные количества в распределении одинаковых предметов, снять нижние границы заменой переменных и проверить невозможный остаток.
Открыть темуКак коэффициент произведения кодирует набор допустимых выборов
Как степени переменной кодируют разрешённые количества, а коэффициент произведения считает сочетания с фиксированной суммой без перебора всех полных распределений.
Открыть тему