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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Алгоритм за O(N3/2): Алгоритм за n^(3/2) не является самым быстрым, задача решается за nlogn)
(не показано 13 промежуточных версий 5 участников)
Строка 1: Строка 1:
 
{{Задача
 
{{Задача
 
|definition =
 
|definition =
  По заданному числу <tex>n</tex> найти количество его различных разбиений на слагаемые<ref name="amount" /> <tex> m_0 + m_1 + m_2 \dots + m_k = n </tex> так что при всех <tex> i: m_i \leqslant m_{i+1} </tex>.}}
+
  По заданному числу <tex>n</tex> найти количество его различных разбиений на положительные слагаемые<ref name="amount" /> <tex> m_0 + m_1 + m_2 + \ldots + m_k = n </tex> так, что при всех <tex> i\colon m_i \leqslant m_{i+1} </tex>.}}
  
 
__TOC__
 
__TOC__
Строка 9: Строка 9:
 
Имеет место следующее рекуррентное соотношение:
 
Имеет место следующее рекуррентное соотношение:
 
<p>
 
<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>
+
<tex dpi = "145">P(n, m, k) =  
 +
\left \{\begin{array}{ll}P(n, m, k - 1) + P(n - k, m - 1, k), & 0 < m \leqslant n, 0 < k \leqslant n \\
 +
P(n, m, n), & k > n \\
 +
1, & n = 0, m = 0 \\
 +
0, & \text{otherwise} \end{array} \right.
 +
</tex>
 
</p>
 
</p>
Начальные условия
 
  
<tex>P(0,0,i) = 1, \forall i \geqslant 0</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>P(i,0,j) = 0, \forall i,j > 0</tex>
+
Количество всех разбиений числа равно <tex>\sum\limits_{i=0}^nP(n, i, n)</tex>. Реализация данного алгоритма методом [[Динамическое программирование|динамического программирования]] с меморизацией будет иметь асимптотику <tex>O(n^{3})</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>) ==
 
== Алгоритм за O(N<sup>2</sup>) ==
 
Обозначим <tex>P(n,k)</tex> — количество разбиений числа <tex>n</tex> на слагаемые, каждое из которых не превосходит <tex>k</tex>. Оно удовлетворяет следующей рекурентной формуле:<p>
 
Обозначим <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>
+
<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>
 
</p>
При этом считается что
 
  
<tex>P(0,0) = 1</tex>
+
Заметим, что нам не нужно считать количество слагаемых <tex>m</tex> в разбиении. Достаточно посчитать <tex>P(n, k)</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> P(i, 0) = 0, \forall i>0</tex>
+
Количество всех разбиений числа <tex>n</tex> равно <tex>P(n,n)</tex>. Асимптотика <tex>O(n^{2})</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>) ==
 
== Алгоритм за O(N<sup>3/2</sup>) ==
Рассмотрим самый быстрый алгоритм нахождения количества разбиений числа <tex>n</tex> на слагаемые, который работает за <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 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 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> 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 + ... = \frac{1}{1 - x}</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 + ... = \frac{1}{1-x^2}</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>p(n)</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>&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 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>
  
Строка 89: Строка 66:
 
Пентагональная теорема Эйлера
 
Пентагональная теорема Эйлера
 
| statement =  
 
| statement =  
<tex> \prod\limits_{k=1}^\infty \left(1-x^k \right) = \sum\limits_{q=-\infty}^\infty (-1)^q x^{\frac{3q^2+q}{2}}</tex>
+
<tex dpi="145"> \prod\limits_{k=1}^\infty \left(1-x^k \right) = \sum\limits_{q=-\infty}^\infty (-1)^q x^{\frac{3q^2+q}{2}}</tex>
 
| proof =
 
| proof =
 
<tex>A = (1-x)(1-x^2)(1-x^3)...(1-x^n)...</tex>
 
<tex>A = (1-x)(1-x^2)(1-x^3)...(1-x^n)...</tex>
  
Раскроем в этом произведении первые 22 скобки. Мы получим выражение  
+
Раскроем в этом произведении первые <tex>22</tex> скобки. Мы получим выражение  
  
 
<tex>A = [1-x-x^2+x^5+x^7-x^{12}-x^{15}+x^{22}+...]\times(1-x^{23})(1-x^{24})...(1-x^n)...</tex>,
 
<tex>A = [1-x-x^2+x^5+x^7-x^{12}-x^{15}+x^{22}+...]\times(1-x^{23})(1-x^{24})...(1-x^n)...</tex>,
  
где в квадратной скобке точками обозначены слагаемые, содержащие <tex>x</tex> в более высокой степени, чем 22. Не будем выписывать эти члены, так как после умножения квадратной скобки на <tex>1-x^{23}</tex>, <tex>1-x^{24}</tex> и т.д. они изменятся. Выписанные же члены больше меняться не будут. Поэтому, если раскрыть все скобки, то получится бесконечный ряд, первые члены которого имеют вид
+
где в квадратной скобке точками обозначены слагаемые, содержащие <tex>x</tex> в более высокой степени, чем <tex>22</tex>. Не будем выписывать эти члены, так как после умножения квадратной скобки на <tex>1-x^{23}</tex>, <tex>1-x^{24}</tex> и т.д. они изменятся. Выписанные же члены больше меняться не будут. Поэтому, если раскрыть все скобки, то получится бесконечный ряд, первые члены которого имеют вид
  
 
<tex>A=1-x-x^2+x^5+x^7-x^{12}-x^{15}+x^{22}+...</tex>
 
<tex>A=1-x-x^2+x^5+x^7-x^{12}-x^{15}+x^{22}+...</tex>
Строка 105: Строка 82:
 
<tex>A = (1-x)(1-x^2)(1-x^3)...(1-x^n)...</tex>
 
<tex>A = (1-x)(1-x^2)(1-x^3)...(1-x^n)...</tex>
  
в ряд, то в этом ряду отличны от нуля лишь слагаемые, вида <tex>(-1)^q x^{\frac{3q^2+q}{2}}</tex>, где <tex>q</tex> - натуральное число.
+
в ряд, то в этом ряду отличны от нуля лишь слагаемые, вида <tex dpi="145">(-1)^q x^{\frac{3q^2+q}{2}}</tex>, где <tex>q</tex> натуральное число.
  
При раскрытии скобок в исходном произведении слагаемое <tex>\pm x^N</tex> встретится столько раз, сколькими способами можно разбить число <tex>N</tex> на различные слагаемые. При этом, если число слагаемых четно, то появляется <tex>x^N</tex>, а если это число нечетно, то появляется <tex>-x^N</tex>. Например, разбиению <tex>12=5+4+2+1</tex> - соответствует слагаемое <tex>(-x^5)(-x^4)(-x^2)(-x^1)=x^{12},</tex> а разбиению <tex>12=5+4+3</tex> - слагаемое <tex>(-x^5)(-x^4)(-x^3)=-x^{12}</tex>. Таким образом, коэффициент при <tex>x^N</tex> в разложении <tex>A</tex> в ряд равен разности между количеством разбиений <tex>N</tex> на четное число различных слагаемых и количеством разбиений <tex>N</tex> на нечетное число различных слагаемых. Тогда теорему можно переформулировать следующим образом:
+
При раскрытии скобок в исходном произведении слагаемое <tex>\pm x^N</tex> встретится столько раз, сколькими способами можно разбить число <tex>N</tex> на различные слагаемые. При этом, если число слагаемых четно, то появляется <tex>x^N</tex>, а если это число нечетно, то появляется <tex>-x^N</tex>. Например, разбиению <tex>12=5+4+2+1</tex> соответствует слагаемое <tex>(-x^5)(-x^4)(-x^2)(-x^1)=x^{12},</tex> а разбиению <tex>12=5+4+3</tex> слагаемое <tex>(-x^5)(-x^4)(-x^3)=-x^{12}</tex>. Таким образом, коэффициент при <tex>x^N</tex> в разложении <tex>A</tex> в ряд равен разности между количеством разбиений <tex>N</tex> на четное число различных слагаемых и количеством разбиений <tex>N</tex> на нечетное число различных слагаемых. Тогда теорему можно переформулировать следующим образом:
  
 
{{Теорема
 
{{Теорема
Строка 113: Строка 90:
 
Переформулировка пентагональной теоремы
 
Переформулировка пентагональной теоремы
 
| statement =  
 
| statement =  
Если число <tex>N</tex> не может быть представлено в виде <tex>N =\frac{3q^2+q}{2}</tex>, то оно имеет одинаковое количество разбиений на четное и на нечетное число различных слагаемых. А для чисел вида <tex>N =\frac{3q^2+q}{2}</tex> разность между этими количествами равна <tex>(-1)^q</tex>.
+
Если число <tex>N</tex> не может быть представлено в виде <tex dpi="145">N =\frac{3q^2+q}{2}</tex>, то оно имеет одинаковое количество разбиений на четное и на нечетное число различных слагаемых. А для чисел вида <tex dpi="145">N =\frac{3q^2+q}{2}</tex> разность между этими количествами равна <tex>(-1)^q</tex>.
 
}}
 
}}
  
Иными словами, если <tex>q</tex> четно, то на одно больше разбиений на четное число слагаемых, а если <tex>q</tex> нечетно, то на одно больше разбиений на нечетно число слагаемых. Докажем эту теорему с помощью диаграмм Юнга<ref name="young" />. Покажем несколько способов превращения диаграммы с четным числом строк  диаграмму из стольких же точек с нечетным числом строк и обратно.
+
Иными словами, если <tex>q</tex> четно, то на одно больше разбиений на четное число слагаемых, а если <tex>q</tex> нечетно, то на одно больше разбиений на нечетное число слагаемых. Докажем эту теорему с помощью диаграмм Юнга<ref name="young" />. Покажем несколько способов превращения диаграммы с четным числом строк  диаграмму из стольких же точек с нечетным числом строк и обратно.
  
 
Так как мы рассматриваем лишь разбиения на различные слагаемые, то диаграммы таких разбиений состоят из нескольких трапеций, поставленных друг на друга. Обозначим число точек в верхней строке диаграммы через <tex>m</tex>, а число строк нижней трапеции через <tex>n</tex> (на рис. 1 слева  изображена диаграмма, для которой <tex>m=2</tex>, <tex>n=3</tex>).
 
Так как мы рассматриваем лишь разбиения на различные слагаемые, то диаграммы таких разбиений состоят из нескольких трапеций, поставленных друг на друга. Обозначим число точек в верхней строке диаграммы через <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]]
+
[[Файл:Diagramma_2_3.jpg|thumb|right|500px|Рис. 1. <tex>m = 2, n = 3</tex>]]
  
'''Преобразование 1.''' Предположим, что диаграмма содержит не менее двух трапеций, причем <tex>m \leqslant n</tex>. В этом случае отбросим первую строку из <tex>m</tex> точек, но удлиним последние <tex>m</tex> строк нижней трапеции на одну точку(рис. 1). После этого общее число точек не изменится, все строки окажутся различной длины, но четность числа строк изменится.
+
'''Преобразование 1.''' Предположим, что диаграмма содержит не менее двух трапеций, причем <tex>m \leqslant n</tex>. В этом случае отбросим первую строку из <tex>m</tex> точек, но удлиним последние <tex>m</tex> строк нижней трапеции на одну точку (рис. 1). После этого общее число точек не изменится, все строки окажутся различной длины, но четность числа строк изменится.
  
 
Точно такое же преобразование можно сделать, если диаграмма состоит из одной  трапеции, но <tex>n \geqslant m+1</tex>. Стираем верхнюю строку и к нижним <tex>n-1</tex> строчкам приписываем <tex>m</tex> точек.
 
Точно такое же преобразование можно сделать, если диаграмма состоит из одной  трапеции, но <tex>n \geqslant m+1</tex>. Стираем верхнюю строку и к нижним <tex>n-1</tex> строчкам приписываем <tex>m</tex> точек.
Строка 133: Строка 110:
 
Осталось выяснить, какие же диаграммы не допускают ни одного из описанных преобразований. Ясно, что эти диаграммы состоят из одной трапеции, причем для них либо <tex>m=n</tex>, либо <tex>m=n+1</tex>. В первом случае диаграмма содержит
 
Осталось выяснить, какие же диаграммы не допускают ни одного из описанных преобразований. Ясно, что эти диаграммы состоят из одной трапеции, причем для них либо <tex>m=n</tex>, либо <tex>m=n+1</tex>. В первом случае диаграмма содержит
  
<tex>n+(n+1)+(n+2)+\dots+(2n-1)=\frac{3n^2-n}{2}</tex>
+
<tex dpi="145">n+(n+1)+(n+2)+\dots+(2n-1)=\frac{3n^2-n}{2}</tex>
  
точек, а во втором - на <tex>n</tex> точек больше, т.е. <tex>\frac{3n^2+n}{2}</tex>.
+
точек, а во втором - на <tex>n</tex> точек больше, т.е. <tex dpi="145">\frac{3n^2+n}{2}</tex>.
  
Приведенные рассуждения показывают, что если <tex>N</tex> не является числом вида <tex>\frac{3n^2 \pm n}{2}</tex>, то оно имеет поровну разбиений на четное и нечетное число различных слагаемых.
+
Приведенные рассуждения показывают, что если <tex>N</tex> не является числом вида <tex dpi="145">\frac{3n^2 \pm n}{2}</tex>, то оно имеет поровну разбиений на четное и нечетное число различных слагаемых.
  
Очевидно также, что равенства <tex>N=\frac{3n^2+n}{2}</tex> и <tex>N=\frac{3l^2-l}{2}</tex> одновременно выполняться не могут, поэтому если <tex>N=\frac{3n^2\pm n}{2}</tex>, то без пары останется ровно одна диаграмма, не допускающая преобразования и имеющая <tex>n</tex> строк (слагаемых <tex>N</tex>). Если <tex>n</tex> - четное число, то разбиений на четное число слагаемых окажется на 1 больше, чем на нечетное число слагаемых. Если же <tex>n</tex> - нечетное число, то на 1 больше будет разбиений на нечетное число слагаемых. Теорема доказана.
+
Очевидно также, что равенства <tex dpi="145">N=\frac{3n^2+n}{2}</tex> и <tex dpi="145">N=\frac{3l^2-l}{2}</tex> одновременно выполняться не могут, поэтому если <tex dpi ="145">N=\frac{3n^2\pm n}{2}</tex>, то без пары останется ровно одна диаграмма, не допускающая преобразования и имеющая <tex>n</tex> строк (слагаемых <tex>N</tex>). Если <tex>n</tex> - четное число, то разбиений на четное число слагаемых окажется на <tex>1</tex> больше, чем на нечетное число слагаемых. Если же <tex>n</tex> - нечетное число, то на <tex>1</tex> больше будет разбиений на нечетное число слагаемых. Теорема доказана.
  
 
}}
 
}}
  
Умножим обе части равенства (1) на <tex>\prod\limits_{k=1}^\infty \left(1-x^k \right) </tex> и воспользуемся пентагональной теоремой:
+
Умножим обе части равенства <tex>(1)</tex> на <tex>\prod\limits_{k=1}^\infty \left(1-x^k \right) </tex> и воспользуемся пентагональной теоремой:
: <tex> ( p(0) + p(1) x + p(2) x^2 + \dots)(1 - x - x^2 + x^5 + x^7 - x^{12} - x^{15} + \dots) = 1 </tex> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(2)
+
: <tex> ( p(0) + p(1) x + p(2) x^2 + \dots)(1 - x - x^2 + x^5 + x^7 - x^{12} - x^{15} + \dots) = 1 </tex> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<tex>(2)</tex>
  
Начнем раскрывать скобки, для наглядности мономы с одинаковыми степенями x пишем друг под другом:
+
Начнем раскрывать скобки, для наглядности мономы с одинаковыми степенями <tex>x</tex> пишем друг под другом:
 
: <tex> 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 </tex>
 
: <tex> 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 </tex>
 
::&nbsp;&nbsp;&nbsp;&nbsp;<tex> - p(0)x - p(1) x^2 - p(2) x^3 - p(3) x^4 - p(4) x^5 - p(5) x^6 - \dots </tex>
 
::&nbsp;&nbsp;&nbsp;&nbsp;<tex> - p(0)x - p(1) x^2 - p(2) x^3 - p(3) x^4 - p(4) x^5 - p(5) x^6 - \dots </tex>
Строка 152: Строка 129:
 
::::::::::::: &nbsp;<tex>+ p(0) x^5 + p(1) x^6 + \dots </tex>     
 
::::::::::::: &nbsp;<tex>+ p(0) x^5 + p(1) x^6 + \dots </tex>     
  
Так как p(0) = 1, то оно сокращается с единицей справа. Так что, чтобы выражение (2) было удовлетворено при любом x, все коэффициенты должны быть равны 0. Поэтому:
+
Так как <tex>p(0) = 1</tex>, то оно сокращается с единицей справа. Так что, чтобы выражение <tex>(2)</tex> было удовлетворено при любом <tex>x</tex>, все коэффициенты должны быть равны <tex>0</tex>. Поэтому:
 
: <tex> p(1) = p(0) </tex>
 
: <tex> p(1) = p(0) </tex>
 
: <tex> p(2) = p(1) + p(0) </tex>
 
: <tex> p(2) = p(1) + p(0) </tex>
Строка 158: Строка 135:
 
: <tex> p(4) = p(3) + p(2) </tex>
 
: <tex> p(4) = p(3) + p(2) </tex>
 
: <tex> p(5) = p(4) + p(3) - p(0) </tex>
 
: <tex> p(5) = p(4) + p(3) - p(0) </tex>
и т.д.
+
: <tex>...</tex>
  
 
Получаем формулу Эйлера, позволяющую последовательно находить числа <tex>p(n)</tex>:
 
Получаем формулу Эйлера, позволяющую последовательно находить числа <tex>p(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 dpi="145"> 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 dpi="145"> n - \frac{3q^2 + q}{2} \geqslant 0 </tex> , то получаем <tex> q </tex> порядка <tex> \sqrt{n} </tex>, а так как находим <tex>n</tex>-е число, то получаем <tex> O(n \sqrt{n}) </tex>.
 +
 
 +
== Примечания ==
 +
<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>
  
Асимптотика <tex> O(n \sqrt{n}) </tex> получается следующим образом. Так как <tex> n - \frac{3q^2 + q}{2} \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://en.wikipedia.org/wiki/Pentagonal_number_theorem Wikipedia {{---}} Pentagonal number theorem]
 
* [http://kvant.mirror1.mccme.ru/1988/11/razbienie_chisel.htm Вайнштейн Ф., Разбиение чисел. Журнал "Квант" № 11, 1988 год]
 
* [http://kvant.mirror1.mccme.ru/1988/11/razbienie_chisel.htm Вайнштейн Ф., Разбиение чисел. Журнал "Квант" № 11, 1988 год]
 
* Н.Я. Виленкин "Комбинаторика", 2007. стр. 138-141.
 
* Н.Я. Виленкин "Комбинаторика", 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>
 
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Комбинаторика]]
 
[[Категория: Комбинаторика]]

Версия 20:55, 30 июня 2020

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


Алгоритм за O(N3)

Пусть [math]P(n, m, k)[/math] — количество разбиений числа [math]n[/math] на [math]m[/math] слагаемых, каждое из которых не превосходит [math]k[/math]. Имеет место следующее рекуррентное соотношение:

[math]P(n, m, k) = \left \{\begin{array}{ll}P(n, m, k - 1) + P(n - k, m - 1, k), & 0 \lt m \leqslant n, 0 \lt k \leqslant n \\ P(n, m, n), & k \gt n \\ 1, & n = 0, m = 0 \\ 0, & \text{otherwise} \end{array} \right. [/math]

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

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

Алгоритм за O(N2)

Обозначим [math]P(n,k)[/math] — количество разбиений числа [math]n[/math] на слагаемые, каждое из которых не превосходит [math]k[/math]. Оно удовлетворяет следующей рекурентной формуле:

[math]P(n,k) = \left \{ \begin{array}{ll} P(n,k - 1) + P(n - k, k), & 0 \lt k \leqslant n \\ P(n, n), & k \gt n \\ 1, & n = 0, k = 0 \\ 0, & n \neq 0 , k = 0 \end{array} \right.[/math]

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

Количество всех разбиений числа [math]n[/math] равно [math]P(n,n)[/math]. Асимптотика [math]O(n^{2})[/math].

Алгоритм за O(N3/2)

Рассмотрим алгоритм нахождения количества разбиений числа [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]0 \leqslant x \lt 1[/math], по формуле ее суммирования:

[math]1 + x + x^2 + x^3 + \dots = \frac{1}{1 - x}[/math],
[math]1 + x^2 + x^4 + x^6 + \dots = \frac{1}{1-x^2}[/math]
[math]\dots[/math]
[math]1 + x^k + x^{2k} + x^{3k} + \dots = \frac{1}{1-x^k}[/math]
[math]\dots[/math]

Запишем теперь производящую функцию последовательности [math]p(n)[/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]

Показатели степеней в правой части — пятиугольные числа[2], т.е. числа вида [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^{\frac{3q^2+q}{2}}[/math]
Доказательство:
[math]\triangleright[/math]

[math]A = (1-x)(1-x^2)(1-x^3)...(1-x^n)...[/math]

Раскроем в этом произведении первые [math]22[/math] скобки. Мы получим выражение

[math]A = [1-x-x^2+x^5+x^7-x^{12}-x^{15}+x^{22}+...]\times(1-x^{23})(1-x^{24})...(1-x^n)...[/math],

где в квадратной скобке точками обозначены слагаемые, содержащие [math]x[/math] в более высокой степени, чем [math]22[/math]. Не будем выписывать эти члены, так как после умножения квадратной скобки на [math]1-x^{23}[/math], [math]1-x^{24}[/math] и т.д. они изменятся. Выписанные же члены больше меняться не будут. Поэтому, если раскрыть все скобки, то получится бесконечный ряд, первые члены которого имеют вид

[math]A=1-x-x^2+x^5+x^7-x^{12}-x^{15}+x^{22}+...[/math]

Анализируя этот ряд, Эйлер пришел к выводу, что, если превратить бесконечное произведение

[math]A = (1-x)(1-x^2)(1-x^3)...(1-x^n)...[/math]

в ряд, то в этом ряду отличны от нуля лишь слагаемые, вида [math](-1)^q x^{\frac{3q^2+q}{2}}[/math], где [math]q[/math] — натуральное число.

При раскрытии скобок в исходном произведении слагаемое [math]\pm x^N[/math] встретится столько раз, сколькими способами можно разбить число [math]N[/math] на различные слагаемые. При этом, если число слагаемых четно, то появляется [math]x^N[/math], а если это число нечетно, то появляется [math]-x^N[/math]. Например, разбиению [math]12=5+4+2+1[/math] соответствует слагаемое [math](-x^5)(-x^4)(-x^2)(-x^1)=x^{12},[/math] а разбиению [math]12=5+4+3[/math] — слагаемое [math](-x^5)(-x^4)(-x^3)=-x^{12}[/math]. Таким образом, коэффициент при [math]x^N[/math] в разложении [math]A[/math] в ряд равен разности между количеством разбиений [math]N[/math] на четное число различных слагаемых и количеством разбиений [math]N[/math] на нечетное число различных слагаемых. Тогда теорему можно переформулировать следующим образом:

Теорема (Переформулировка пентагональной теоремы):
Если число [math]N[/math] не может быть представлено в виде [math]N =\frac{3q^2+q}{2}[/math], то оно имеет одинаковое количество разбиений на четное и на нечетное число различных слагаемых. А для чисел вида [math]N =\frac{3q^2+q}{2}[/math] разность между этими количествами равна [math](-1)^q[/math].

Иными словами, если [math]q[/math] четно, то на одно больше разбиений на четное число слагаемых, а если [math]q[/math] нечетно, то на одно больше разбиений на нечетное число слагаемых. Докажем эту теорему с помощью диаграмм Юнга[3]. Покажем несколько способов превращения диаграммы с четным числом строк диаграмму из стольких же точек с нечетным числом строк и обратно.

Так как мы рассматриваем лишь разбиения на различные слагаемые, то диаграммы таких разбиений состоят из нескольких трапеций, поставленных друг на друга. Обозначим число точек в верхней строке диаграммы через [math]m[/math], а число строк нижней трапеции через [math]n[/math] (на рис. 1 слева изображена диаграмма, для которой [math]m=2[/math], [math]n=3[/math]).

Рис. 1. [math]m = 2, n = 3[/math]

Преобразование 1. Предположим, что диаграмма содержит не менее двух трапеций, причем [math]m \leqslant n[/math]. В этом случае отбросим первую строку из [math]m[/math] точек, но удлиним последние [math]m[/math] строк нижней трапеции на одну точку (рис. 1). После этого общее число точек не изменится, все строки окажутся различной длины, но четность числа строк изменится.

Точно такое же преобразование можно сделать, если диаграмма состоит из одной трапеции, но [math]n \geqslant m+1[/math]. Стираем верхнюю строку и к нижним [math]n-1[/math] строчкам приписываем [math]m[/math] точек.

Преобразование 2.Пусть теперь диаграмма опять содержит не менее двух трапеций, но [math]m \gt n[/math]. Тогда от каждой строки последней трапеции возьмем по одной точке и составим из них первую строку (из [math] n [/math] точек) новой диаграммы. Это можно сделать, так как [math]m \gt n[/math], и поэтому составленная строка короче первой строки исходной диаграммы. Кроме того, так как мы взяли все строки будут иметь различную длину. Наконец, новая диаграмма содержит столько же точек, что и исходная, но четность числа строк изменилась - новая диаграмма содержит еще одну строку.

Преобразование 2 допускают и диаграммы, состоящие из одной трапеции, если [math]n \leqslant m - 2[/math] (появляющаяся первая строка состоит из [math]n[/math] точек, она должна быть короче бывшей первой строки, уменьшившейся до [math]m-1[/math] точки).

Легко видеть, что описанные преобразования взаимно обратны - если сначала сделать одно из них, а потом второе, то снова получим исходную диаграмму. Кроме того, для каждой диаграммы может быть допустимо лишь одно из этих преобразований. Таким образом, диаграммы разбиений числа [math]N[/math], допускающие одно из этих преобразований, распадаются на пары диаграмм с четным и нечетным числом строк, поэтому их одинаковое число.

Осталось выяснить, какие же диаграммы не допускают ни одного из описанных преобразований. Ясно, что эти диаграммы состоят из одной трапеции, причем для них либо [math]m=n[/math], либо [math]m=n+1[/math]. В первом случае диаграмма содержит

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

точек, а во втором - на [math]n[/math] точек больше, т.е. [math]\frac{3n^2+n}{2}[/math].

Приведенные рассуждения показывают, что если [math]N[/math] не является числом вида [math]\frac{3n^2 \pm n}{2}[/math], то оно имеет поровну разбиений на четное и нечетное число различных слагаемых.

Очевидно также, что равенства [math]N=\frac{3n^2+n}{2}[/math] и [math]N=\frac{3l^2-l}{2}[/math] одновременно выполняться не могут, поэтому если [math]N=\frac{3n^2\pm n}{2}[/math], то без пары останется ровно одна диаграмма, не допускающая преобразования и имеющая [math]n[/math] строк (слагаемых [math]N[/math]). Если [math]n[/math] - четное число, то разбиений на четное число слагаемых окажется на [math]1[/math] больше, чем на нечетное число слагаемых. Если же [math]n[/math] - нечетное число, то на [math]1[/math] больше будет разбиений на нечетное число слагаемых. Теорема доказана.
[math]\triangleleft[/math]

Умножим обе части равенства [math](1)[/math] на [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]      [math](2)[/math]

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

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

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

[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]...[/math]

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

[math] 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)) [/math].

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

Примечания

См. также

Источники информации