Введение

Число разбиений целого числа

В теории чисел функция разбиений p(n) представляет собой количество возможных разбиений неотрицательного целого числа n. Например, p(4) = 5, поскольку целое число 4 имеет пять разбиений: 1 + 1 + 1 + 1, 1 + 1 + 2, 1 + 3, 2 + 2 и 4. Не существует формулы в замкнутом виде для функции разбиений, но для неё известны как асимптотические разложения, точно её приближающие, так и рекуррентные соотношения, позволяющие вычислить её значение точно. Она растёт как экспоненциальная функция от квадратного корня своего аргумента. Мультипликативно обратная к её порождающей функции – функция Эйлера; согласно теореме Эйлера о пентагональных числах, эта функция является знакопеременной суммой степеней пентагональных чисел своего аргумента. Сриниваса Рамануджан первым обнаружил, что функция разбиений обладает нетривиальными закономерностями в модульной арифметике, ныне известные как конгруенции Рамануджана. Например, если десятичная запись n заканчивается цифрой 4 или 9, то число разбиений n будет делиться на 5.

Ограниченная функция разделов

В более общем смысле, можно рассматривать разбиения, ограниченные только элементами подмножества А натуральных чисел (например, ограничением на максимальное значение слагаемых), или с ограничением на количество слагаемых или на максимальную разность между слагаемыми. Каждое конкретное ограничение порождает соответствующую функцию разбиений с определенными свойствами. Ниже приведены некоторые распространенные примеры.

Теорема Эйлера и Глейшера

Два важных примера — это разбиения, ограниченные только нечетными целыми частями или только четными целыми частями, с соответствующими функциями разбиений, которые часто обозначаются и . Теорема Эйлера показывает, что количество строгих разбиений равно количеству разбиений, состоящих только из нечетных частей: для всех n, . Это обобщается теоремой Глейшера, которая утверждает, что количество разбиений, в которых ни одна часть не повторяется более чем d-1 раз, равно количеству разбиений, не содержащих частей, делящихся на d.