Нахождение количества разбиений числа на слагаемые

Задача: По заданному числу [math]n[/math] найти количество его различных разбиений на слагаемые [math] m_0 + m_1 + m_2 \dots + m_k = n [/math] так что [math] \forall i: m_i \le m_{i+1} [/math].

Алгоритм за n sqrt(n)

Существует несколько алгоритмов решения данной задачи. Рассмотрим самый быстрый алгоритм нахождения количества разбиений числа [math]n[/math] на слагаемые, который работает за [math] O(n \sqrt{n}) [/math].

Итак, обозначим количество таких разбиений за [math] p(n) [/math].

Рассмотрим следующее бесконечное произведение [math] (1 + x + x^2 + \dots)(1 + x^2 + x^4 + \dots) \dots (1 + x^k + x^{2k} + \dots) \dots [/math] После раскрытия скобок каждый член произведения получается в результате умножения мономов (одночленов), взятых по одному из каждой скобки. Если в первой скобке взять [math]x^{m_1}[/math], во второй — [math]x^{2m_2}[/math] и т.д., то их произведение будет равно [math]x^{m_1 + 2m_2 + 3m_3 + \dots}.[/math] Значит, после раскрытия скобок получится сумма мономов вида [math]x^{m_1 + 2m_2 + 3m_3 + \dots}[/math].

Можно увидеть, что [math] x^n [/math] встретится в полученной бесконечной сумме столько раз, сколькими способами можно представить [math]n[/math] как сумму [math]m_1 + 2m_2 + 3m_3 + ...[/math] Каждому такому представлению отвечает разбиение числа [math]n[/math] на [math]m_1[/math] единиц, [math]m_2[/math] двоек и т.д. Таким образом очевидно получаются все разбиения, так как из первой скобки мы можем взять любое [math]x^{m_i}[/math], где [math]m_i \in \{0 \dots \infty \},[/math] то есть произвольное количество единиц в нашем разбиении. Аналогично, мы можем взять произвольное количество двоек и т.д. Но при раскрытии скобок мы находим произведения всех возможных комбинации множителей из разных скобок. Поэтому коэффициент при [math]x^n[/math] равен числу разбиений [math]p(n)[/math].

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

[math]1 + x + x^2 + x^3 + ... = \frac{1}{1 - x}[/math],

[math]1 + x^2 + x^4 + x^6 + ... = \frac{1}{1-x^2}[/math]

и т.д. Теперь наш результат можно записать так:

[math]p(0) + p(1) x + p(2) x^2 + p(3) x^3 + \dots = \frac{1}{(1-x)(1-x^2)(1-x^3)\dots}[/math]                                                           [math](1)[/math]

Рассмотрим произведение [math](1-x)(1-x^2)(1-x^3)...[/math], т.е. знаменатель правой части формулы [math](1)[/math]. Раскрывая в нём скобки, получим следующий результат:

[math](1 - x)(1 - x^2)(1 - x^3) ... = 1 - x - x^2 + x^5 + x^7 - x^{12} - x^{15} + x^{22} + x^{26} - x^{35} - x^{40} + ...[/math]

Показатели степеней в правой части — пятиугольные числа, т.е. числа вида [math](3q^2 \pm q)/2[/math], а знаки при соответствующих мономах равны [math](-1)^q[/math]. Исходя из этого наблюдения, Эйлер предположил, что должна быть верна следующая теорема, впоследствии названная его именем.

Теорема (Пентагональная теорема Эйлера):

[math] \prod\limits_{k=1}^\infty \left(1-x^k \right) = \sum\limits_{q=-\infty}^\infty (-1)^q x^{(3q^2+q)/2}[/math]

Доказательство:

[math]\triangleright[/math]

Пентагональная теорема оказалась «крепким орешком» — Эйлер сумел доказать её лишь 14 лет спустя. TODO: скурить доказательство

[math]\triangleleft[/math]

Умножим обе части равенства (1) на [math]\prod\limits_{k=1}^\infty \left(1-x^k \right) [/math] и воспользуемся пентагональной теоремой:

[math] ( p(0) + p(1) x + p(2) x^2 + \dots)(1 - x - x^2 + x^5 + x^7 - x^{12} - x^{15} + \dots) = 1 [/math](2)

Начнем раскрывать скобки, для наглядности мономы с одинаковыми степенями x пишем друг под другом:

[math] p(0) + p(1)x + p(2) x^2 + p(3) x^3 + p(4) x^4 + p(5) x^5 + p(6) x^6 + \dots [/math]

[math] - p(0)x - p(1) x^2 - p(2) x^3 - p(3) x^4 - p(4) x^5 - p(5) x^6 - \dots [/math]

[math] - p(0) x^2 - p(1) x^3 - p(2) x^4 - p(3) x^5 - p(4) x^6 - \dots [/math]

[math]+ p(0) x^5 + p(1) x^6 + \dots [/math]

// тут ужасное быдлоформатирование, не знаю как нормально расположить друг под другом

Так как p(0) = 1, то оно сокращается с единицей справа. Так что чтобы выражение (2) было удовлетворено при любом x, все коэффициенты должны быть равны 0(вроде так). Поэтому:

[math] p(1) = p(0) [/math]

[math] p(2) = p(1) + p(0) [/math]

[math] p(3) = p(2) + p(1) [/math]

[math] p(4) = p(3) + p(2) [/math]

[math] p(5) = p(4) + p(3) - p(0) [/math]

и т.д.

Получаем формулу Эйлера, позволяющую последовательно находить числа [math]p(n)[/math]:

[math] p(n) = p(n-1) + p(n-2)+ ... + (-1)^{q+1} (p(n - \frac{3q^2 - q}{2}) + p(n - \frac{3q^2 + q}{2})) [/math].

Ну и объяснение асимптотики [math] O(n \sqrt{n}) [/math] - так как [math] n - \frac{3q^2 + q}{2} \ge 0 [/math] , получаем [math] q [/math] порядка [math] \sqrt{n} [/math], а так как находим n-е число, то получаем [math] O(n \sqrt{n}) [/math].

Используемые материалы

• Pentagonal number theorem
• Вайнштейн Ф., Разбиение чисел. Журнал "Квант" № 11, 1988 год
• Последовательность на OEIS