Калькулятор числа разбиений p(n)

Что означает число разбиений p(n)

Одинаковое количество жетонов разложено по группам разного размера

Число разбиений p(n) показывает, сколькими способами неотрицательное целое n можно представить суммой положительных целых слагаемых, если порядок не важен. Например, для 5 существуют семь вариантов: 5, 4 + 1, 3 + 2, 3 + 1 + 1, 2 + 2 + 1, 2 + 1 + 1 + 1 и 1 + 1 + 1 + 1 + 1. Записи 4 + 1 и 1 + 4 считаются одним разбиением.

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

У нуля принято одно разбиение, пустая сумма, поэтому p(0) = 1. Это соглашение не добавляет к нулю выдуманные положительные части. Оно задаёт базовый случай, с которым рекурсия одинаково работает для p(1), p(2) и следующих значений.

Как калькулятор получает точный ответ

Калькулятор использует рекурсию Эйлера. В неё входят обобщённые пятиугольные числа k(3k - 1) / 2 и k(3k + 1) / 2. Для k = 1, 2, 3 первые пары индексов равны 1 и 2, 5 и 7, 12 и 15. Знаки повторяются парами: плюс, плюс, минус, минус.

Полная рекурсия записывается так:

\displaystyle p(n)=\sum_{k=1}^{\infty}(-1)^{k+1}\left[p\!\left(n-\frac{k(3k-1)}{2}\right)+p\!\left(n-\frac{k(3k+1)}{2}\right)\right]

Здесь p(0) = 1, а p(m) = 0 для m < 0. Поэтому бесконечная сумма при каждом конкретном n фактически конечна: как только оба пятиугольных смещения превышают n, следующие слагаемые тоже равны нулю. Например, p(10) = p(9) + p(8) - p(5) - p(3) = 30 + 22 - 7 - 3 = 42.

Значения от p(0) до p(n) вычисляются последовательно и хранятся как BigInt. Алгоритму требуется O(n√n) целочисленных операций. Он не перебирает сами разбиения, поэтому p(10 000) можно посчитать, хотя вывести все соответствующие варианты было бы совершенно непрактично. Определение, производящая функция и рекурсия приведены в NIST Digital Library of Mathematical Functions, §27.14; контрольная последовательность имеет номер OEIS A000041.

Как читать результат на примерах

🧩 Ручная проверка для n = 5. Семь сумм перечислены в начале страницы, значит, p(5) = 7. Практический вывод: сначала приводите слагаемые к невозрастающему порядку. Тогда перестановки одной суммы не попадут в список повторно.

🪙 Пять одинаковых жетонов. Если важны только размеры кучек, жетоны можно разложить семью способами: одной кучкой из пяти, кучками 4 + 1, 3 + 2 и ещё четырьмя вариантами. Если сами жетоны имеют номера или цвета, это уже другая задача, потому что появляется индивидуальность объектов.

📦 Восемь одинаковых деталей по партиям. Когда порядок партий не важен, а каждая партия содержит хотя бы одну деталь, наборы размеров считаются числом p(8) = 22. Ответ описывает варианты размеров партий, но не выбирает, какие именно пронумерованные детали попадут в каждую из них.

🏭 Десять единиц выпуска. Для неупорядоченных положительных размеров серий получается p(10) = 42. Если первая, вторая и третья серии относятся к разным дням, порядок уже важен и 4 + 3 + 3 отличается от 3 + 4 + 3. Тогда число разбиений применять нельзя.

↔️ Суммы, где порядок важен. У числа 5 есть 7 разбиений, но 16 композиций, то есть упорядоченных представлений положительными слагаемыми. Например, 3 + 2 и 2 + 3 становятся разными композициями. Перед расчётом достаточно проверить один вопрос: изменится ли смысл после перестановки частей?

👥 Сравнение с числами Белла. Для n = 3 калькулятор даёт p(3) = 3: 3, 2 + 1 и 1 + 1 + 1. Число Белла B₃ равно 5, потому что оно разбивает три различимых элемента, например Анну, Бориса и Веру, на группы. Здесь же одинаковые слагаемые не имеют имён и индивидуальности.

💻 Контроль большой реализации. p(100) = 190 569 292, а p(1000) содержит 32 цифры и равно 24061467864032622473692149727991. Эти значения удобно использовать в автоматических тестах. Если программа возвращает дробь, экспоненциальную запись или другое последнее число, где-то потеряна точная целочисленная арифметика.

Почему результат растёт так быстро

Первые значения выглядят спокойно: p(0) = 1, p(1) = 1, p(2) = 2, p(3) = 3, p(4) = 5, p(5) = 7 и p(10) = 42. Затем вариантов становится заметно больше: p(20) = 627, p(50) = 204 226, p(100) = 190 569 292. Рост ускоряется, потому что новое n допускает всё больше наборов повторяющихся частей.

При n = 10 000 результат содержит 107 цифр. Калькулятор показывает их полностью, группирует по десять знаков для чтения и копирует без пробелов. Верхняя граница ограничивает не математическое определение, а объём вычислений и вывода в браузере. Значение не округляется и не преобразуется в степень десяти.

Число разбиений отвечает только на вопрос «сколько». Оно не перечисляет сами суммы и не ограничивает число частей, максимальное слагаемое или допустимый набор номиналов. Если в задаче можно использовать, например, только 1, 2 и 5, потребуется ограниченная модель. Для выбора k элементов из n без учёта порядка подходит калькулятор сочетаний, а для упорядочивания разных объектов нужен калькулятор перестановок.

Важно! Не путайте p(n) с разбиением множества. В p(n) части являются обычными положительными числами, повторяются и не различаются между собой. Числа Белла считают способы распределить по непустым группам различимые элементы.

Вопросы о разбиениях целого числа

Граничные случаи и похожие комбинаторные задачи меняют ответ сильнее, чем размер n. Эти уточнения помогают выбрать p(n), а не внешне похожую формулу.

Почему p(0) равно 1?

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

Учитывается ли порядок слагаемых?

Нет. Суммы 4 + 1 и 1 + 4 являются одним разбиением. Обычно части записывают по невозрастанию, чтобы одинаковые варианты сразу совпадали.

Могут ли слагаемые повторяться?

Да. Разбиение 5 содержит варианты 3 + 1 + 1, 2 + 2 + 1 и 1 + 1 + 1 + 1 + 1. Каждая часть должна быть положительным целым числом.

Чем разбиения отличаются от композиций?

В композиции порядок частей важен, поэтому 3 + 2 и 2 + 3 считаются отдельно. Для положительного n число композиций равно 2 в степени n - 1, а число разбиений p(n) меньше.

Чем p(n) отличается от числа Белла Bₙ?

p(n) разбивает само целое число на неразличимые положительные части. Bₙ разбивает множество из n различимых элементов на непустые группы, поэтому уже p(3) = 3, а B₃ = 5.

Можно ли вводить отрицательное или дробное n?

Нет. Калькулятор принимает целые n от 0 до 10 000. Отрицательное или дробное количество единиц не соответствует определению неограниченных разбиений целого числа.

Почему калькулятор не выводит все разбиения?

Количество вариантов быстро растёт. Уже p(100) = 190 569 292, поэтому полный список занял бы несопоставимо больше времени и памяти, чем вычисление одного количества.

Округляются ли большие ответы?

Нет. Расчёт выполняется с BigInt и возвращает точное целое. Пробелы между группами цифр служат только для чтения и удаляются при копировании.

Есть что добавить?

Напишите своё мнение, комментарий или предложение.