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

Как один набор пар даёт два способа подсчёта

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

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

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

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

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

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

Найти объект между двумя сторонами

Пусть несколько учеников участвуют в нескольких проектах. Составим пары «ученик, проект», где участие действительно есть. Суммируя число проектов у каждого ученика, получаем количество таких пар. Суммируя число участников у каждого проекта, получаем тот же результат. Ни один способ не считает отдельного ученика или отдельный проект сам по себе.

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

От пар к тождеству

Выберем подмножество из k элементов среди n различных, затем отметим в нём один элемент. Сначала выбрать весь набор можно C(n,k) способами, а отметить элемент — k способами. Значит отмеченных наборов k·C(n,k). Иной порядок: сначала выбрать отмеченный элемент среди n, затем добавить к нему k−1 элементов из оставшихся n−1.

Получаем k·C(n,k)=n·C(n−1,k−1) при 1≤k≤n. Каждый объект здесь — набор с одной отметкой, а не просто набор. Если забыть отметку в одном из подсчётов, появится лишний множитель и доказательство распадётся. Формула объясняет арифметическое равенство через два порядка построения, не требуя сокращать факториалы.

Пример

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

Сначала набор: C(7,3)·3=35·3=105. Сначала назначенная книга: 7·C(6,2)=7·15=105. В обоих случаях учтены ровно наборы с одной выделенной книгой.

Когда связь считается дважды намеренно

В неориентированном графе каждое обычное ребро имеет два конца. Если суммировать степени вершин, одно ребро попадёт в сумму у обоих концов. Поэтому сумма степеней равна удвоенному числу рёбер. Здесь объектом промежуточного подсчёта служит пара «вершина, инцидентное ребро», а не ребро без выбранного конца.

Перед доказательством полезно произнести полное описание считаемого объекта. Нужны ли порядок, отметка, направление, повторения? Затем для каждого способа проверяют отсутствие пропусков и одинаковую кратность. Если одна сторона учитывает каждый объект один раз, а другая несколько раз, этот множитель нужно явно вынести. Именно такая аккуратность превращает рисунок в доказательство.

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

А теперь — вы

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

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

Можно ли доказать тождество вычислением обеих сторон для нескольких n?

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

Почему часто считают пары?

Пара фиксирует связь двух типов объектов. Её удобно группировать то по первому, то по второму компоненту.

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

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

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