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

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

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

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

Пример

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

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

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

$n(n-1)\cdots (n-k+1)={\binom {n}{k}}k!,$

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

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

${\binom {n}{k}}k!(n-k)!=n!$

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

Преимущество

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

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

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

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

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

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

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

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

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

Ссылки

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

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

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

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