bulgakov

26. Тождество Вандермонда

Если из группы, где nn человек одного вида и mm другого, выбирают rr человек, то это можно сделать (m+nr)\dbinom{m+n}{r} способами. А можно разложить по числу kk выбранных людей первого вида: (nk)(mr−k)\dbinom nk\dbinom m{r-k} способов для каждого kk. Равенство двух подсчётов — тождество Вандермонда: ∑k=0r(nk)(mr−k)=(m+nr)\sum_{k=0}^r\dbinom nk\dbinom m{r-k}=\dbinom{m+n}{r}.

Что пригодится из прошлого: бином Ньютона и следствие (1+x)n=∑(nk)xk(1+x)^n=\sum\dbinom nkx^k — на нём построено доказательство; сочетания; правила суммы и произведения. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.

История: комиссия из мужчин и женщин

В группе 44 мужчины и 33 женщины. Нужно выбрать комиссию из 33 человек. Посчитаем двумя способами.

Способ 1: сразу. Всего 77 человек, выбираем 33: (73)=35\dbinom73=35.

Способ 2: по числу мужчин. Пусть в комиссии kk мужчин, тогда 3−k3-k женщин. Для каждого kk выбор мужчин и затем женщин — два шага подряд (произведение). Разные kk дают непересекающиеся случаи (сумма):

kk (4k)\dbinom{4}{k} (33−k)\dbinom{3}{3-k} Вклад
0 1 1 1
1 4 3 12
2 6 3 18
3 4 1 4
сумма 35

Получилось то же число 3535. Это не совпадение, а общее тождество.

Теорема

Теорема (тождество Вандермонда). Для любых m,n∈Nm,n\in\mathbb N и любого целого r≥0r\ge0 (если b>ab>a, считаем (ab)=0\dbinom ab=0)

∑k=0r(nk)(mr−k)=(m+nr).\boxed{\sum_{k=0}^{r}\binom nk\binom m{r-k}=\binom{m+n}{r}}.

Как читать. Слева — сумма по числу kk «людей первого вида» (от 00 до rr); каждое слагаемое — число способов выбрать kk из nn и r−kr-k из mm. Справа — число способов выбрать rr из всех m+nm+n сразу.

Объяснение через выбор. Любой выбор rr человек из m+nm+n однозначно определяет число kk людей первого вида среди выбранных. Когда kk фиксировано, выбираем kk из nn и r−kr-k из mm (произведение). Суммируем по всем kk (разные kk не пересекаются).

Доказательство через многочлены

Тождество можно доказать и без слов про людей — сравнением коэффициентов.

Рассмотрим тождество

(1+x)n(1+x)m=(1+x)m+n.(1+x)^n(1+x)^m=(1+x)^{m+n}.

Приравняем коэффициенты при xrx^r в правой и левой частях.

Справа. Коэффициент при xrx^r в (1+x)m+n(1+x)^{m+n} равен (m+nr)\dbinom{m+n}{r} (следствие 1 из главы про бином).

Слева. Раскроем оба сомножителя: (1+x)n=∑k(nk)xk(1+x)^n=\sum_k\dbinom nkx^k и (1+x)m=∑j(mj)xj(1+x)^m=\sum_j\dbinom mjx^j. При перемножении степень xrx^r получается, если из первой скобки взять xkx^k, а из второй xr−kx^{r-k}, и так для каждого kk от 00 до rr. Коэффициенты перемножаем и все такие слагаемые складываем:

(n0)(mr)+(n1)(mr−1)+(n2)(mr−2)+⋯+(nr)(m0).\binom n0\binom mr+\binom n1\binom m{r-1}+\binom n2\binom m{r-2}+\cdots+\binom nr\binom m0.

Приравнивая левую и правую части, получаем тождество. □\square

Теорему часто формулируют при r≤min⁡{m,n}r\le\min\{m,n\}: тогда все слагаемые — обычные ненулевые числа. На самом деле это условие не нужно: при больших rr часть слагаемых равна нулю (нельзя выбрать больше людей, чем есть), и равенство остаётся верным.

Следствие: сумма квадратов

Следствие.

∑k=0n(nk)2=(2nn).\boxed{\sum_{k=0}^{n}\binom nk^2=\binom{2n}{n}}.

Доказательство. Возьмём в тождестве m=nm=n и r=nr=n:

∑k=0n(nk)(nn−k)=(2nn).\sum_{k=0}^{n}\binom nk\binom n{n-k}=\binom{2n}{n}.

По симметрии (nn−k)=(nk)\dbinom n{n-k}=\dbinom nk (свойство сочетаний), поэтому слагаемые — квадраты (nk)2\dbinom nk^2. □\square

Пример. n=4n=4: 1^2+4^2+6^2+4^2+1^2=1+16+36+16+1=70, и (84)=70\dbinom84=70.

Примеры

1. В группе 55 мужчин и 44 женщины; комиссия из 33 человек: ∑k=03(5k)(43−k)=(93)=84\sum_{k=0}^{3}\dbinom5k\dbinom4{3-k}=\dbinom93=84.

2. (60)2+(61)2+⋯+(66)2=(126)=924\dbinom{6}{0}^2+\dbinom61^2+\dots+\dbinom66^2=\dbinom{12}{6}=924.

Частые ошибки

  • Суммировать произведения как (n+mr)\dbinom{n+m}{r} без kk. Слева стоит сумма r+1r+1 слагаемых, а не одно.
  • Путать ∑(nk)2\sum\dbinom nk^2 и (∑(nk))2\left(\sum\dbinom nk\right)^2. Первое равно (2nn)\dbinom{2n}n, второе (2n)2=4n(2^n)^2=4^n. Для n=2n=2: 1+4+1=61+4+1=6, а 42=164^2=16.
  • Забыть вторую часть произведения. В слагаемом (nk)(mr−k)\dbinom nk\dbinom m{r-k} нижние числа в сумме дают rr.
  • Сложить вместо перемножить. Выбор мужчин и затем женщин — произведение.

Проверь себя

1. Вычислите ∑k=03(5k)(43−k)\sum_{k=0}^{3}\dbinom5k\dbinom4{3-k}, не считая слагаемых по отдельности.

Решение

По тождеству Вандермонда сумма равна (5+43)=(93)=84\dbinom{5+4}{3}=\dbinom93=84.

2. Найдите (60)2+(61)2+⋯+(66)2\dbinom60^2+\dbinom61^2+\dots+\dbinom66^2.

Решение

По следствию ∑k=0n(nk)2=(2nn)\sum_{k=0}^{n}\dbinom nk^2=\dbinom{2n}n при n=6n=6: (126)=924\dbinom{12}6=924.

3. Из группы 55 мужчин и 44 женщин выбирают комиссию из 44 человек. Сколькими способами в ней окажется ровно две женщины?

Решение

Две женщины из четырёх: (42)=6\dbinom42=6; два мужчины из пяти: (52)=10\dbinom52=10. Всего 6⋅10=606\cdot10=60. Вся комиссия из любых людей: (94)=126\dbinom94=126.

4. Найдите (30)(32)+(31)(31)+(32)(30)\dbinom30\dbinom32+\dbinom31\dbinom31+\dbinom32\dbinom30.

Решение

Это ∑k=02(3k)(32−k)=(62)=15\sum_{k=0}^{2}\dbinom3k\dbinom3{2-k}=\dbinom62=15. Проверка: 1⋅3+3⋅3+3⋅1=151\cdot3+3\cdot3+3\cdot1=15.

Итог

  • Выбор rr из m+nm+n разбивается по числу выбранных «первых»: ∑k=0r(nk)(mr−k)=(m+nr)\sum_{k=0}^r\dbinom nk\dbinom m{r-k}=\dbinom{m+n}{r}.
  • Доказательство: приравниваем коэффициенты при xrx^r в (1+x)n(1+x)m=(1+x)m+n(1+x)^n(1+x)^m=(1+x)^{m+n}.
  • Следствие: ∑k=0n(nk)2=(2nn)\sum_{k=0}^n\dbinom nk^2=\dbinom{2n}{n}.
ПрактикаЗагружаем тест…