Математика · объяснение и практика

Как выбор из двух групп объясняет тождество Вандермонда

Как выбор фиксированного числа объектов из двух непересекающихся групп объясняет свёртку сочетаний и почему в сумме нужно учитывать все допустимые составы.

Синяя и оранжевая половины складываются в целый круг.

В теме Доказательства и комбинаторные модели · Учебная карта

В маршруте Счёт через устройство объектов · 10 тем

Главная мысль

Выбор r объектов из групп размеров m и n можно разделить по числу k объектов первой группы. Сумма C(m,k)·C(n,r−k) по допустимым k равна C(m+n,r).

Один выбор с разным составом

Пусть есть четыре разные красные карточки и три разные синие. Нужно выбрать три карточки без учёта порядка. Можно сразу выбирать из семи, получая C(7,3). Можно сначала решить, сколько красных входит в набор, а затем независимо выбрать конкретные карточки нужного цвета. Цвет не делает карточки неразличимыми: каждая имеет свою метку.

Возможны составы с нулём, одной, двумя или тремя красными. Для фиксированного числа красных количество равно произведению сочетаний из двух групп. Наборы разных составов не пересекаются, потому что готовый набор имеет единственное количество красных. Поэтому результаты по составам разрешено сложить без дополнительного деления или вычитания общих случаев.

Границы суммы важнее красивой записи

Для размеров m,n и общего выбора r нужно одновременно 0≤k≤m и 0≤r−k≤n. Значит k идёт от max(0,r−n) до min(m,r). Иногда сумму пишут по более широкому диапазону, условно считая невозможные сочетания нулевыми. Если такого соглашения не было, факториалы отрицательных чисел подставлять нельзя.

Для четырёх красных и трёх синих карточек число троек равно 1+12+18+4=35. Слагаемые соответствуют составам: три синие; одна красная и две синие; две красные и одна синяя; три красные. Прямой выбор C(7,3)=35 подтверждает, что список составов исчерпывающий.

Пример

Из пяти задач первого раздела и четырёх второго выбирают четыре разные задачи. Сколько наборов получается через разбиение по числу задач первого раздела?

Сумма равна C(5,0)C(4,4)+C(5,1)C(4,3)+C(5,2)C(4,2)+C(5,3)C(4,1)+C(5,4)C(4,0)=1+20+60+40+5=126=C(9,4).

Когда тождество перестаёт быть ответом задачи

Если условие требует хотя бы одну карточку каждого цвета, полная сумма включает лишние одноцветные наборы. Тогда ограничивают составы либо вычитают запрещённые края. Само тождество остаётся верным, но считает более широкий набор. Аналогично различимые роли выбранных объектов потребуют отдельного множителя или другого способа подсчёта.

Красивый частный случай получается при равных группах и выборе половины общего количества: сумма квадратов C(n,k) равна C(2n,n). Квадрат возникает потому, что C(n,n−k)=C(n,k). Он не означает, что нужно дважды выбрать один и тот же набор: выборы делаются в разных непересекающихся группах с одинаковыми размерами.

От чтения к действию

А теперь — вы

Выбирают пять объектов из двух непересекающихся групп размеров 2 и 4. Какие значения числа выбранных объектов первой группы возможны?

Частые вопросы

Обязательно ли цвета обозначают вероятность?

Нет. Это чистый подсчёт конечных наборов. Вероятностная модель и равновозможность понадобятся только при переходе к вероятностям.

Почему группы должны быть непересекающимися?

Объект должен однозначно относиться к одной группе, иначе разбиение по составу может повторно считать один и тот же выбор.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться