2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Асимптотика числа разбиений
Сообщение30.05.2015, 15:06 
Известно, что асимптотическое выражение для разбиений числа (логарифма числа) $n$ имеет следующий вид:
$ \log p(n) \sim C \sqrt n \mbox { при } n\rightarrow \infty \mbox { где } 
C = \pi\sqrt\frac23$
Для сравнения аналогичное выражение для композиций числа $n$ выглядит как
$ \log p(n)\sim C\ n \mbox { при } n\rightarrow \infty \mbox { где } 
C = 2 $ - из известной легко получаемой формулы для числа слабых(включающих нулевые позиции) композиций
($ \tbinom{n+k-1}{k-1}$), где $k$ положили равным $n$ и применили формулу Стирлинга.

Очень хотелось бы понять, почему "число состояний" целого числа n, подсчитанное таким образом(как число разбиений), пропорционально корню квадратному из $n$ . Асимптотика, получаемая из формулы для числа слабых композиций, приведена для сравнения ( собственно, формула для слабых композиций это статвес системы из $n $ неразличимых частиц, могущих находится в одной из n ячеек, с неограниченным числом частиц в ячейке (бозоны)) В полупопулярных книжках по комбинаторике объяснения "на пальцах" или вывода асимптотики не обнаружил, только отсылки на оригинальные математические работы. Хотелось бы получить от знающих людей качественное объяснение данной зависимости

 
 
 
 Re: Асимптотика числа разбиений
Сообщение30.05.2015, 15:34 
Аватара пользователя
Довольно просто получить оценку $\ln p(n)\leqslant C\sqrt n$ с правильным $C$. Вам известно, что при $|t|<1$
$$
\sum_{n=0}^\infty p(n)t^n=\prod_{n=1}^\infty\frac1{1-t^n}?
$$
Пусть $0<t<1$. Тогда левая часть больше $p(n)t^n$. Теперь разложите логарифм правой части в степенной ряд и оцените сверху. Осталось лишь подобрать оптимальное значение $t$.

Вывод асимптотики -- дело совсем не простое. С решения этой задачи Харди и Литтлвудом и пошел знаменитый круговой метод. Еще там модулярная группа с функцией Дедекинда замешаны.

 
 
 
 Re: Асимптотика числа разбиений
Сообщение01.06.2015, 10:19 
ex-math в сообщении #1021536 писал(а):
и оцените сверху

Нельзя ли этот момент по-подробнее? Очевидно, при логарифмировании правая часть будет равна сумме логарифмов, каждый из которых раскладывается в ряд и при суммировании будет ряд по степеням t с некоторыми коэффициентами, а как делается оценка сверху и корень из $n$ как получается?

 
 
 
 Re: Асимптотика числа разбиений
Сообщение01.06.2015, 21:39 
Аватара пользователя
После разложения логарифмов в ряд нужно поменять порядок суммирования и сложить геометрическую прогрессию. Напишите, что получается. Дальше там один не вполне тривиальный ход, я подскажу.

 
 
 
 Re: Асимптотика числа разбиений
Сообщение02.06.2015, 11:53 
Вроде бы такой ряд получается:
$$
\sum_{n=1}^\infty \frac1{n(1-t^n)}?
$$

 
 
 
 Re: Асимптотика числа разбиений
Сообщение02.06.2015, 13:40 
Аватара пользователя
Не совсем, там первые члены прогрессий $t^n $, а не единицы. Будет так:
$$
\sum_{n=1}^\infty\frac {t^n}{n (1-t^n)}.
$$
А вот теперь в числителе сделаем так:
$$
t^{n-1}\leqslant\frac {1+t+\ldots+t^{n-1}}n.
$$

 
 
 
 Re: Асимптотика числа разбиений
Сообщение04.06.2015, 19:35 
Что-то опять не догоняю.
ex-math в сообщении #1022742 писал(а):
А вот теперь в числителе сделаем так:
$$
t^{n-1}\leqslant\frac {1+t+\ldots+t^{n-1}}n.
$$

Ну, допустим, подставим мы в числитель это выражение, найдем сумму $n $ членов геом. прогрессии, сократим $t^n-1$ в числителе и знаменателе, получим в правой части сходящийся по $n$ ряд, но как получается нужная оценка, не представляю

 
 
 
 Re: Асимптотика числа разбиений
Сообщение04.06.2015, 21:38 
Аватара пользователя
druggist
После сокращения и суммирования ряда выходит
$$
\ln p (n)+n\ln t\leqslant\frac {\pi^2}6\frac t {1-t}.
$$
Теперь переносим второе слагаемое в правую часть. Здесь удобно вместо $t $ ввести новую переменную $u $ с помощью равенства $t=\frac1 {1+u } $. Имеем
$$
\ln p (n)\leqslant n\ln (1+u)+\frac {\pi^2}{6u}\leqslant nu+\frac {\pi^2}{6u}.
$$
Первое слагаемое растет с ростом $u $, а второе убывает. Надо выбрать $u $ так, чтобы они были равны.

 
 
 
 Re: Асимптотика числа разбиений
Сообщение04.06.2015, 22:20 
ex-math в сообщении #1023468 писал(а):
Надо выбрать $u $ так, чтобы они были равны.

Но это и будет минимум по u, если продифференцировать и взять значение правой части в минимуме? В общем, понятно, большое спасибо.

 
 
 
 Re: Асимптотика числа разбиений
Сообщение05.06.2015, 00:51 
Асимптотика, возможно, следует из простейших "квазистатфизических" соображений. Введем для целого неотрицательного числа $E$ "температуру" $T$ - среднеквадратичное отклонение, равное как известно $\sqrt{E}$. Тогда по определению температуры $1/T=dS/dE =1/ \sqrt {E}$, где $S(E)$ - энтропия, равная логарифму числа всевозможных разбиений энергии $E$ на все возможные части (ненулевые целые числа), т. е., логарифму числа микросостояний , что по определению есть число разбиений. Интегрируя, получаем пропорциональность логарифма числа разбиений $E$ квадратному корню из $E$.

 
 
 
 Re: Асимптотика числа разбиений
Сообщение05.06.2015, 09:52 
Аватара пользователя
druggist
Да, можно и продифференцировать, но это чуть больше в плане трудозатрат. Хотя для таких простых функций почти одинаково.
На мой взгляд, очень изящное рассуждение.
В статфизике очень слабо разбираюсь, поэтому оценить предложенный Вами подход не могу :oops:

 
 
 
 Re: Асимптотика числа разбиений
Сообщение05.06.2015, 20:55 
druggist в сообщении #1023523 писал(а):
Введем для целого неотрицательного числа $E$ ... $1/T=dS/dE =1/ \sqrt {E}$, где $S(E)$ - энтропия, равная логарифму числа всевозможных разбиений энергии $E$ на все возможные части (ненулевые целые числа)...Интегрируя
Это Вы дискретные величины дифференцируете и интегрируете?

druggist в сообщении #1023523 писал(а):
Интегрируя, получаем пропорциональность логарифма числа разбиений $E$ квадратному корню из $E$.
Интегрируя, получаем $\sim 2\sqrt{E}$. Почему-то $2\neq \pi\sqrt\frac23$, наверное, в рассуждениях ошибка.

 
 
 
 Re: Асимптотика числа разбиений
Сообщение06.06.2015, 10:54 
Sonic86 в сообщении #1023752 писал(а):
Это Вы дискретные величины дифференцируете и интегрируете?

Так ведь вся статфизика тоже оперирует дискретными величинами - числом частиц, состояний...
Sonic86 в сообщении #1023752 писал(а):
Интегрируя, получаем $\sim 2\sqrt{E}$. Почему-то $2\neq \pi\sqrt\frac23$, наверное, в рассуждениях ошибка.

Скорее всего, да, ошибка и я, возможно, постулирую то, что требуется доказать. Надо еще подумать над обоснованием, но дело, конечно же, не в числовом коэффициенте

 
 
 [ Сообщений: 13 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group