Асимптотика суммы с участием биномиальных коэффициентов

[zcorvid]

Есть две следующие суммы:

$\sum\limits_{j = 0}^{n}(-1)^j C_{n}^{j}(n - j)^n$

$\sum\limits_{k = 0}^{n - 1}(-1)^k C_{n}^{k}C_{3n - k - 1}^{2n - k}$

Нужно найти их асимптотическое поведение при $n \to \infty$. У меня что-то совсем нет идей, как это правильно делать. Единственное, что смог попытаться - разбить суммы на хвост и середину, хвосты идут до $\sqrt{n}$ и аналогичный симметричный ему, тогда слагаемые хвостов могут быть оценены по оценкам для биномиальных коэффициентов при $k^2 = O(n)$ и для них будет найдено некоторое выражение через $O(f(n))$, для середины, возможно, удастся найти асимптотику, и если она будет не медленнее, чем $f(n)$ найденное при оценке хвостов, то это и будет асимптотика суммы.

К сожалению, пока дальше подобных общих рассуждений продвинуться не удалось. Подскажите, пожалуйста, как такие суммы следует исследовать ? Мне бы хоть какую-нибудь зацепку...

Кстати, мне кажется, для первой из сумм можно попытаться найти явное выражения, используя производящие функции. Возможно это поможет, но пока не уверен.

(Оффтоп)

Задача из ШАД'а, на лекциях и семинарах про суммы было лишь одно утверждение, там находили асимптотическое поведение числа определённых графов, в процессе доказательства использовалась "магия", в ходе которой просто была предъявлена граница, по которой сумма разбивалась на две части. Хватит ли в нашем случае разбиения суммы на части, и как угадать эту границу, пока не понятно.

[Ms-dos4]

zcorvid
Первое - вообще выражаются через известные числа Стирлинга (с точностью до коэффициента $\[n!\]$) поэтому писать ничего не буду.
Второе выражение, кстати, легко считается точно. Например легко получить это используя интегральное представление $\[C_{3n - k - 1}^{2n - k} = \frac{1}{{2\pi i}}\int\limits_{\left| z \right| = \varepsilon } {\frac{{{{(1 + z)}^{3n - k - 1}}}}{{{z^{2n - k + 1}}}}dz} \]$ (это вычет)
В таком случае $\[\sum\limits_{k = 0}^{n - 1} {{{( - 1)}^k}C_n^kC_{3n - k - 1}^{2n - k}} = \frac{1}{{2\pi i}}\int\limits_{\left| z \right| = \varepsilon } {dz\frac{{{{(1 + z)}^{3n - 1}}}}{{{z^{2n + 1}}}}} \sum\limits_{k = 0}^{n - 1} {{{( - 1)}^k}C_n^k{{(\frac{z}{{1 + z}})}^k}} \]$. Сумма $\[\sum\limits_{k = 0}^{n - 1} {{{( - 1)}^k}C_n^k{{(\frac{z}{{1 + z}})}^k}} \]$ прекрасно известна (производящая функция, только т.е. считаем не до $\[n\]$ нужно это учесть) и равна $\[{(\frac{1}{{1 + z}})^n} + {( - 1)^{n + 1}}{(\frac{z}{{1 + z}})^n}\]$. Заметим, что $\[\frac{1}{{2\pi i}}\int\limits_{\left| z \right| = \varepsilon } {\frac{{{{(1 + z)}^{2n - 1}}}}{{{z^{2n + 1}}}}} dz = C_{2n - 1}^{2n} = 0\]$ и $\[\frac{1}{{2\pi i}}\int\limits_{\left| z \right| = \varepsilon } {\frac{{{{(1 + z)}^{2n - 1}}}}{{{z^{n + 1}}}}} dz = C_{2n - 1}^n\]$, поэтому $\[\sum\limits_{k = 0}^{n - 1} {{{( - 1)}^k}C_n^kC_{3n - k - 1}^{2n - k}} = {( - 1)^{n + 1}}C_{2n - 1}^n\]$

[2old]

Я для первой начал думать в сторону деревьев с каким-то набором признаков, просто очень на формулу включений-искючений похоже, ну и там выбираем $j$ вершин на которых не будем строить дерево, а на остальных будем, но последнее это не совсем "правда", потому что было бы $(n-j)^{n-j-2}$ тогда, ну и я застрял, не понятно какой смысл в еще две точки вложить :(

[zcorvid]

Ms-dos4 в сообщении #1064586 писал(а):

zcorvid
Первое - вообще выражаются через известные числа Стирлинга (с точностью до коэффициента $\[n!\]$) поэтому писать ничего не буду.
Второе выражение, кстати, легко считается точно. Например легко получить это используя интегральное представление $\[C_{3n - k - 1}^{2n - k} = \frac{1}{{2\pi i}}\int\limits_{\left| z \right| = \varepsilon } {\frac{{{{(1 + z)}^{3n - k - 1}}}}{{{z^{2n - k + 1}}}}dz} \]$ (это вычет)
В таком случае $\[\sum\limits_{k = 0}^{n - 1} {{{( - 1)}^k}C_n^kC_{3n - k - 1}^{2n - k}} = \frac{1}{{2\pi i}}\int\limits_{\left| z \right| = \varepsilon } {dz\frac{{{{(1 + z)}^{3n - 1}}}}{{{z^{2n + 1}}}}} \sum\limits_{k = 0}^{n - 1} {{{( - 1)}^k}C_n^k{{(\frac{z}{{1 + z}})}^k}} \]$. Сумма $\[\sum\limits_{k = 0}^{n - 1} {{{( - 1)}^k}C_n^k{{(\frac{z}{{1 + z}})}^k}} \]$ прекрасно известна (производящая функция, только т.е. считаем не до $\[n\]$ нужно это учесть) и равна $\[{(\frac{1}{{1 + z}})^n} + {( - 1)^{n + 1}}{(\frac{z}{{1 + z}})^n}\]$. Заметим, что $\[\frac{1}{{2\pi i}}\int\limits_{\left| z \right| = \varepsilon } {\frac{{{{(1 + z)}^{2n - 1}}}}{{{z^{2n + 1}}}}} dz = C_{2n - 1}^{2n} = 0\]$ и $\[\frac{1}{{2\pi i}}\int\limits_{\left| z \right| = \varepsilon } {\frac{{{{(1 + z)}^{2n - 1}}}}{{{z^{n + 1}}}}} dz = C_{2n - 1}^n\]$, поэтому $\[\sum\limits_{k = 0}^{n - 1} {{{( - 1)}^k}C_n^kC_{3n - k - 1}^{2n - k}} = {( - 1)^{n + 1}}C_{2n - 1}^n\]$

Спасибо, разобрался.

С числом Стирлинга чуть пришлось повозиться - я не знал про них и не умел их считать.

Техника с комплексным интегралом очень красивая. Честно говоря не думал, что здесь может так помочь комплексный анализ.

[shurikabv]

Здравствуйте!

zcorvid, подскажите, пожалуйста, как в итоге оценивали числа Стирлинга.

2old, Вы написали

Цитата:

Сумма $\[\sum\limits_{k = 0}^{n - 1} {{{( - 1)}^k}C_n^k{{(\frac{z}{{1 + z}})}^k}} \]$ прекрасно известна

- что за сумма? Как доказывается упомянутое Вами интегральное представление для биномиальных коэффициентов?

Заранее спасибо!

[Ms-dos4]

shurikabv
1)Про числа Стирлинга в интернете информации полно, в т.ч. и асимптотики. Неужели сложно поискать?
2)Про интегральное представление писал я. По поводу суммы - вы что, не знаете бинома Ньютона? Это он самый, $\[{(1 + x)^n}\]$, где $\[x = - \frac{z}{{1 + z}}\]$, только у нас сумма без последнего слагаемого (его мы там и учли).
Интегральное представление вообще очевидно, я же написал, что это вычет (коэффициент при $ \[{z^{ - 1}}\]$) . А если вы присмотритесь, что под интегралом (примените к числителю бином Ньютона) станет ясно, почему $ \[C_n^k = \frac{1}{{2\pi i}}\int\limits_{\left| z \right| = \varepsilon } {\frac{{{{(1 + z)}^n}}}{{{z^{k + 1}}}}dz} \]$