Асимптотика комбинаторного ряда

[Gaary_P]

Необходима найти асимптотику для
$\sum_{k = 0}^{n} (C_n^k)^5$.

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

[Sonic86]

Не знаю, правильно или нет, но можно попробовать метод перевала. Хотя бы в книжках посмотреть, есть там такое или нет.

[sup]

Попробуйте использовать представление (теорема Коши)
$C_n^k = \frac {1}{2\pi i} \int \limits_C \frac {(1+x)^n dx}{x^{k+1}}$
Ну например

$$S_2 = \sum \limits_k (C_n^k)^2 = \sum \limits_k\frac {1}{(2\pi i)^2} \int \int \frac {(1+x)^n (1+y)^n dxdy}{(xy)^{k+1}} = \frac {1}{(2\pi i)^2} \int \int \frac {(1+x)^n (1+y)^n dxdy}{xy - 1}$$

Отсюда

$$S_2 = \frac {1}{2\pi i} \int (1+x)^n(1+1/x)^n \frac{dx}{x} = \frac {1}{2\pi i} \int (1+x)^{2n}\frac{dx}{x^{n+1}} = C_{2n}^n$$

С двойкой, однако, повезло. Уже с тройкой сложнее

$$S_3 = \frac {1}{(2\pi i)^2} \int \int (1+x)^n(1+y)^n (1+xy)^n \frac{dxdy}{(xy)^{n+1}}$$

Далее стандартно $x = e^{i\alpha}$, $y = e^{i\beta}$. Получим интеграл, к которому применяем метод Лапласа.
С пятой степенью аналогично. Отмечу лишь, что для малых $\varphi$ стоит использовать приближенное равенство $\cos(\varphi) \approx e^{-\varphi^2/2}$

[Vince Diesel]

Можно попробовать так. Обозначим

$$ S_m(n)=\sum_{k=0}^n (C_n^k)^m. $$

Если $\xi$ - с.в., принимающая значения 0 и 1 с вероятностью $1/2$, и $\xi_i$ — iid как $\xi$, то вероятность того, что $\eta=\xi_1+\ldots+\xi_n=k$ равна $2^{-n}C_n^k$. Если теперь $\eta_i$ iid как $\eta$, то $S_m(n)=2^{mn}P(\eta_1=\eta_2=\ldots=\eta_m)$. Сдвигом системы координат в точку $(n/2,\ldots,n/2)$ и растяжением можно добиться того, что среднее $\eta_i$ будет равно нулю, а дисперсия единице.

При больших $n$ распределение $\eta_i$ будет похоже на нормальное. А $2^{-mn}S_m(n)$ — на плотность вероятности $\nu_1=\ldots=\nu_m$, где $\nu_i\sim N(0,1)$ (с точностью до константы). Последняя равна (интегрируем плотность нормального $n$-мерного распределение по прямой $x_1=\ldots=x_n$)

$$ (2 \pi )^{-\frac{m}{2}}\int_{-\infty }^{\infty } e^{-\frac{1}{2} m x^2} \, dx= \frac1{\sqrt{m}{(2 \pi )^{\frac{m-1}{2}}}}. $$

Масштабируя обратно и умножая на $2^{mn}$ получим приближенное значение исходной суммы (которое должно быть главным членом асимптотики). У меня вышло

$$ S_m(n)\approx\frac{2^{mn}}{\sqrt{m}(\pi n/2)^{\frac{m-1}{2}}}}. $$

[ewert]

Gaary_P в сообщении #777582 писал(а):

Начала делать представлением факториала по формуле Стирлинга, но там все очень плохо получается.

Там всё очень хорошо и очень тупо получается. Для $C_n^{\frac{n}2+k}$ выплывает выражение вида

$$\dfrac{n^n}{\left(\frac{n^2}4-k^2\right)^{\frac{n}2}}\cdot\left(\dfrac{\frac{n}2-k}{\frac{n}2+k}\right)^k=2^ne^{n\,f(x_k)},$$

где $x_k=\frac{2k}n\in(-1;1)$ и $f(x)=-\frac12\,\ln(1-x^2)+\frac{x}2\,\ln\frac{1-x}{1+x}$. Сумма -- интегральная, а дальше просто метод Лапласа. Причём вторую производную в нуле даже считать не надо -- эта функция в уме раскладывается в ряд.

Если, конечно, нужен только главный член асимптотики. Если же весь ряд, то в любом случае вряд ли что выйдет.

[RIP]

topic25283.html