10
правок
Изменения
Нет описания правки
__TOC__
== Алгоритм за O(N<sup>3</sup>)==Пусть <tex>P(n sqrt, m, k)</tex> — количество разбиений числа <tex>n</tex> на <tex>m</tex> слагаемых, каждое из которых не превосходит <tex>k</tex>.Имеет место следующее рекуррентное соотношение:<p><tex dpi = "145">P(n, m, k) =P(n, m, k - 1) + P(n - k, m - 1, k)</tex> при <tex>m,k \leqslant n</tex></p>Начальные условия <tex>P(0,0,i) =1, \forall i \geqslant 0</tex>Существует несколько алгоритмов <tex>P(i,0,j) = 0, \forall i,j > 0</tex> <tex>P(i, j, 0) = 0, \forall i,j>0</tex> Ниже приведен алгоритм решения данной задачи:<pre>function Partition(n, m, k): if n >= 0 and k >= 0 and d[n][m][k] > 0: return d[n][m][k] if n == 0 and m == 0 return 1; if n < 0 or m == 0 or k == 0: return 0 d[n][m][k] = Partition(n, m, k - 1) + Partition(n - k, m - 1, k) return d[n][m][k]</pre>Начальные значения динамики <tex>d[n][k] = -1</tex>. Ответ на исходную задачу равен <tex>\sum\limits_{i=0}^nPartition(n, i, n)</tex>. Асимптотика <tex>O(n^{3})</tex>. __TOC__ == Алгоритм за 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), & k \leqslant n \\ P(n, n), & k > n \end{array} \right.</tex></p>При этом считается что <tex>P(0,0) = 1</tex> <tex> P(i, 0) = 0, \forall i>0</tex> Количество всех разбиений числа <tex>n</tex> равно <tex>P(n,n)</tex>.Следующий алгоритм решает данную задачу:<p><pre>function Partition(n, k): if n >= 0 and k >= 0 and d[n][k] > 0: return d[n][k] if n < 0: return 0 if n <= 1 or k == 1: return 1 d[n][k] = Partition(n, k - 1) + Partition(n - k, k) return d[n][k]</pre> Начальные значения динамики <tex>d[n][k] = -1</tex>. Для вычисления ответа необходимо вызвать <tex>Partition(n, n)</tex>. Асимптотика <tex>O(n^{2})</tex>.</p> __TOC__ == Алгоритм за O(N<sup>3/2</sup>) ==Рассмотрим самый быстрый алгоритм нахождения количества разбиений числа <tex>n</tex> на слагаемые, который работает за <tex> O(n \sqrt{n}) </tex>.
Итак, обозначим количество таких разбиений за <tex> p(n) </tex>.
Рассмотрим произведение <tex>(1-x)(1-x^2)(1-x^3)...</tex>, т.е. знаменатель правой части формулы <tex>(1)</tex>. Раскрывая в нём скобки, получим следующий результат:
: <tex>(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} + ...</tex>
Показатели степеней в правой части — [http://ru.wikipedia.org/wiki/%D0%A4%D0%B8%D0%B3%D1%83%D1%80%D0%BD%D1%8B%D0%B5_%D1%87%D0%B8%D1%81%D0%BB%D0%B0#.D0.9F.D1.8F.D1.82.D0.B8.D1.83.D0.B3.D0.BE.D0.BB.D1.8C.D0.BD.D1.8B.D0.B5_.D1.87.D0.B8.D1.81.D0.BB.D0.B0 пятиугольные числа]<ref name="pentagon" />, т.е. числа вида <tex>(3q^2 \pm q)/2</tex>, а знаки при соответствующих мономах равны <tex>(-1)^q</tex>. Исходя из этого наблюдения, Эйлер предположил, что должна быть верна следующая теорема, впоследствии названная его именем.
{{Теорема
}}
Иными словами, если <tex>q</tex> четно, то на одно больше разбиений на четное число слагаемых, а если <tex>q</tex> нечетно, то на одно больше разбиений на нечетно число слагаемых. Докажем эту теорему с помощью [http://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D0%B7%D0%B1%D0%B8%D0%B5%D0%BD%D0%B8%D0%B5_%D1%87%D0%B8%D1%81%D0%BB%D0%B0#.D0.94.D0.B8.D0.B0.D0.B3.D1.80.D0.B0.D0.BC.D0.BC.D1.8B_.D0.AE.D0.BD.D0.B3.D0.B0 диаграмм Юнга].<ref name="young" />. Покажем несколько способов превращения диаграммы с четным числом строк диаграмму из стольких же точек с нечетным числом строк и обратно.
Так как мы рассматриваем лишь разбиения на различные слагаемые, то диаграммы таких разбиений состоят из нескольких трапеций, поставленных друг на друга. Обозначим число точек в верхней строке диаграммы через <tex>m</tex>, а число строк нижней трапеции через <tex>n</tex> (на рис. 1 слева изображена диаграмма, для которой <tex>m=2</tex>, <tex>n=3</tex>).
[[Файл:Diagramma_2_3.jpg|thumb|right|Рис. 1. m = 2, n = 3]]
'''Преобразование 1.''' Предположим, что диаграмма содержит не менее двух трапеций, причем <tex>m\leq leqslant n</tex>. В этом случае отбросим первую строку из <tex>m</tex> точек, но удлиним последние <tex>m</tex> строк нижней трапеции на одну точку(рис. 1). После этого общее число точек не изменится, все строки окажутся различной длины, но четность числа строк изменится.
Точно такое же преобразование можно сделать, если диаграмма состоит из одной трапеции, но <tex>n \geq geqslant m+1</tex>. Стираем верхнюю строку и к нижним <tex>n-1</tex> строчкам приписываем <tex>m</tex> точек.
'''Преобразование 2.'''Пусть теперь диаграмма опять содержит не менее двух трапеций, но <tex>m > n</tex>. Тогда от каждой строки последней трапеции возьмем по одной точке и составим из них первую строку (из <tex> n </tex> точек) новой диаграммы. Это можно сделать, так как <tex>m > n</tex>, и поэтому составленная строка короче первой строки исходной диаграммы. Кроме того, так как мы взяли все строки будут иметь различную длину. Наконец, новая диаграмма содержит столько же точек, что и исходная, но четность числа строк изменилась - новая диаграмма содержит еще одну строку.
Преобразование 2 допускают и диаграммы, состоящие из одной трапеции, если <tex>n \leq leqslant m - 2</tex> (появляющаяся первая строка состоит из <tex>n</tex> точек, она должна быть короче бывшей первой строки, уменьшившейся до <tex>m-1</tex> точки).
Легко видеть, что описанные преобразования взаимно обратны - если сначала сделать одно из них, а потом второе, то снова получим исходную диаграмму. Кроме того, для каждой диаграммы может быть допустимо лишь одно из этих преобразований. Таким образом, диаграммы разбиений числа <tex>N</tex>, допускающие одно из этих преобразований, распадаются на пары диаграмм с четным и нечетным числом строк, поэтому их одинаковое число.
: <tex> p(n) = p(n-1) + p(n-2)+ ... + (-1)^{q+1} (p\left(n - \frac{3q^2 - q}{2}\right) + p\left(n - \frac{3q^2 + q}{2}\right)) </tex>.
Асимптотика <tex> O(n \sqrt{n}) </tex> получается следующим образом. Так как <tex> n - \frac{3q^2 + q}{2} \ge geqslant 0 </tex> , то получаем <tex> q </tex> порядка <tex> \sqrt{n} </tex>, а так как находим n-е число, то получаем <tex> O(n \sqrt{n}) </tex>.
== Используемые материалы Источники информации ==
* [http://en.wikipedia.org/wiki/Pentagonal_number_theorem Pentagonal number theorem]
* [http://kvant.mirror1.mccme.ru/1988/11/razbienie_chisel.htm Вайнштейн Ф., Разбиение чисел. Журнал "Квант" № 11, 1988 год]
* Н.Я. Виленкин "Комбинаторика", 2007. стр. 138-141.
= Примечания =
<references>
<ref name="amount">[http://oeis.org/A000041 Последовательность 000041 на OEIS]</ref>
<ref name="pentagon">[http://ru.wikipedia.org/wiki/%D0%A4%D0%B8%D0%B3%D1%83%D1%80%D0%BD%D1%8B%D0%B5_%D1%87%D0%B8%D1%81%D0%BB%D0%B0#.D0.9F.D1.8F.D1.82.D0.B8.D1.83.D0.B3.D0.BE.D0.BB.D1.8C.D0.BD.D1.8B.D0.B5_.D1.87.D0.B8.D1.81.D0.BB.D0.B0 Пятиугольные числа]</ref>
<ref name="young">[http://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D0%B7%D0%B1%D0%B8%D0%B5%D0%BD%D0%B8%D0%B5_%D1%87%D0%B8%D1%81%D0%BB%D0%B0#.D0.94.D0.B8.D0.B0.D0.B3.D1.80.D0.B0.D0.BC.D0.BC.D1.8B_.D0.AE.D0.BD.D0.B3.D0.B0 Диаграммы Юнга]</ref>
</references>
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
