Найти сумму

[Leox]

Доказать, что

$$ \sum_{k=1}^n (-1)^k {n \choose k} k^n=(-1)^n n!, $$

$$ \sum_{k=1}^n {n \choose k} k^{k-1} (n-k+1)^{n-k}=n(n+1)^{n-1}. $$

Хотя бы идею подскажите.

[Integrall]

Leox в сообщении #568868 писал(а):

Хотя бы идею подскажите.

бином ньютона знаете?

[Leox]

Integrall в сообщении #568879 писал(а):

Leox в сообщении #568868 писал(а):

Хотя бы идею подскажите.

бином ньютона знаете?

знаю.. и что, нужно разложить слева и справа?
справа просится переписать в виде $(n-k+1+k)^{n-1}$

[Integrall]

Leox в сообщении #568907 писал(а):

знаю.. и что, нужно разложить слева и справа?

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

[Leox]

Integrall в сообщении #568910 писал(а):

Leox в сообщении #568907 писал(а):

знаю.. и что, нужно разложить слева и справа?

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

если бы так $k$ было в степени $k$ то там был бы почти бином $(n+1)^n$

[Хорхе]

Не уверен, что бином тут поможет, Ньютона ли или еще кого. В первом есть простая комбинаторная интерпретация с отображениями множества $\{1,2,\dots,n\}$ в себя и формулой включения-исключения.

Во втором можно чуть иначе его переписать и тоже придумать не самую простую комбинаторную интерпретацию с деревьями Кейли. Можно свести к некоторым (не слишком) хитрым соотношениям с функцией деревьев Кейли $T(z) = \sum_{n\ge 0} \frac{n^n}{n!}z^n$. Но ничего простого не видно.

Идею подсказал

[Leox]

Хорхе в сообщении #568920 писал(а):

Не уверен, что бином тут поможет, Ньютона ли или еще кого. В первом есть простая комбинаторная интерпретация с отображениями множества $\{1,2,\dots,n\}$ в себя и формулой включения-исключения.

Во втором можно чуть иначе его переписать и тоже придумать не самую простую комбинаторную интерпретацию с деревьями Кейли. Можно свести к некоторым (не слишком) хитрым соотношениям с функцией деревьев Кейли $T(z) = \sum_{n\ge 0} \frac{n^n}{n!}z^n$. Но ничего простого не видно.

Идею подсказал

спасибо.. попробую формулу включения-исключения для первой задачи

[Хорхе]

Если что, вторая задача - это (с точностью до простых преобразований) задача 1.2.6 б) из "Перечислительной комбинаторики" Гульдена и Джексона, там она решена. Так что если совсем не будет идей, загляните туда.

[Leox]

Спасибо за наводку, посмотрю

[Vince Diesel]

Это частный случай формулы для разности $n$-го порядка

$$ \Delta^n x^n=\sum_{k=0}^n(-1)^{n-k}C_n^k(x+k)^n =n!, $$

разностный аналог производной.

[RIP]

Ну, первую вполне можно и с помощью бинома решить.

[nnosipov]

Тождество Абеля

$$ x\sum_{k=0}^n C_n^k(x+ka)^{k-1}(y+(n-k)a)^{n-k}=(x+y+na)^n. $$

Доказать можно применяя вычеты. Общий метод см. в книге Егорычев Г.П. Интегральное представление и вычисление комбинаторных сумм. Новосибирск: Наука, 1977.

[Хорхе]

Собственно, теорема Лагранжа, которую предлагают применять Гульден с Джексоном, вычетами и доказывается.

А Вы комбинаторно докажите исходное тождество (это возможно).

[Leox]

Кстати, первое тождество, как написано в книге Егорычева стр. 46 , есть следствие тождества Теппера

$$ \sum_{k=0}^n (-1)^k { n \choose k} (\alpha-k)^n=n!. $$

Хотелось бы иметь комбинаторное доказательство, без вычетов.

[Хорхе]

Это неправильное тождество

Но если его поправить, то все равно чисто комбинаторного доказательства, понятно, не будет. Вот если скобки раскрыть, то по крайней мере со свободным членом с комбинаторной точки зрения все хорошо. Я думаю, с остальными коэффициентами где-то так же.

Но это не так интересно. Второе интереснее. Я даже напишу его в том виде, в котором у него есть комбинаторная интерпретация:

$$ n^n = \sum_{k=1}^{n} C_n^k k^{k-1} (n-k)^{n-k}. $$