2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2  След.
 
 Найти сумму
Сообщение08.05.2012, 20:45 
Доказать, что
$$
\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}.
$$

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

 
 
 
 Re: Найти сумму
Сообщение08.05.2012, 21:00 
Аватара пользователя
Leox в сообщении #568868 писал(а):
Хотя бы идею подскажите.

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

 
 
 
 Re: Найти сумму
Сообщение08.05.2012, 21:42 
Integrall в сообщении #568879 писал(а):
Leox в сообщении #568868 писал(а):
Хотя бы идею подскажите.

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


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

 
 
 
 Re: Найти сумму
Сообщение08.05.2012, 21:53 
Аватара пользователя
Leox в сообщении #568907 писал(а):
знаю.. и что, нужно разложить слева и справа?

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

 
 
 
 Re: Найти сумму
Сообщение08.05.2012, 21:56 
Integrall в сообщении #568910 писал(а):
Leox в сообщении #568907 писал(а):
знаю.. и что, нужно разложить слева и справа?

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


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

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

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

Идею подсказал :-)

 
 
 
 Re: Найти сумму
Сообщение08.05.2012, 22:25 
Хорхе в сообщении #568920 писал(а):
Не уверен, что бином тут поможет, Ньютона ли или еще кого. В первом есть простая комбинаторная интерпретация с отображениями множества $\{1,2,\dots,n\}$ в себя и формулой включения-исключения.

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

Идею подсказал :-)



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

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

 
 
 
 Re: Найти сумму
Сообщение08.05.2012, 23:19 
Спасибо за наводку, посмотрю

 
 
 
 Re: Найти сумму
Сообщение08.05.2012, 23:59 
Это частный случай формулы для разности $n$-го порядка
$$
\Delta^n x^n=\sum_{k=0}^n(-1)^{n-k}C_n^k(x+k)^n =n!,
$$
разностный аналог производной.

 
 
 
 Re: Найти сумму
Сообщение09.05.2012, 00:44 
Аватара пользователя
Ну, первую вполне можно и с помощью бинома решить.

 
 
 
 Re: Найти сумму
Сообщение09.05.2012, 10:07 
Тождество Абеля
$$
x\sum_{k=0}^n C_n^k(x+ka)^{k-1}(y+(n-k)a)^{n-k}=(x+y+na)^n.
$$
Доказать можно применяя вычеты. Общий метод см. в книге Егорычев Г.П. Интегральное представление и вычисление комбинаторных сумм. Новосибирск: Наука, 1977.

 
 
 
 Re: Найти сумму
Сообщение09.05.2012, 11:01 
Аватара пользователя
Собственно, теорема Лагранжа, которую предлагают применять Гульден с Джексоном, вычетами и доказывается.

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

 
 
 
 Re: Найти сумму
Сообщение09.05.2012, 11:13 
Кстати, первое тождество, как написано в книге Егорычева стр. 46 , есть следствие тождества Теппера
$$
\sum_{k=0}^n (-1)^k { n \choose k} (\alpha-k)^n=n!.
$$
Хотелось бы иметь комбинаторное доказательство, без вычетов.

 
 
 
 Re: Найти сумму
Сообщение09.05.2012, 11:34 
Аватара пользователя
Это неправильное тождество :-)

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

Но это не так интересно. Второе интереснее. Я даже напишу его в том виде, в котором у него есть комбинаторная интерпретация:
$$
n^n = \sum_{k=1}^{n} C_n^k k^{k-1} (n-k)^{n-k}.
$$

 
 
 [ Сообщений: 20 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group