Need асимптотика числа сочетаний С_n^k при небольших k

888julia888

Подскажите, плиз, асимптотическую оценку числа сочетаний С_n^k при больших n и k<=n-2*log_2(n).
Или же достаточно будет, если при больших n все они будут малы по сравнению с С_n^(n-2*log_2)
В идеале, надо найти максимум по x для величины 2^x * sum_{i=1}^{[log(n)]+1} {C_{n-x}^i}, 0<=x<=[log_2(n)+1]
need help!

Afonya

>Подскажите, плиз, асимптотическую оценку числа сочетаний С_n^k при больших n и k<=n-2*log_2(n).
>Или же достаточно будет, если при больших n все они будут малы по сравнению с С_n^(n-2*log_2)
Если имется ввиду область k>=n-2*log_2(n то все остальные члены даже в сумме действительно будут малы по сравнению с крайним. Кроме того, выполняется приближенное равенство С_n^k = n^k/k!
Максимум последнего выражения также достигается на границе. Но для обоснования всего этого нужна не очень приятная возня с малыми величинами.

888julia888

Спасибо !
Черт, ведь и на самом деле имелась в виду область примерно k<log(n) (короче, середина, где k~=n/2 в сумму не входит а не как написал сначала Насколько я понимаю, совет остается верным, так что еще раз спасибо!

naami_moloko

А вообще-то есть формула Стирлинга для факториала, будет всё прозрачно, понятно и обоснованно...

Afonya

Да, именно для таких k это будет верно (к слову, они называются вероятностями больших уклонений )
Что касаемо задачи, то ее проще сделать следующим образом. Пусть F(x) = 2^x * sum_{i=1}^{[log(n)]+1} {C_{n-x}^i} . Покажем, что F(x+1) - F(x) > 0. это следует из того, что при всех i, 2*C_{n-x-1}^i - C_{n-x}^i = 2*C_{n-x-1}^i - C_{n-x-1}^i - C_{n-x-1}^{i-1} = C_{n-x-1}^i - C_{n-x-1}^{i-1} >0 , если i<(n-x-1)/2 , что верно при больших n.
Оставить комментарий
Имя или ник:
Комментарий: