0
1

Дать комбинаторное доказательство тождеств. Т.е. на примере какой-то задачи показать, что её можно решить по формуле из левой части и по формуле из правой части, тем самым доказав их эквивалентность. Формулы для сочетаний использовать нельзя.

задан 11 Ноя '19 21:32

изменен 11 Ноя '19 21:35

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

Ну, например, равенство б) можно переписать как $$ C_n^m = C_2^0\cdot C_{n-2}^m + C_2^1\cdot C_{n-2}^{m-1} + C_2^2\cdot C_{n-2}^{m-2} $$ что является частным случаем свёртки Вандермонда...

Традиционная интерпретация такая:
Имеется $%n$% шарика, среди которых 2 белых, а остальные чёрные...
Вынимаем $%m$% шариков... слева общее число вариантов... а справа разбор случаев - все чёрные, один белый остальные чёрные, два белых остальные чёрные...

ссылка

отвечен 11 Ноя '19 22:06

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

а) Из n предметов выбираем m, а потом из выбранных m предметов берём k. Это даёт формулу из левой части. То же самое посчитаем по-другому. Сначала из n предметов выберем k. Затем из оставшихся n-k предметов выберем m-k, чтобы вместе с уже имеющимися k предметами получилось m. Этот способ даёт выражение в правой части.

б) Про это уже написали: основная идея -- выделить два элемента.

в) Здесь нужно взять за основу какую-либо задачу, ответом для которой является (n+2)-е число Фибоначчи. Рассмотрим двоичные последовательности из n символов без двух единиц подряд. Сегодня уже говорилось, что их F(n+2), где F(1)=F(2)=1. Подсчитаем их число другим способом. Возьмём такую последовательность (слово из 0 и 1), и припишем 0 слева. То, что получилось, можно однозначно представить в виде произведения "слогов" вида 0 и 01, так как перед единицей всегда стоит 0. Пусть k -- число слогов вида 01. Ясно, что 0<=k<=(n+1)/2. Для заданного k у нас имеется n-k+1 слогов, так как длина слова равна n+1, и k букв уходит на слоги двойной длины. Итого у нас есть n-k+1 место для слогов, и из них мы выбираем k мест для расположения слогов 01. На остальные места ставим нули. Получается суммы сочетаний из n-k+1 по k в указанных пределах.

ссылка

отвечен 12 Ноя '19 0:50

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

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

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

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

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

отмечен:

×1,463

задан
11 Ноя '19 21:32

показан
1108 раз

обновлен
12 Ноя '19 0:50

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

по почте:

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

по RSS:

Ответы

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

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