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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (поправил индекс суммирования)
Строка 1: Строка 1:
Задача: Дано число n, найти [http://oeis.org/A000041 количество его различных разбиений на слагаемые] <tex> m_0 + m_1 + m_2 \dots + m_k = n </tex> так что <tex> \forall i: m_i \le m_{i+1} </tex>.
+
'''Задача:''' По заданному числу <tex>n</tex> найти [http://oeis.org/A000041 количество его различных разбиений на слагаемые] <tex> m_0 + m_1 + m_2 \dots + m_k = n </tex> так что <tex> \forall i: m_i \le m_{i+1} </tex>.
  
 
__TOC__
 
__TOC__
  
 
== Алгоритм за n sqrt(n) ==
 
== Алгоритм за n sqrt(n) ==
Рассмотрим самый быстрый алгоритм их нахождения - за <tex> O(n \sqrt{n}) </tex>. Если кто хочет добавить другие алгоритмы, добавьте.
+
Существует несколько алгоритмов решения данной задачи. Рассмотрим самый быстрый алгоритм нахождения количества разбиений числа <tex>n</tex> на слагаемые, который работает за <tex> O(n \sqrt{n}) </tex>.
  
 
Итак, обозначим количество таких разбиений за <tex> p(n) </tex>.
 
Итак, обозначим количество таких разбиений за <tex> p(n) </tex>.
  
Рассмотрим бесконечное произведение
+
Рассмотрим следующее бесконечное произведение
 
<tex> (1 + x + x^2 + \dots)(1 + x^2 + x^4 + \dots) \dots (1 + x^k + x^{2k} + \dots) \dots </tex>
 
<tex> (1 + x + x^2 + \dots)(1 + x^2 + x^4 + \dots) \dots (1 + x^k + x^{2k} + \dots) \dots </tex>
Каждый член произведения получается в результате умножения мономов(одночленов), взятых по одному из каждой скобки. Если в первой скобке взять <tex>x^{m_1}</tex>, во второй — <tex>x^{2m_2}</tex> и т.д., то их произведение будет равно <tex>x^{m_1 + 2m_2 + 3m_3 + \dots}.</tex> Значит, после раскрытия скобок получится сумма мономов вида <tex>x^{m_1 + 2m_2 + 3m_3 + \dots}</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> встретится в полученной бесконечной сумме столько раз, сколькими способами можно представить <math>n</math> как сумму <tex>m_1 + 2m_2 + 3m_3 + ...</tex> Каждому такому представлению отвечает разбиение числа <tex>n</tex> на <tex>m_1</tex> единиц, <tex>m_2</tex> двоек и т.д. Так получаются все разбиения, так как каждое из них, конечно, состоит из нескольких единиц, нескольких двоек и т.д. Поэтому коэффициент при <tex>x^n</tex> равен числу разбиений <tex>p(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>1 + x + x^2 + x^3 + ... = \frac{1}{1 - x}</tex>,
+
: <tex dpi = "145">1 + x + x^2 + x^3 + ... = \frac{1}{1 - x}</tex>,
: <tex>1 + x^2 + x^4 + x^6 + ... = \frac{1}{1-x^2}</tex>
+
: <tex dpi = "145">1 + x^2 + x^4 + x^6 + ... = \frac{1}{1-x^2}</tex>
 
и т.д. Теперь наш результат можно записать так:
 
и т.д. Теперь наш результат можно записать так:
: <tex>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>(1)
+
: <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>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<tex>(1)</tex>
  
Рассмотрим произведение <tex>(1-x)(1-x^2)(1-x^3)...</tex>, т.е. знаменатель правой части формулы (1). Раскрывая в нём скобки, получим такой результат:
+
Рассмотрим произведение <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>
 
: <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>
Показатели в правой части — пятиугольные числа''(при чем тут пятиугольники? o_O )'', т.е. числа вида <tex>(3q^2 \pm q)/2</tex>, а знаки при соответствующих мономах равны <tex>(-1)^q</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 пятиугольные числа], т.е. числа вида <tex>(3q^2 \pm q)/2</tex>, а знаки при соответствующих мономах равны <tex>(-1)^q</tex>. Исходя из этого наблюдения, Эйлер предположил, что должна быть верна следующая теорема, впоследствии названная его именем.
  
 
{{Теорема
 
{{Теорема

Версия 10:15, 14 ноября 2011

Задача: По заданному числу [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].

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