Двойной счёт: комбинаторный метод доказательства равенств

Введение

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

Умножение (натуральных чисел)

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

Создание комитетов

Один из примеров метода двойного подсчета — это подсчет количества способов, которыми можно сформировать комитет из *n* человек, позволяя любому количеству людей (даже нулю из них) входить в состав комитета. То есть, подсчитывается количество подмножеств, которые может иметь множество из *n* элементов. Один из способов формирования комитета — попросить каждого человека решить, входить в него или нет. У каждого человека есть два варианта — да или нет — и эти решения независимы от решений других людей. Поэтому существует 2^*n* возможностей. Альтернативно, можно заметить, что размер комитета должен быть каким-то числом от 0 до *n*. Для каждого возможного размера *k*, количество способов, которыми можно сформировать комитет из *k* человек из *n* человек, равно биномиальному коэффициенту ^*n*C_*k*.

Следовательно, общее количество возможных комитетов — это сумма биномиальных коэффициентов по *k* от 0 до *n*. Приравнивание двух выражений дает тождество ^*n*C₀ + ^*n*C₁ + ... + ^*n*C_*n* = 2^*n*, являющееся частным случаем биномиальной теоремы. Аналогичный метод двойного подсчета можно использовать для доказательства более общего тождества.

Лемма рукопожатия

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

где – количество рёбер. Таким образом, сумма степеней вершин является чётным числом, что было бы невозможно, если бы нечётное число вершин имело нечётную степень. Этот факт, вместе с этим доказательством, впервые появляется в статье Леонарда Эйлера 1736 года о семи мостах Кёнигсберга, которая положила начало изучению теории графов.

Дополнительные примеры

Тождество Вандермонда, другое тождество для сумм биномиальных коэффициентов, которое можно доказать методом двойного подсчёта. Число в форме квадратной пирамиды. Равенство между суммой первых квадратных чисел и кубическим многочленом можно показать, используя двойной подсчёт троек чисел , , и , где больше любого из двух других чисел. Неравенство Любелла — Ямамото — Мешалкина. Доказательство Любелла этого результата для семейств множеств основано на аргументе двойного подсчёта на перестановках, используемом для доказательства неравенства, а не равенства. Теорема Эрдеша — Ко — Радо, устанавливающая верхнюю границу для пересекающихся семейств множеств, доказана Дьюлой О. Х. Катона с использованием неравенства двойного подсчёта. Доказательства малой теоремы Ферма. Доказательство делимости методом двойного подсчёта: для любого простого числа и натурального числа существует слов длины над алфавитом из символов, содержащих два или более различных символа. Эти слова можно сгруппировать в наборы, которые можно преобразовать друг в друга циклическими сдвигами; эти наборы называются ожерельями. Следовательно, (количество ожерелий) делится на . Доказательства закона квадратичной взаимности. Доказательство Эйзенштейна выводит ещё один важный результат из теории чисел, используя двойной подсчёт точек решётки в треугольнике.

Связанные темы

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