10
правок
Изменения
Нет описания правки
__TOC__
== Алгоритм за O(N<sup>3</sup>)==
Имеет место следующее рекуррентное соотношение:
<p>
<tex dpi = "145">P(n, m, k) = \left \{\begin{array}{ll}P(n, m, k - 1) + P(n - k, m - 1, k), & 0 </tex> при <tex>m\leqslant n,0 < k \leqslant n\\1, & n = 0, m = 0 \\0, & \text{otherwise} \end{array} \right. </tex>
</p>
Рассмотрим множество разбиений числа <tex>n</tex> на <tex>m</tex> слагаемых, каждое из которых не больше <tex>k</tex>. Разделим его на две непересекающиеся группы — в первой будут всеразбиения, которые не содержат в качестве старшего слагаемого <tex>k</tex>. Таких разбиений <tex>P(0n,0m,ik - 1) = </tex>. Во второй — все разбиения со старшим слагаемым <tex>k</tex>. Их столько же, сколько разбиений числа <tex>n - k</tex> на <tex>m - 1</tex> слагаемое, каждое из которых не больше <tex>k</tex>, \forall i \geqslant 0то есть <tex>P(n - k, m - 1, k)</tex>.
== Алгоритм за O(N<sup>2</sup>) ==
Обозначим <tex>P(n,k)</tex> — количество разбиений числа <tex>n</tex> на слагаемые, каждое из которых не превосходит <tex>k</tex>. Оно удовлетворяет следующей рекурентной формуле:<p>
<tex dpi="145">P(n,k) = \left \{ \begin{array}{ll} P(n,k - 1) + P(n - k, k), & 0 < k \leqslant n \\ P(n, n), & k > n \\1, & n = 0, k = 0 \\0, & n \neq 0 , k = 0 \end{array} \right.</tex>
</p>
Заметим, что нам не нужно считать количество слагаемых <tex>P(0,0) = 1m</tex> в разбиении. Достаточно посчитать <tex> P(in, 0k) = 0, \forall i>0</tex> Обоснование: Аналогично предыдущему пункту, рассмотрим разбиения — количество разбиений числа <tex>n</tex> на произвольное количество слагаемых, каждое из которых не больше <tex>k</tex>.Рассмотрим множество таких разбиений. Разделим их его на две не пересекающиеся группы. В первую войдут те разбиения, в которых отсутствует слагаемое <tex>k</tex>. Очевидно, таких разбиений <tex>P(n, k - 1)</tex>.Во второй группе — те разбиения, в которые слагаемое <tex>k</tex> вошло. Их количество совпадает с количеством разбиений числа <tex>n - k</tex> на слагаемые, каждое из которых не превосходит <tex>k</tex>, и равно <tex>P(n - k, k)</tex>.
Количество всех разбиений числа <tex>n</tex> равно <tex>P(n,n)</tex>. Асимптотика <tex>O(n^{2})</tex>.
После раскрытия скобок каждый член произведения получается в результате умножения мономов (одночленов), взятых по одному из каждой скобки. Если в первой скобке взять <tex dpi = "145">x^{m_1}</tex>, во второй — <tex dpi = "145">x^{2m_2}</tex> и т.д., то их произведение будет равно <tex dpi = "145">x^{m_1 + 2m_2 + 3m_3 + \dots}.</tex> Значит, после раскрытия скобок получится сумма мономов вида <tex dpi = "145">x^{m_1 + 2m_2 + 3m_3 + \dots}</tex>.
Можно увидеть, что <tex> x^n </tex> встретится в полученной бесконечной сумме столько раз, сколькими способами можно представить <tex>n</tex> как сумму <tex>m_1 + 2m_2 + 3m_3 + ...</tex> Каждому такому представлению отвечает разбиение числа <tex>n</tex> на <tex>m_1</tex> единиц, <tex>m_2</tex> двоек и т.д. Таким образом, очевидно, получаются все разбиения, так как из первой скобки мы можем взять любое <tex>x^{m_i}</tex>, где <tex>m_i \in [0 \dots \infty),</tex> то есть произвольное количество единиц в нашем разбиении. Аналогично, мы можем взять произвольное количество двоек и т.д. Но при раскрытии скобок мы находим произведения всех возможных комбинации множителей из разных скобок. Поэтому коэффициент при <tex>x^n</tex> равен числу разбиений <tex>p(n)</tex>. Для доказательства следующего факта обратимся к [[Производящая функция|методу производящих функций]].
Посмотрим теперь на выражения в скобках. Каждое из них — бесконечная геометрическая прогрессия. Полагая <tex>0 \leqslant x < 1</tex>, по формуле ее суммирования:
: <tex dpi = "145">1 + x + x^2 + x^3 + ... \dots = \frac{1}{1 - x}</tex>,: <tex dpi = "145">1 + x^2 + x^4 + x^6 + ... \dots = \frac{1}{1-x^2}</tex>: <tex>\dots</tex>: <tex dpi = "145">1 + x^k + x^{2k} + x^{3k} + \dots = \frac{1}{1-x^k}</tex>
: <tex>\dots</tex>
: <tex dpi = "145">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}</tex> <tex>(1)</tex>
