$$ \sum_s (C_{n+s}^{k+l} * C_{k}^{s} * C_{l}^{s}) = C_{n}^{k}*C_{n}^{l}$$

Можно ли это доказать без привлечения высокой техники простыми комбинаторными рассуждениями?

задан 26 Июн '15 13:04

изменен 26 Июн '15 13:49

Когда-то я видел решение этой задачи. В решении рассматривались слова, образованные из трёх букв. Собственно доказательно не помню.

(26 Июн '15 22:02) EdwardTurJ

а каждая буква в слове была из определенного множества, вроде первая из n+s, вторая из k, третья - из l?

(26 Июн '15 22:28) sapere aude
10|600 символов нужно символов осталось
1

Можно. Если Вы готовы читать по-английски, - комбинаторное доказательство есть вот в этой статье (теорема 2.5, второе доказательство).

George E. Andrews. Identities in combinatorics, I: on sorting two ordered sets. Discrete Mathematics, Volume 11, Issue 2, 1975, Pages 97–106

http://www.sciencedirect.com/science/article/pii/0012365X75900011

ссылка

отвечен 26 Июн '15 21:48

О, спасибо. Но там тоже не чисто комбинаторика - есть примесь вероятности. Просто обычно тождества с биномиальными коэффициентами доказывают через какие-нибудь раскраски шаров и в разные цвета или еще попроще, но тут наверное нереально иначе.

(26 Июн '15 22:05) sapere aude

думал над идеей доказательства, которое ограничивалось школьной комбинаторикой, можно было бы сделать так: имеется n шаров и мы хотим k из них покрасить и l проколоть, причем некоторые окажутся проколотыми и покрашенными, пусть их будет s. Шары обладающие 2 из перечисленных свойств "расщепим" на два - покрашенный и проколотый, это и будет левой частью, но что тогда правая?

(22 Сен '15 23:08) sapere aude
1

http://math.stackexchange.com/questions/1460712/li-shanlans-combinatorial-identities

нашел еще одно доказательство, но оно совсем техничное. Видимо это слишком сложная задача, чтобы обойтись без вероятностей и/или вычислений

(3 Окт '15 4:26) sapere aude

@sapere aude: да, оно техническое, но за этими формулами уже можно при желании проследить какие-то комбинаторные отображения. Трудность этой задачи в том, что они весьма неочевидные.

(3 Окт '15 8:14) falcao

Еще нужно поглядеть в "Конкретную математику" Кнута-Грэхема. Там есть две больших главы, посвященных тождествам с суммированием биномиальных коэффициентов. Правда, комбинаторных рассуждений там не бывает, но если вы все равно готовы смотреть и некомбинаторные решения...

(3 Окт '15 10:17) knop

@knop Напротив, ищу как раз ЧИСТО комбинаторное тождество, без алгебраических трюков или вероятностного подхода. Ссылку скинул на тот случай, если, как предположил @falcao, за техникой скрываются какие-то нетривиальные биекции.

@falcao Возможно нужно на каком-то более научном языке смоделировать, а то с цветными проколотыми шариками я погорячился. Есть два равномощных алфавита в которых s общих символов. Справа мы выбираем k слов из первого и l из второго, а слева...

(3 Окт '15 15:19) sapere aude
показано 5 из 6 показать еще 1
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

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

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,161
×1,067
×1,062
×14

задан
26 Июн '15 13:04

показан
1097 раз

обновлен
3 Окт '15 15:19

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru