Двойной счет (метод доказательства) - Double counting (proof technique)

В комбинаторика, двойной счет, также называемый подсчет двумя способами, это комбинаторное доказательство способ показать, что два выражения равны, продемонстрировав, что это два способа подсчета размера одного набор. В этой технике, которая ван Линт и Уилсон (2001) называют «одним из важнейших инструментов комбинаторики», один описывает конечный набор Икс с двух точек зрения, что приводит к двум различным выражениям размера набора. Поскольку оба выражения равны размеру одного и того же набора, они равны друг другу.

Примеры

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

Это простой пример двойного счета, который часто используется при обучении детей младшего возраста умножению. В этом контексте умножение натуральные числа вводится как повторное сложение, а затем показано как коммутативный путем подсчета двумя разными способами количества элементов, расположенных в прямоугольной сетке. Предположим, что сетка имеет ${ displaystyle n}$ ряды и ${ displaystyle m}$ столбцы. Сначала подсчитываем предметы, суммируя ${ displaystyle n}$ ряды ${ displaystyle m}$ каждый, затем второй раз, суммируя ${ displaystyle m}$ столбцы ${ displaystyle n}$ пунктов каждый, таким образом показывая, что для этих конкретных значений ${ displaystyle n}$ и ${ displaystyle m}$ , ${ Displaystyle п раз м = м раз п}$ . Хотя это не доказательство, оно ясно показывает, что умножение коммутирует для любого примера (практического размера), который мы выберем.

Формирование комитетов

Один из примеров метода двойного подсчета подсчитывает количество способов, которыми комитет может быть сформирован из п людей, позволяя любому количеству людей (даже нулю) быть частью комитета. То есть считается количество подмножества что п-элемент в комплекте может быть. Один из методов формирования комитета - попросить каждого человека выбрать, присоединяться к нему или нет. У каждого человека есть два варианта выбора - да или нет - и этот выбор не зависит от выбора других людей. Следовательно, имеется 2 × 2 × ... × 2 = 2^п возможности. В качестве альтернативы можно заметить, что размер комитета должен быть некоторым числом от 0 до п. Для каждого возможного размера k, количество способов, которыми комитет k люди могут быть сформированы из п люди это биномиальный коэффициент

{ displaystyle {n select k}.}

Следовательно, общее количество возможных комитетов - это сумма биномиальных коэффициентов по k = 0, 1, 2, ... п. Приравнивание двух выражений дает личность

{ displaystyle sum _ {k = 0} ^ {n} {n select k} = 2 ^ {n},}

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

{ displaystyle sum _ {k = d} ^ {n} {n choose k} {k choose d} = 2 ^ {n-d} {n choose d}}

(Гарбано, Малерба и Левинтер, 2003 г.; Клавжар 2006 ).

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

Другая теорема, которая обычно доказывается аргументом двойного счета, утверждает, что каждое неориентированный граф содержит четное количество вершины странного степень. То есть количество вершин с нечетным числом инцидентов края должно быть даже. Говоря более разговорным языком, в группе людей, некоторые из которых пожимают руки, четное количество людей должно было пожать нечетное количество рук другим людям; по этой причине результат известен как лемма о рукопожатии.

Чтобы доказать это двойным счетом, пусть d(v) - степень вершины v. Число инцидентностей вершин и ребер в графе можно подсчитать двумя различными способами: суммированием степеней вершин или подсчетом двух инцидентов для каждого ребра. Следовательно

{ Displaystyle сумма _ {v} d (v) = 2e}

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

Подсчет деревьев

Формула Кэли подразумевает, что есть 1 = 2^{2 − 2} дерево на двух вершинах, 3 = 3^{3 − 2} деревья на трех вершинах, и 16 = 4^{4 − 2} деревья на четырех вершинах.

Добавление направленной кромки в корневой лес

Какой номер Т_п разных деревья который может быть сформирован из набора п различные вершины? Формула Кэли дает ответ Т_п = п^{п − 2}. Айгнер и Зиглер (1998) перечислите четыре доказательства этого факта; они пишут о четвертом, доказательстве двойного счета, благодаря Джиму Питману, что он «самый красивый из всех».

Доказательство Питмана подсчитывает двумя разными способами количество различных последовательностей направленных ребер, которые могут быть добавлены к пустой график на п вершины, чтобы сформировать из него укоренившееся дерево. Один из способов сформировать такую последовательность - начать с одного из Т_п возможных некорневых деревьев, выберите одно из п вершины как корень, и выберите одну из (п − 1)! возможные последовательности для добавления п − 1 (направленные) края. Следовательно, общее количество последовательностей, которые могут быть сформированы таким образом, равно Т_п п(п − 1)! = Т_п п!.

Другой способ подсчета этих последовательностей ребер - рассмотреть возможность добавления ребер одно за другим к пустому графу и подсчета количества вариантов, доступных на каждом шаге. Если кто-то добавил коллекцию п − k ребер уже, так что граф, образованный этими ребрами, является корневым лес с k деревья, есть п(k − 1) варианты добавления следующего ребра: его начальная вершина может быть любой из п вершины графа, а его конечная вершина может быть любой из k − 1 корни, кроме корня дерева, содержащего начальную вершину. Следовательно, если умножить количество вариантов первого шага, второго шага и т. Д., Общее количество вариантов будет равно

{ Displaystyle prod _ {k = 2} ^ {n} n (k-1) = n ^ {n-1} (n-1)! = n ^ {n-2} n !.}

Приравнивание этих двух формул для количества последовательностей ребер приводит к формуле Кэли:

{ displaystyle displaystyle T_ {n} n! = n ^ {n-2} n!}

и

{ displaystyle displaystyle T_ {n} = n ^ {n-2}.}

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

Смотрите также

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

Личность Вандермонда, еще одно тождество сумм биномиальных коэффициентов, которое можно доказать двойным счетом.
Квадратное пирамидальное число. Равенство между суммой первых п квадратные числа а кубический многочлен можно показать двойным подсчетом троек чисел Икс, у, и z куда z больше, чем любое из двух других чисел.
Неравенство Любелла – Ямамото – Мешалкина.. Доказательство Любелла этого результата для семейств множеств является аргументом двойного счета на перестановки, используется, чтобы доказать неравенство а не равенство.
Доказательства малой теоремы Ферма. А делимость доказательство двойным счетом: по любому основной п и натуральное число А, Существуют А^п − А длина-п слова над А-символьный алфавит, состоящий из двух или более различных символов. Их можно сгруппировать в наборы п слова, которые можно преобразовать друг в друга круговые смены; эти наборы называются украшения на шею. Следовательно, А^п − А = п × (число ожерелий) и делится нап.
Доказательства квадратичной взаимности. Доказательство Эйзенштейн получает еще один важный теоретико-числовой факт двойным подсчетом точек решетки в треугольнике.