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

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

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

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

• 1 Пример
• 2 Преимущество комбинаторного доказательства
• 3 Разница между двуъективным доказательством и доказательством двойного счета
• 4 Понятия, связанные с данным
• 5 Ссылки

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

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

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

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

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

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

$(n\; k)\; k!\; (п\; -\; к)!\; =\; п!\; \{\backslash \; displaystyle\; \{\backslash \; binom\; \{n\}\; \{k\}\}\; k!\; (n-k)!\; =\; n!\}$

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

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

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

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

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

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

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

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

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

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

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

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