Двойной счет (метод доказательства)

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

Примеры [ править ]

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

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

Формирование комитетов [ править ]

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

${\ displaystyle {n \ select k}.}$

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

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

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

${\ displaystyle \ sum _ {k = d} ^ {n} {n \ choose k} {k \ choose d} = 2 ^ {nd} {n \ choose d}}$

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

Лемма о рукопожатии [ править ]

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

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

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

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

Подсчет деревьев [ править ]

Формула Кэли означает, что существует 1 = 2 ^2–2 дерева на двух вершинах, 3 = 3 ^3–2 дерева на трех вершинах и 16 = 4 ^4–2 дерева на четырех вершинах.

Добавление направленного края в укорененный лес

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

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

Другой способ подсчета этих последовательностей ребер - рассмотреть возможность добавления ребер одно за другим к пустому графу и подсчитать количество вариантов, доступных на каждом шаге. Если уже добавлен набор из n - k ребер, так что граф, образованный этими ребрами, является корневым лесом с k деревьями, есть n ( k - 1) вариантов для добавления следующего ребра: его начальная вершина может быть любая из n вершин графа, а его конечная вершина может быть любой из 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 .

См. Также [ править ]

Дополнительные примеры [ править ]

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

Связанные темы [ править ]

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

Ссылки [ править ]

• Айгнер, Мартин; Циглер, Гюнтер М. (1998), Доказательства из КНИГИ , Springer-Verlag. Двойной счет описан как общий принцип на стр. 126; Доказательство Питмана двойным счетом формулы Кэли находится на стр. 145–146.
• Эйлер, Л. (1736 г.), "Решение проблем с геометрией, подходящее место" (PDF) , Комментарии Academiae Scientiarum Imperialis Petropolitanae , 8 : 128–140. Перепечатано и переведено в Биггсе, Нидерланды; Ллойд, EK; Уилсон, Р.Дж. (1976), Теория графов 1736–1936 , Oxford University Press.
• Гарбано, ML; Malerba, JF; Lewinter, M. (2003), "гиперкубы и Паскаля треугольник: рассказ о двух доказательствах", Математика Magazine , 76 (3): 216-217, DOI : 10,2307 / 3219324 , JSTOR  3219324.
• Klavžar, Санди (2006), "Counting гиперкубы в гиперкубы", Дискретная математика , 306 (22): 2964-2967, DOI : 10.1016 / j.disc.2005.10.036.
• van Lint, Jacobus H .; Уилсон, Ричард М. (2001), Курс комбинаторики , Cambridge University Press, стр. 4, ISBN 978-0-521-00601-9.