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

Combinatorial proof

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

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

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

Пример

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

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

и после деления на k! это приводит к указанной формуле для . В общем, если формула счета включает деление, аналогичный аргумент двойного счета (если он существует) дает наиболее прямое комбинаторное доказательство тождества, но аргументы двойного счета не ограничиваются ситуациями, когда формула имеет такую ​​форму.

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

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

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

Стэнли (1997) приводит пример комбинаторное перечисление задача (подсчет количества последовательностей k подмножества S1, S2, ... Sk, который может быть сформирован из набора п такие, что подмножества имеют пустое общее пересечение) с двумя разными доказательствами решения. Первое доказательство, которое не является комбинаторным, использует математическая индукция и производящие функции чтобы найти, что количество последовательностей этого типа равно (2k −1)п. Второе доказательство основано на наблюдении, что существует 2k −1 правильные подмножества множества {1, 2, ..., k} и (2k −1)п функции из множества {1, 2, ..., п} к семейству собственных подмножеств {1, 2, ..., k}. Последовательности для подсчета могут быть помещены во взаимно однозначное соответствие с этими функциями, где функция, сформированная из заданной последовательности подмножеств, отображает каждый элемент я к множеству {j | я ∈ Sj}.

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

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

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

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

Альтернативное биективное доказательство, данное Айгнером и Циглером и приписанное ими Андре Жоял, предполагает взаимное соответствие между, с одной стороны, п-узловые деревья с двумя назначенными узлами (которые могут быть одинаковыми друг с другом), и, с другой стороны, п-узел направленный псевдолеса. Если есть Тп п-узловые деревья, то есть п2Тп деревья с двумя обозначенными узлами. И псевдолесье можно определить, задав для каждого из его узлов конечную точку края, идущего наружу от этого узла; Существуют п возможные варианты конечной точки единственного ребра (позволяющие зацикливаться) и, следовательно, пп возможны псевдолеса. Обнаружив взаимное соответствие между деревьями с двумя помеченными узлами и псевдолесьями, доказательство Джояла показывает, что Тп = пп − 2.

Наконец, четвертое доказательство формулы Кэли, представленное Эйгнером и Циглером, является Доказательство двойного счета из-за Джима Питмана. В этом доказательстве Питман рассматривает последовательности направленных ребер, которые могут быть добавлены к п-узел пустой график чтобы сформировать из него одно корневое дерево, и подсчитывает количество таких последовательностей двумя разными способами. Показывая, как получить последовательность этого типа путем выбора дерева, корня дерева и упорядочения ребер в дереве, он показывает, что существуют Тпп! возможные последовательности этого типа. И, подсчитав количество способов, которыми частичная последовательность может быть расширена одним ребром, он показывает, что есть пп − 2п! возможные последовательности. Приравнивая эти две разные формулы к размеру одного и того же набора реберных последовательностей и исключая общий множитель п! приводит к формуле Кэли.

Связанные понятия

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

Рекомендации

  • Айгнер, Мартин; Циглер, Гюнтер М. (1998), Доказательства из КНИГИ, Springer-Verlag, стр. 141–146, ISBN 3-540-40460-0.
  • Стэнли, Ричард П. (1997), Перечислительная комбинаторика, Том I, Кембриджские исследования по высшей математике, 49, Cambridge University Press, стр. 11–12, ISBN 0-521-55309-1.