Изменения

По заданному числу <tex>n</tex> найти количество его различных разбиений на положительные слагаемые<ref name="amount" /> <tex> m_0 + m_1 + m_2 + \dots ldots + m_k = n </tex> так, что при всех <tex> i: \colon m_i \leqslant m_{i+1} </tex>.}}

<tex dpi = "145">P(n, m, k) = \left \{\begin{array}{ll}P(n, m, k - 1) + P(n - k, m - 1, k), & 0 </tex> при m \leqslant n, 0 <tex>k \leqslant n \\P(n, m,n), & k > n \leqslant \1, & n= 0, m = 0 \\0, & \text{otherwise} \end{array} \right. </tex>

Рассмотрим множество разбиений числа <tex>n</tex> на <tex>m</tex> слагаемых, каждое из которых не больше <tex>k</tex>. Разделим его на две непересекающиеся группы — в первой будут всеразбиения , которые не содержат в качестве старшего слагаемого <tex>k</tex>. Таких разбиений <tex>P(n, m, k - 1)</tex>. Во второй — все разбиения со старшим слагаемым <tex>k</tex>. Их столько же, сколько разбиений числа <tex>n - k</tex> на <tex>m - 1</tex> слагаемое, каждое из которых не больше <tex>k</tex>, то есть <tex>P(n - k, m - 1, k)</tex>.

Количество всех разбиений числа равно <tex>\sum\limits_{i=0}^nP(n, i, n)</tex>. Асимптотика Реализация данного алгоритма методом [[Динамическое программирование|динамического программирования]] с меморизацией будет иметь асимптотику <tex>O(n^{3})</tex> получается из-за использования трехмерной динамики.

<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>

Заметим, что нам не нужно считать количество слагаемых <tex>m</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> O(n \sqrt{n}) </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 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>p(n)</tex>: