Биномиальный коэффициент, асимптотика

[cyb12]

Возник такой вопрос. Вроде бы понятный факт -- если $\alpha=\alpha(n)=o(n),$ то

$$\binom{n}{\alpha}$$

не может расти как экспонента.
Пробую доказать так - ограничиваю сверху чем-то вроде $\left(\dfrac{n}{\alpha}\right)^{\alpha}$ (остальные множители не пишу). Что с этим можно сделать? Оставить просто $n^{\alpha}$ не получится, например, $\alpha = \dfrac{n}{\ln n}$ и уже экспонента из $n^{\alpha}$. Как быть?

[Sonic86]

Асимптотика в точности выводится из формулы Стирлинга.

cyb12 в сообщении #485752 писал(а):

например, $\alpha = \dfrac{n}{\ln n}$ и уже экспонента из $n^{\alpha}$

С чего Вы это взяли? Рост будет медленнее, чем экспоненциальный. Просто подставьте $\alpha = \dfrac{n}{\ln n}$ и упростите до конца.

[cyb12]

Sonic86 в сообщении #485810 писал(а):

С чего Вы это взяли? Рост будет медленнее, чем экспоненциальный. Просто подставьте $\alpha = \dfrac{n}{\ln n}$ и упростите до конца.

$n^{\alpha} = e^{\alpha \ln n} = e^n,$ что-то не так? Здесь я говорил именно про $n^{\alpha}.$

Sonic86 в сообщении #485810 писал(а):

Асимптотика в точности выводится из формулы Стирлинга.

Мне кажется, что можно проще. Потому что три факториала - это уже неудобно для формулы Стирлинга. Ну хорошо, получится что-нибудь вроде

$$\dfrac{\sqrt{n}}{\sqrt{2\pi\alpha(n-\alpha)}}\dfrac{n^n}{\alpha^{\alpha}(n-\alpha)^{n-\alpha}}$$

Что с этим делать дальше? Я не смог что-то хорошее получить.

[Sonic86]

cyb12 в сообщении #485833 писал(а):

$n^{\alpha} = e^{\alpha \ln n} = e^n,$ что-то не так? Здесь я говорил именно про $n^{\alpha}.$

Так а зачем брать $n^{\alpha}$? У нас же $\left(\dfrac{n}{\alpha}\right)^{\alpha}$ и для него получаем $\left(\dfrac{n}{\alpha}\right)^{\alpha} = (\ln n)^{\frac{n}{\ln n}} = e^{\frac{n \ln \ln n}{\ln n}} \prec e^{c n}$ для любого $c > 0$.
Или Вам нужно нечто другое?

cyb12 в сообщении #485833 писал(а):

Мне кажется, что можно проще. Потому что три факториала - это уже неудобно для формулы Стирлинга. Ну хорошо, получится что-нибудь вроде

$$\dfrac{\sqrt{n}}{\sqrt{2\pi\alpha(n-\alpha)}}\dfrac{n^n}{\alpha^{\alpha}(n-\alpha)^{n-\alpha}}$$

Что с этим делать дальше? Я не смог что-то хорошее получить.

Да упростить просто максимально с учетом $\alpha = o(n)$ (левый множитель, очевидно, упрощается до константы и $\sqrt{\alpha}$). Я через 2 часа домой приду и упрощу, если у Вас не получится. Можно прологарифмировать для удобства. Может и проще можно, не спорю.

[cyb12]

Sonic86 в сообщении #485810 писал(а):

cyb12 в сообщении #485752 писал(а):

например, $\alpha = \dfrac{n}{\ln n}$ и уже экспонента из $n^{\alpha}$

С чего Вы это взяли?

Sonic86 в сообщении #485834 писал(а):

Так а зачем брать $n^{\alpha}$?

Ну я же говорил, если оценивать грубо... Я прекрасно понимаю, что для такого $\alpha$ экспоненты не будет, я ж уточнил, что она будет при "тупом" оценивании. Что ж вы напали-то...

Sonic86 в сообщении #485834 писал(а):

Да упростить просто максимально с учетом $\alpha = o(n)$ (левый множитель, очевидно, упрощается до константы и $\sqrt{\alpha}$).

Ну вообще не знаю, насколько это просто. И почему $\sqrt{\alpha},$ а не $\frac{1}{\sqrt{\alpha}}$?
Вопрос как раз в том, как углядеть все это без формулы Стирлинга...

[Sonic86]

cyb12 в сообщении #485839 писал(а):

Ну я же говорил, если оценивать грубо... Я прекрасно понимаю, что для такого $\alpha$ экспоненты не будет, я ж уточнил, что она будет при "тупом" оценивании. Что ж вы напали-то...

Да я не напал вообще утверждение просто показалось интересным я и попросил уточнить и пишу конкретики побольше

cyb12 в сообщении #485839 писал(а):

Ну вообще не знаю, насколько это просто. И почему $\sqrt{\alpha},$ а не $\frac{1}{\sqrt{\alpha}}$?

Ну да, $\frac{1}{\sqrt{\alpha}}$, $\sqrt{\alpha}$ там будет как подстрока

cyb12 в сообщении #485839 писал(а):

опрос как раз в том, как углядеть все это без формулы Стирлинга...

Без Стирлинга не знаю. Откуда вот можно $\sqrt{2 \pi}$ взять
А! Можно так: взять $\alpha = cn$ и показать, что получается экспонента + доказать, что если $\alpha (n) \prec \beta (n)$, то $\binom{n}{\alpha (n)} \prec \binom{n}{\beta (n)}$. Ведь мы же откуда-то интуитивно утверждение нашли? Наверное, отсюда. Доказывать не пробовал.

[cyb12]

Sonic86 в сообщении #485841 писал(а):

Без Стирлинга не знаю. Откуда вот можно $\sqrt{2 \pi}$ взять

А зачем нам $\sqrt{2\pi}$?
Да, при $\alpha = cn$ будет экспонента.

Sonic86 в сообщении #485841 писал(а):

если $\alpha (n) \prec \beta (n)$, то $\binom{n}{\alpha (n)} \prec \binom{n}{\beta (n)}$.

А это я не представляю, как доказать... Отношение по Стирлингу расписать? Наверное, еще хуже...

[ewert]

cyb12 в сообщении #485833 писал(а):

Ну хорошо, получится что-нибудь вроде

$$\dfrac{\sqrt{n}}{\sqrt{2\pi\alpha(n-\alpha)}}\dfrac{n^n}{\alpha^{\alpha}(n-\alpha)^{n-\alpha}}$$

Что с этим делать дальше? Я не смог что-то хорошее получить.

Сделать стандартную замену: $\frac{\alpha}{n}=t$; получится $\left[t^t(1-t)^{1-t}\right]^{-n}$. И поскольку основание стремится к единице, то и.

[Sonic86]

cyb12 в сообщении #485845 писал(а):

А зачем нам $\sqrt{2\pi}$?

Если асимптотику с точностью до константы считать, то коэффициент будет выражаться через $\sqrt{2\pi}$ - его обычно найти не очень просто.

cyb12 в сообщении #485845 писал(а):

А это я не представляю, как доказать... Отношение по Стирлингу расписать? Наверное, еще хуже...

Сейчас попробую просто просто расписать, посокращать... Ведь просто при $a < b<\frac{n}{2}$ очевидно, что $\binom{n}{a}<\binom{n}{b}$. Значит и тут не сложно должно быть.
...
Только надо доказывать, что если $a(n) \prec b(n) \prec n$, то $\ln \binom{n}{a(n)} \prec \ln \binom{n}{b(n)}$.
...
Хе-хе, матан рулит:
$\ln x! = x \ln x - x + O(\ln x)$
$\ln \binom{n}{x} = n \ln n - (n-x_n) \ln (n-x_n) -x_n \ln x_n + O(\ln x)$
$\ln \binom{n}{a_n} \prec \ln \binom{n}{b_n} \Leftrightarrow $
$(n-b_n) \ln (n-b_n) -b_n \ln b_n +O(\ln n) \prec$ $ (n-a_n) \ln (n-a_n) -a_n \ln a_n +O(\ln n) \Leftrightarrow$
$f(b_n)-f(a_n) \prec O(\ln n)$, где $f(t)=(n-t) \ln (n-t) + t \ln t$.
По теореме Лагранжа $f(b_n)-f(a_n) = f'(\xi _n)(b_n-a_n)$, где $f'(t)=2 - \ln (n-t)+ \ln t = - O(\ln n)$, $\xi _n \in [a_n; b_n]$. И значит
$f'(\xi _n)(b_n-a_n) \prec O(\ln n) \Leftrightarrow (b_n-a_n) \succ O(1)$.

-- Сб сен 24, 2011 10:30:36 --

для $x_n \prec n$ асимптотику $\ln \binom{n}{x_n}$ красивую найти не удалось - какая-то она кривая получается. Т.е. там, например, при $\alpha (n) = \frac{n}{\ln n}$ как раз получается, что в разности $\ln \binom{n}{b_n} - \ln \binom{n}{a_n}$ старшие члены сокращаются и поэтому надо брать несколько членов, получается что-то вроде кусочной функции.

[cyb12]

2ewert
Разве означает то, что если $t^t(1-t)^{1-t}\to 1,$ то $[(t^t(1-t)^{1-t})^{-1}+o(1)]^{n}\prec e^n$? Нет же!

2Sonic86
Не понял последнего:

Sonic86 в сообщении #485880 писал(а):

И значит
$f'(\xi _n)(b_n-a_n) \prec O(\ln n) \Leftrightarrow (b_n-a_n) \succ O(1)$.

Однако.... не верится, что все так сложно...

[ewert]

Ну уж если Стирлинги невместны, то достаточно очень грубой оценки для факториала: $\ln m!>\int\limits_{1}^{m}\ln x\,dx>m\ln m-m,$ откуда $m!>(\frac me)^m.$ Тогда

$C_n^m<\frac{n^m}{m!}<(\frac{ne}{m})^m=\Big[m=\varepsilon(n)\cdot n\Big]=\Big((\frac{e}{\varepsilon})^{\varepsilon}\Big)^n\equiv\theta^n,$

где $\theta(n)=(\frac{e}{\varepsilon(n)})^{\varepsilon(n)}\to1,$ вот и всё.

[Sonic86]

cyb12 в сообщении #485906 писал(а):

Не понял последнего:

Ну я же написал асимптотику для $f ' (\xi _n)$ и просто ее подставил.

cyb12 в сообщении #485906 писал(а):

Однако.... не верится, что все так сложно...

да у меня, наверное, техники не хватает, никогда не считал такие асимптотики. В лоб считать просто текста было бы больше.

[ewert]

cyb12 в сообщении #485906 писал(а):

Разве означает то, что если $t^t(1-t)^{1-t}\to 1,$ то $[(t^t(1-t)^{1-t})^{-1}+o(1)]^{n}\prec e^n$?

Означает. Это означает, что выражение растёт медленнее показательной функции со сколь угодно малым (в смысле сколь угодно близким к единице) основанием.

[cyb12]

2Sonic86
Да, понял, что-то нашло). Однако...

2ewert
Да, Вы правы. Просто сбило, что, например $(1+o(1))^n$ может, например, при $o(1)=\frac{1}{\sqrt{n}}$ быть как $e^{\frac{\sqrt n}2}.$ Хоть это и $\prec e^n.$ Спасибо.

[ewert]

cyb12 в сообщении #485926 писал(а):

$(1+o(1))^n$ может, например, при $o(1)=\frac{1}{\sqrt{n}}$ быть как $e^{\frac{\sqrt n}2}.$

Только двойка-то зачем.