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

Почему разбиения числа отличаются от упорядоченных сумм

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

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

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

В маршруте Счёт через устройство объектов · 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. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

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