Разбиение числа на слагаемые: подсчёт и алгоритм

Число 5 можно представить как , или . Если разрешить повторения положительных целых слагаемых и не считать перестановку новым вариантом, получится конечный список разбиений. Сколько в нём строк и как убедиться, что ни одна не пропущена? Калькулятор ниже считает общее число разбиений и показывает, сколько из них состоит из одной, двух и большего числа частей.
Что называют разбиением числа
Разбиение положительного целого числа - представление его суммой положительных целых чисел, которые называют частями. Одинаковые части разрешены. Суммы и задают одно разбиение: изменился только порядок записи. Чтобы избежать повторов, удобно записывать части по невозрастанию. Число всех разбиений обозначают ; такое определение использует и справочник NIST DLMF.
Например, все варианты для пятёрки можно расположить так:
Всего семь строк, поэтому . На видео выделение последовательно проходит по этому списку. Каждый ряд содержит пять клеток; промежутки отделяют части друг от друга.
Запись самого числа, например , тоже считается разбиением: это сумма из одной части. В стандартном определении ноль среди частей запрещён, иначе к любой строке можно было бы добавлять сколько угодно нулей. Отрицательные числа также исключены. С такими ограничениями число вариантов конечно.
Почему порядок меняет ответ
При подсчёте разбиений и совпадают. Если же места слагаемых различаются, это две разные упорядоченные суммы, или композиции. Для 5 таких сумм 16, а разбиений только 7. Причина видна на пяти единицах в ряд: в каждом из четырёх промежутков независимо выбирают, поставить разделитель или нет. По правилу произведения получается .
Разделитель после второй единицы, например, даёт , а после третьей - . Для композиции это разные ответы, для разбиения - один. Вообще положительное имеет композиций при , но эта формула не считает разбиения. В задаче сначала выясните, различаются ли перестановки; полезное сравнение двух типов выбора есть в статье про сочетания и перестановки.
Перечисление без повторов
Для маленького числа можно построить список вручную. Сначала выпишите вариант из одной части, затем выбирайте наибольшую часть по убыванию и разбивайте остаток на части не больше выбранной. Для 5 после строки берём 4 и получаем ; затем берём 3 и получаем и . При наибольшей части 2 остаются и , а последний вариант состоит из единиц.
Условие невозрастания делает представление единственным: всякое разбиение можно так упорядочить, а перестановки уже не попадут в список повторно. При программном переборе удобно хранить остаток и максимальную разрешённую следующую часть. Каждый рекурсивный вызов выбирает часть не больше обоих значений, уменьшает остаток и передаёт выбранную часть как новый предел. При нулевом остатке найден один готовый вариант.
Важно различать перечисление и подсчёт. Первый алгоритм обязан вывести каждую строку, поэтому при росте числа вариантов растёт и объём вывода. Если нужно только количество, можно сохранять ответы на повторяющиеся подзадачи. Эту идею подробно разбирает статья об основах динамического программирования.
При реализации рекурсивного перебора каждый вызов помнит выбранную часть и место, с которого продолжить поиск после возврата. Эти состояния можно хранить и явно в стеке: механизм последним возвращается к последнему незавершённому выбору. О такой дисциплине работы рассказывает статья про стек и очередь. Например, после вывода программа возвращается к остатку 2 и пробует меньшую следующую часть; так она достигает . Ограничение на следующую часть действует на каждом уровне, а не только в начале. Это важно и для остановки, и для отсутствия повторов: остаток строго уменьшается, пока не станет нулевым.
Сколько разбиений имеют ровно k частей
Обозначим через число разбиений ровно на положительных частей. Для шести части распределяются так:
| Число частей | Количество | Примеры |
|---|---|---|
| 1 | 1 | |
| 2 | 3 | , , |
| 3 | 3 | , , |
| 4 | 2 | , |
| 5 | 1 | |
| 6 | 1 |

Сумма высот столбцов равна , значит . Калькулятор в начале строит это же распределение для выбранного числа от 1 до 30. Он не выводит сами варианты: столбец отвечает только на вопрос «сколько?». Например, при сумма столбцов равна 42. На схеме золотом выделен столбец для двух частей; его высота 3.
Рекуррентная формула и её смысл
Все разбиения на частей делятся на две непересекающиеся группы. В первой есть хотя бы одна единица. Удалив одну единицу, получим разбиение на частей; обратная операция добавляет единицу. Во второй группе единиц нет. Вычтя единицу из каждой части, получим разбиение на те же положительных частей; прибавление единицы ко всем частям восстанавливает исходный вариант. Поэтому
Базой служит : пустое разбиение позволяет завершить вычисление. Для положительного значение равно нулю, а при невозможных параметрах, например , тоже ставят ноль. Тогда . Суммирование по от 1 до даёт . Базовый случай для нуля - соглашение счёта, а не разрешение нулевых частей в разбиении положительного числа.
Ограничения на части: пример задачи
Условие может уточнять, какие части разрешены. Допустим, нужно разложить 6 только на нечётные положительные слагаемые. В обычном списке остаются четыре варианта: , , и сумма шести единиц. Разбиение исключено из-за четвёрки, хотя итоговая сумма у него правильная. Поэтому стандартное значение здесь ответом не будет.
Для похожих задач полезно сначала зафиксировать три условия: допустимые размеры частей, возможность повторения и требуемое количество частей. Затем проверьте каждый кандидат по всем условиям сразу. Если требуется ровно две нечётные части, из четырёх вариантов остаются только первые два. Если же разрешены только различные нечётные части, остаётся один вариант: . Слово «различные» относится к значениям частей, а не к тому, что они занимают разные места в записи.
В одномерном алгоритме ограничение на размеры задают во внешнем цикле: вместо всех чисел от 1 до перебирают только разрешённые. При разрешённых повторах суммы по-прежнему идут вверх. При запрете повторений суммы идут вниз: тогда значение для меньшего остатка ещё не обновлено текущей частью, и добавить её второй раз на этом шаге нельзя. Ограничение ровно на заданное число частей требует дополнительного измерения состояния или другой подходящей рекуррентной формулы.
Производящая функция
Есть и компактная запись, которая объединяет все значения в один ряд. Для каждой возможной части выбирают ноль, одно, два и более её вхождений; им соответствуют степени . Перемножив такие ряды для всех положительных , получим
Коэффициент при считает способы набрать суммарную степень : выбор степени в каждом множителе определяет число частей данного размера. Каждый набор кратностей учитывается один раз, поэтому порядок частей не возникает. Для вычисления конкретного коэффициента до степени достаточно множителей с . Эта формула также приведена в справочнике NIST; она объясняет, почему алгоритм обрабатывает размеры частей по одному.
Как посчитать ответ программой
Создайте таблицу с индексами суммы и числа частей, запишите в ячейку единицу и заполните строки от меньших сумм к большим по формуле выше. Оба слагаемых справа относятся к меньшим суммам, поэтому их значения уже известны. При таблица размера требует ячеек и столько же арифметических операций. Это оценка количества операций; для очень больших целых цена отдельного сложения тоже растёт.
Для подсчёта только общего количества есть и одномерная версия. Положите , остальные значения - ноль. Для каждой разрешённой части от 1 до проходите суммы от до по возрастанию и прибавляйте к . Внешний цикл фиксирует порядок обработки размеров частей, поэтому перестановки не дублируются; движение суммы вверх позволяет использовать одну часть неоднократно. Память составляет , а число сложений - .
Частые ошибки
- Считать перестановки отдельно. Запишите каждую сумму по невозрастанию и удалите одинаковые строки.
- Запретить одинаковые части без условия. Например, входит в обычные разбиения 6; разные части - дополнительное ограничение.
- Добавлять нули или отрицательные числа. В стандартной задаче части строго положительны.
- Путать число частей и их максимальный размер. Это разные ограничения для конкретного разбиения, даже если некоторые итоговые количества совпадают.
- Менять порядок циклов в одномерном алгоритме. Проход по суммам снаружи может начать считать разные порядки частей как отдельные варианты.
FAQ
Можно ли разбить число на одно слагаемое?
Да. Для любого положительного запись - разбиение из одной части.
Сколько разбиений у нуля?
По принятому соглашению : учитывают единственное пустое разбиение. Оно нужно и для базовых случаев алгоритмов.
Как найти разбиения только на различные части?
При перечислении после выбора части запрещайте выбирать её снова. В одномерном подсчёте для каждой части проходите суммы вниз, чтобы одну и ту же часть нельзя было использовать повторно.
Коротко
Разбиение - сумма положительных целых частей без учёта их порядка. Для небольших чисел варианты удобно перечислять по невозрастанию, а для подсчёта использовать таблицу или одномерное динамическое программирование. Прежде чем считать, уточните, разрешены ли повторения и имеет ли значение порядок.
Читайте также

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

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

Количество путей в ориентированном графе
Как найти количество путей в ориентированном графе: подсчёт в DAG, динамическое программирование, матрица смежности, заданная длина и влияние циклов на ответ.

Наибольшая общая подпоследовательность: алгоритм и пример
Как найти наибольшую общую подпоследовательность двух строк: таблица динамического программирования, восстановление ответа, пример на словах и оценка сложности.

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

Задача о рюкзаке: динамическое программирование
Разбор задачи о рюкзаке (0/1 Knapsack) методом ДП: таблица dp[i][w], рекуррентный переход, traceback-восстановление набора. Пошаговые примеры и анализ сложности O(n*W).