2014 dxdy logo

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

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




 
 Комбинаторное тождество
Сообщение21.02.2015, 01:24 
Аватара пользователя
$$\textstyle C_{m+n}^k=\sum_{s=0}^{k}\textstyle C_{m}^s\textstyle C_{n}^{k-s}$$
Как понять математический смысл данного тождества? В чём его прелесть? Для решения каких задач нужно это тождество?

 
 
 
 Re: Комбинаторное тождество
Сообщение21.02.2015, 02:26 
Аватара пользователя
Я думаю, Вам достаточно будет ссылки на Вики, там можно сориентироваться про древнюю историю открытия свёртки, о применениях (по доказательствам) и о прелестях далеко идущих обобщений.

По поводу различных применений и решения задач можете полистать первые страницы книги Дж. Риордана "Комбинаторные тождества". Там его называют наиболее используемым комбинаторным тожеством и с помощью относительно простой техники тут же получают из него множество красивых следствий с примерами к задачам.

 
 
 
 Re: Комбинаторное тождество
Сообщение21.02.2015, 02:30 
Ktina, а что Вы имеете в виду под "математическим" смыслом? Комбинаторный достаточно очевиден. Он годится?

 
 
 
 Re: Комбинаторное тождество
Сообщение21.02.2015, 02:38 
Аватара пользователя
Otta,
Я имею в виду, какую задачу можно решить при помощи этого тождества? Какой-нибудь пример из жизни.

 
 
 
 Re: Комбинаторное тождество
Сообщение21.02.2015, 03:13 
Ну не придумывается нетривиальных примеров. Смысл-то простой.
Сколькими способами можно выбрать $k$ шариков из кучи, где намешаны $m$ белых и $n$ черных. Можно выбирать сразу. Это левая часть. А можно постепенно. Из белых 0, из черных соотв. $k$... ну и т.д. Это правая.
Вот и все, собссно.

 
 
 
 Re: Комбинаторное тождество
Сообщение21.02.2015, 05:37 
Аватара пользователя
Или два способа подсчёта кратчайших ломаных со звеньями, параллельными координатным осям - один сразу из точки $(0;0)$ в точку $(m+n;k)$, а другой транзитом через точки прямой $x=m.$

 
 
 
 Re: Комбинаторное тождество
Сообщение21.02.2015, 13:11 
Аватара пользователя
Виноват, не то ляпнул.
Правильная интертрепация - число путей из $(0;0)$ в $(m+n-k; k)$ транзитом через прямую $x+y=m.$

 
 
 
 Re: Комбинаторное тождество
Сообщение21.02.2015, 13:49 
Ktina в сообщении #980675 писал(а):
Для решения каких задач нужно это тождество?

При умножении рядов Тэйлора функций нескольких переменных иногда упрощаются выкладки.

 
 
 
 Re: Комбинаторное тождество
Сообщение21.02.2015, 14:39 
Аватара пользователя
Разделив на $2^{m+n}$, получим, фактически, уравнение Колмогорова-Чепмена для простого случайного блуждания (bot примерно о том же уже сказал)

 
 
 [ Сообщений: 9 ] 


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