26. Тождество Вандермонда
Если из группы, где человек одного вида и другого, выбирают человек, то это можно сделать способами. А можно разложить по числу выбранных людей первого вида: способов для каждого . Равенство двух подсчётов — тождество Вандермонда: .
Что пригодится из прошлого: бином Ньютона и следствие — на нём построено доказательство; сочетания; правила суммы и произведения. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.
История: комиссия из мужчин и женщин
В группе мужчины и женщины. Нужно выбрать комиссию из человек. Посчитаем двумя способами.
Способ 1: сразу. Всего человек, выбираем : .
Способ 2: по числу мужчин. Пусть в комиссии мужчин, тогда женщин. Для каждого выбор мужчин и затем женщин — два шага подряд (произведение). Разные дают непересекающиеся случаи (сумма):
| Вклад | |||
|---|---|---|---|
| 0 | 1 | 1 | 1 |
| 1 | 4 | 3 | 12 |
| 2 | 6 | 3 | 18 |
| 3 | 4 | 1 | 4 |
| сумма | 35 |
Получилось то же число . Это не совпадение, а общее тождество.
Теорема
Теорема (тождество Вандермонда). Для любых и любого целого (если , считаем )
Как читать. Слева — сумма по числу «людей первого вида» (от до ); каждое слагаемое — число способов выбрать из и из . Справа — число способов выбрать из всех сразу.
Объяснение через выбор. Любой выбор человек из однозначно определяет число людей первого вида среди выбранных. Когда фиксировано, выбираем из и из (произведение). Суммируем по всем (разные не пересекаются).
Доказательство через многочлены
Тождество можно доказать и без слов про людей — сравнением коэффициентов.
Рассмотрим тождество
Приравняем коэффициенты при в правой и левой частях.
Справа. Коэффициент при в равен (следствие 1 из главы про бином).
Слева. Раскроем оба сомножителя: и . При перемножении степень получается, если из первой скобки взять , а из второй , и так для каждого от до . Коэффициенты перемножаем и все такие слагаемые складываем:
Приравнивая левую и правую части, получаем тождество.
Теорему часто формулируют при : тогда все слагаемые — обычные ненулевые числа. На самом деле это условие не нужно: при больших часть слагаемых равна нулю (нельзя выбрать больше людей, чем есть), и равенство остаётся верным.
Следствие: сумма квадратов
Следствие.
Доказательство. Возьмём в тождестве и :
По симметрии (свойство сочетаний), поэтому слагаемые — квадраты .
Пример. : 1^2+4^2+6^2+4^2+1^2=1+16+36+16+1=70, и .
Примеры
1. В группе мужчин и женщины; комиссия из человек: .
2. .
Частые ошибки
- Суммировать произведения как без . Слева стоит сумма слагаемых, а не одно.
- Путать и . Первое равно , второе . Для : , а .
- Забыть вторую часть произведения. В слагаемом нижние числа в сумме дают .
- Сложить вместо перемножить. Выбор мужчин и затем женщин — произведение.
Проверь себя
1. Вычислите , не считая слагаемых по отдельности.
Решение
По тождеству Вандермонда сумма равна .
2. Найдите .
Решение
По следствию при : .
3. Из группы мужчин и женщин выбирают комиссию из человек. Сколькими способами в ней окажется ровно две женщины?
Решение
Две женщины из четырёх: ; два мужчины из пяти: . Всего . Вся комиссия из любых людей: .
4. Найдите .
Решение
Это . Проверка: .
Итог
- Выбор из разбивается по числу выбранных «первых»: .
- Доказательство: приравниваем коэффициенты при в .
- Следствие: .
