Комбинаторное доказательство

В математике термин комбинаторное доказательство часто используется для обозначения одного из двух типов математического доказательства :

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

Термин «комбинаторное доказательство» может также использоваться в более широком смысле для обозначения любого вида элементарного доказательства в комбинаторике. Однако, как пишет Гласс (2003) в своем обзоре Benjamin & Quinn (2003) (книга о комбинаторных доказательствах), этих двух простых методов достаточно для доказательства многих теорем комбинаторики и теории чисел .

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

Архетипическое двойной счет доказательство для хорошо известной формулы для числа из K - комбинации (т.е. подмножества размера к ) из с п - элементного множества: ${\ displaystyle {\ tbinom {n} {k}}}$

{\ displaystyle {\ binom {n} {k}} = {\ frac {n (n-1) \ cdots (n-k + 1)} {k (k-1) \ cdots 1}}.}

Здесь прямое биективное доказательство невозможно: поскольку правая часть тождества является дробью, не существует множества, явно подсчитываемого ею (даже нужно подумать, чтобы увидеть, что знаменатель всегда делит числитель поровну). Однако его числитель подсчитывает декартово произведение из K конечных множеств размеров п , п - 1 , ..., п - к + 1 , в то время как ее знаменатель подсчитывает перестановки из в K - элементного множества (множество наиболее явно рассчитывали на знаменатель будет еще одно декартово произведение kконечные множества; при желании можно было бы сопоставить перестановки с этим набором явной биекцией). Теперь возьмем S как набор последовательностей из k элементов, выбранных из нашего набора n -элементов без повторения. С одной стороны, существует простая биекция S с декартовым произведением, соответствующим числителю , а с другой стороны, существует биекция из множества C пар k -комбинации и перестановки σ элемента k в S , по формуле взяв элементы C в порядке возрастания, а затем переставив эту последовательность на σ, чтобы получить элемент S ${\ Displaystyle п (п-1) \ cdots (п-к + 1)}$ . Два способа подсчета дают уравнение

{\ Displaystyle п (п-1) \ cdots (п-к + 1) = {\ binom {п} {к}} к !,}

и после деления на k ! это приводит к заявленной формуле для . В общем, если формула подсчета включает деление, аналогичный аргумент двойного подсчета (если он существует) дает наиболее прямое комбинаторное доказательство идентичности, но аргументы двойного подсчета не ограничиваются ситуациями, когда формула имеет такую форму. ${\ displaystyle {\ tbinom {n} {k}}}$

Вот более простое и неформальное комбинаторное доказательство того же тождества:

{\ Displaystyle {\ binom {п} {к}} к! (пк)! = п!}

Предположим, что n человек хотят войти в музей, но в нем есть место только для k человек. Сначала выберите, какие k человек из n человек будут допущены. Есть способы сделать это по определению. Теперь закажите k человек в одну линию, чтобы они могли платить по одному. Есть k ! способы переставить этот набор размера k . Затем прикажите n - k человек, которые должны оставаться снаружи, в одну строку, чтобы позже они могли входить по одному, когда остальные уходят. Есть ( n - k ${\ displaystyle {\ tbinom {n} {k}}}$ )! способы сделать это. Но теперь мы заказали всю группу из n человек, что можно сделать за n ! способами. Итак, обе стороны подсчитывают количество способов упорядочить n человек. Деление дает известную формулу для . ${\ displaystyle {\ tbinom {n} {k}}}$

Преимущество комбинаторного доказательства [ править ]

Стэнли (1997) приводит пример комбинаторной задачи перечисления (подсчета количества последовательностей k подмножеств S ₁ , S ₂ , ... S _k , которые могут быть сформированы из набора из n элементов, так что подмножества имеют пустую общее пересечение) с двумя разными доказательствами ее решения. Первое доказательство, которое не является комбинаторным, использует математическую индукцию и производящие функции, чтобы найти, что количество последовательностей этого типа равно (2 ^k −1) ⁿ . Второе доказательство основано на наблюдении, что существует 2 ^k −1Собственные подмножества множества {1, 2, ..., k } и (2 ^k −1) ⁿ функций из множества {1, 2, ..., n } в семейство собственных подмножеств {1, 2, ..., k }. Подлежащие подсчету последовательности могут быть помещены во взаимно однозначное соответствие с этими функциями, где функция, сформированная из данной последовательности подмножеств, отображает каждый элемент i в набор { j | i ∈ S _j }.

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

Разница между биективными доказательствами и доказательствами двойного счета [ править ]

Стэнли не делает четкого различия между доказательством биективности и двойным счетом и приводит примеры обоих типов, но различие между двумя типами комбинаторного доказательства можно увидеть в примере, приведенном Эйгнером и Зиглером (1998) , доказательства формулы Кэли, утверждающей что существует n ^{n - 2} разных деревьев, которые могут быть сформированы из данного набора n узлов. Айгнер и Зиглер приводят четыре доказательства этой теоремы, первое из которых является биективным, а последнее - аргументом двойного счета. Они также упоминают, но не описывают детали пятого биективного доказательства.

Самый естественный способ найти биективное доказательство этой формулы - найти взаимно однозначное соответствие между деревьями n- узлов и некоторым набором объектов, который имеет n ^{n - 2} члена, например, последовательностями из n - 2 значений, каждое в диапазоне от 1 к п . Такая биекция может быть получена с использованием последовательности Прюфера каждого дерева. Любое дерево можно однозначно закодировать в последовательность Прюфера, и любую последовательность Прюфера можно однозначно декодировать в дерево; вместе эти два результата обеспечивают биективное доказательство формулы Кэли.

Альтернативное биективное доказательство, данное Айгнером и Циглером и приписанное ими Андре Жоялу , включает взаимно однозначное соответствие между, с одной стороны, n- узловыми деревьями с двумя обозначенными узлами (которые могут быть одинаковыми) и между С другой стороны, п -node направлено pseudoforests . Если существует T _n n -узловых деревьев, то существует n ²T _n деревьев с двумя назначенными узлами. И псевдолесье можно определить, задав для каждого из его узлов конечную точку края, идущего наружу от этого узла; есть nвозможные варианты конечной точки единственного ребра (позволяющие петли) и, следовательно, n ⁿ возможных псевдолесов. Обнаружив взаимно однозначное соответствие между деревьями с двумя помеченными узлами и псевдолесьями, доказательство Джояла показывает, что T _n = n ^{n - 2} .

Наконец, четвертое доказательство формулы Кэли, представленное Эйгнером и Зиглером, является доказательством двойного счета, принадлежащим Джиму Питману . В этом доказательстве Питман рассматривает последовательности направленных ребер, которые могут быть добавлены к пустому графу с n узлами, чтобы сформировать из него одно корневое дерево, и подсчитывает количество таких последовательностей двумя разными способами. Показывая, как получить последовательность этого типа, выбирая дерево, корень дерева и упорядочивая ребра в дереве, он показывает, что существует T _n n ! возможные последовательности этого типа. И, подсчитав количество способов, которыми частичная последовательность может быть расширена одним ребром, он показывает, что существует n ⁿ^{- 2}n! возможные последовательности. Приравнивая эти две разные формулы к размеру одного и того же набора последовательностей ребер и исключая общий множитель n ! приводит к формуле Кэли.

Понятия, связанные с данным [ править ]

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

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

Айгнер, Мартин; Зиглер, Гюнтер М. (1998), Доказательства из КНИГИ , Springer-Verlag , стр. 141–146, ISBN 3-540-40460-0.

Бенджамин, Артур Т .; Куинн, Дженнифер Дж. (2003), Доказательства, которые действительно важны : Искусство комбинаторного доказательства , Dolciani Mathematical Expositions, 27 , Математическая ассоциация Америки , ISBN 978-0-88385-333-7.

Гласс, Даррен (2003), Прочтите это: Действительно важные доказательства , Математическая ассоциация Америки.

Стэнли, Ричард П. (1997), Перечислительная комбинаторика, Том I , Кембриджские исследования в области высшей математики, 49 , Cambridge University Press, стр. 11–12, ISBN 0-521-55309-1.