Самый простой способ посчитать что-либо — это соотнести объекты с чем-то более простым. Например, можно изучить абстрактные операции на бытовых примерах: соотносить числа и множества с книгами и книжными полками.
Это же упрощение работает и в математике: чтобы подсчитать сложные объекты, надо соотносить их с объектами, которые вы уже умеете считать. Для этого используется теорема Кейли. В этом уроке мы рассмотрим эту теорему и докажем ее. Вы узнаете, что такое биекция, а также умная конструкция.
Теорема Кейли
Теорема Кейли применяется, чтобы подсчитать количество меченых прямых деревьев. Другими словами, теорема Кейли помогает ответить на вопрос: «Сколько всего существует деревьев на фиксированном множестве вершин множестве ?».
При этом характер элементов не важен. Например, мы можем взять такое выражение:
В этом случае ответ будет зависеть не от , а только от размера . Обозначим это число через .
Теперь сгенерируем деревья. Сначала определяем все возможные формы деревьев — то есть немеченые деревья на вершинах.
Затем найдем все способы присвоить элементам их метки:
В правой части этой схемы мы видим числа и . Они равны .
Таким образом можно сформулировать теорему Кейли:
Для всех верно, что число прямых деревьев на множестве вершин размера равно
Попробуем доказать эту теорему с помощью биекции.
Доказательство с помощью биекции
Код Прюфера – это такой способ кодирования деревьев с n вершинами с помощью последовательности.
Чтобы доказать эту теорему, выполним первый шаг:
Создадим код Прюфера дерева на множестве вершин ]
Для этого нам нужно рекурсивно определить три последовательности:
-
-
вершин
-
деревьев
Эти последовательности можно определить следующим образом:
-
-
Для , пусть — вершина степени в с наименьшим индексом
-
Для , пусть — сосед в
-
Для , пусть — дерево, которое получили, когда удалили вершины и ребра
Рассмотрим следующее дерево:
У нас есть две последовательности:
Рассмотрим код Прюфера .
У каждого дерева есть хотя бы две вершины степени , поэтому вершина никогда не будет удалена. Следовательно, .
Выберем . Удаляются только вершины степени , поэтому степень вершины в дереве на единицу больше, чем число вхождений среди .
Получается, вершины степени в — это те вершины, которые не встречаются в этом выражении:
Теперь — наименьший элемент из ], который не входит в множество. Такой элемент всегда существует, и у него не более членов.
Отсюда следует, что из последовательности можно восстановить:
Поэтому мы можем восстановить в таком порядке: .
Каждое дерево дает последовательность, с помощью которой можно восстановить уникальное дерево. В этом случае повторное присоединение к однозначно определено. Поэтому количество последовательностей и количество деревьев должны быть равны. Число последовательностей равно , так как каждый принимает различных значений.
Биекция — это не единственный способ доказательства теоремы Кейли. Еще есть умная конструкция, которая помогает в подсчетах более сложных структур. Этот прием встречается все чаще, но пока мы не будем останавливаться на нем подробно из-за объемного и трудоемкого доказательства.
Выводы
В этом уроке мы изучили еще один инструмент комбинаторики — теорему Кейли, которая помогает упростить подсчеты и свести их к уже известным объектам.
Чтобы разобраться в этом теореме, мы познакомились с такими фундаментальными понятиями, как биекция и код Прюфера. Эти термины будут полезны далее в курсе по комбинаторике и в других курсах по дискретной математике.
Остались вопросы? Задайте их в разделе «Обсуждение»
Вам ответят команда поддержки Хекслета или другие студенты
Для полного доступа к курсу нужен базовый план
Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.
