Доказать комбинаторно $$\sum_k C_p^k C_{q+k}^n = C^{p+n}_{p+q}; $$

задан 11 Апр '14 6:56

10|600 символов нужно символов осталось
2

В том виде, в котором тождество сейчас написано, оно является неверным. Я рассмотрю доказательство исправленного варианта указанной формулы (см. ниже).

Исходим из определения сочетаний, интерпретируя $%C_n^m$% как число способов взять $%m$% предметов из $%n$% (попарно) различных.

Пусть у нас имеется $%p+q$% предметов, и мы хотим подсчитать число способов взять из них $%p+n$%, где $%0\le n\le q$%. Будем считать, что наши предметы бывают двух видов: красные в количестве $%p$% штук и синие в количестве $%q$% штук; все предметы отличаются друг от друга.

Из этого количества нам надо взять $%p+n$% предметов. Мы при этом берём какое-то количество красных предметов, которое нам удобно обозначить через $%p-k$%, так как оно не превосходит $%p$%. При этом $%0\le k\le p$%. Сделать это можно $%C_p^{p-k}=C_p^k$% различными способами.

Далее мы добираем оставшиеся предметы из числа синих в количестве $%(p+n)-(p-k)=n+k$%. При этом число $%n+k$% не должно превосходить $%q$%, то есть $%k\le q-n$%. Это можно сделать $%C_q^{n+k}$% способами. Тогда по правилу произведения получается, что при фиксированном $%k\le\max(p,q-n)$% выбор красных и синих предметов с указанными свойствами можно осуществить $%C_p^kC_q^{n+k}$% способами. Для разных значений $%k$% способы получаются разными, и тогда по правилу суммы надо сложить все полученные числа этого вида. При этом возникает равенство $$C_{p+q}^{p+n}=\sum\limits_kC_p^kC_q^{n+k},$$ где суммирование происходит по $%k$% в означенных пределах.

ссылка

отвечен 11 Апр '14 13:24

изменен 11 Апр '14 13:53

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,402

задан
11 Апр '14 6:56

показан
418 раз

обновлен
11 Апр '14 13:53

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

по почте:

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

по RSS:

Ответы

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

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