Введение

В математике термин «комбинаторное доказательство» часто используется для обозначения одного из двух типов математических доказательств:
Доказательство двойным подсчетом. Комбинаторное тождество доказывается путем подсчета количества элементов некоторого тщательно выбранного множества двумя различными способами, чтобы получить различные выражения в тождестве. Поскольку эти выражения подсчитывают одни и те же объекты, они должны быть равны друг другу, и таким образом тождество устанавливается. Биективное доказательство. Демонстрируется, что два множества имеют одинаковое количество элементов, путем построения биекции, то есть взаимно однозначного соответствия, между ними. Термин «комбинаторное доказательство» также может использоваться в более широком смысле для обозначения любого элементарного доказательства в комбинаторике. Однако, как отмечает в своем обзоре (книги о комбинаторных доказательствах), этих двух простых методов достаточно для доказательства многих теорем в комбинаторике и теории чисел.

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

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

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

Стэнли не проводит четкого различия между биективными и доказательствами методом двойного подсчета и приводит примеры обоих видов, но разницу между этими двумя типами комбинаторных доказательств можно увидеть на примере, представленном для доказательств формулы Кейли, утверждающей, что существует nn − 2 различных деревьев, которые можно построить из заданного множества n узлов. Айгнер и Зиглер приводят четыре доказательства этой теоремы, первое из которых является биективным, а последнее — аргументом двойного подсчета. Они также упоминают, но не описывают деталей пятого биективного доказательства. Наиболее естественным способом найти биективное доказательство этой формулы было бы найти биекцию между n-узловыми деревьями и некоторым набором объектов, содержащим nn − 2 элементов, например, последовательностями из n − 2 значений, каждое из которых находится в диапазоне от 1 до n. Такую биекцию можно получить, используя последовательность Прюфера для каждого дерева. Любое дерево может быть однозначно закодировано в последовательность Прюфера, и любая последовательность Прюфера может быть однозначно декодирована в дерево; вместе эти два результата дают биективное доказательство формулы Кейли. Альтернативное биективное доказательство, представленное Айгнером и Зиглером и приписываемое ими Андре Жоялю, включает биекцию между, с одной стороны, n-узловыми деревьями с двумя выделенными узлами (которые могут совпадать), а с другой стороны — n-узловыми ориентированными псевдолесами. Если существует Tn n-узловых деревьев, то существует n2Tn деревьев с двумя выделенными узлами. Псевдолес можно определить, указав для каждого его узла конечную точку ребра, исходящего из этого узла; существует n возможных вариантов для конечной точки одного ребра (допускаются петли), и, следовательно, nn возможных псевдолесов. Найдя биекцию между деревьями с двумя отмеченными узлами и псевдолесами, доказательство Жояля показывает, что Tn = nn − 2. Наконец, четвертое доказательство формулы Кейли, представленное Айгнером и Зиглером, является доказательством методом двойного подсчета, полученным Джимом Питманом. В этом доказательстве Питман рассматривает последовательности ориентированных ребер, которые можно добавить к пустому n-узловому графу, чтобы получить единственное корневое дерево, и подсчитывает количество таких последовательностей двумя разными способами. Показывая, как получить последовательность такого типа, выбрав дерево, корень для дерева и порядок ребер в дереве, он показывает, что существует Tnn! возможных последовательностей такого типа. И, подсчитав количество способов, которыми частичную последовательность можно расширить одним ребром, он показывает, что существует nn − 2n! возможных последовательностей. Приравнивая эти две различные формулы для размера одного и того же множества последовательностей ребер и сокращая общий множитель n!, получаем формулу Кейли.

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

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