Зарегистрируйтесь для доступа к 15+ бесплатным курсам по программированию с тренажером

Подсчет по биекции Комбинаторика

eyJpZCI6ImVhMGZmYWE3ZWIzMWM1M2QzYWE3MGZlOGU2ZGEzMDQ4LnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=0c6b6b63603bb0df61fa765ef2cddc6c3781708a78a6deb6bff91bb1a4613c01

Самый простой способ посчитать что-либо — это соотнести объекты с чем-то более простым. Например, можно изучить абстрактные операции на бытовых примерах: соотносить числа и множества с книгами и книжными полками.

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

Теорема Кейли

Теорема Кейли применяется, чтобы подсчитать количество меченых прямых деревьев. Другими словами, теорема Кейли помогает ответить на вопрос: «Сколько всего существует деревьев на фиксированном множестве вершин множестве ?».

При этом характер элементов не важен. Например, мы можем взять такое выражение:

В этом случае ответ будет зависеть не от , а только от размера . Обозначим это число через .

Теперь сгенерируем деревья. Сначала определяем все возможные формы деревьев — то есть немеченые деревья на вершинах.

Затем найдем все способы присвоить элементам их метки:

eyJpZCI6ImFhY2QyNjAxOWU0NDg4OWMxNDgwYmViMjhiYzA4MGJmLnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=de9a0441e1e116b9fb87989a99a7d67168f12b663654e8832ea564d5235a4df6

В правой части этой схемы мы видим числа и . Они равны .

Таким образом можно сформулировать теорему Кейли:

Для всех верно, что число прямых деревьев на множестве вершин размера равно

Попробуем доказать эту теорему с помощью биекции.

Доказательство с помощью биекции

Код Прюфера – это такой способ кодирования деревьев с n вершинами с помощью последовательности.

Чтобы доказать эту теорему, выполним первый шаг:

Создадим код Прюфера дерева на множестве вершин ]

Для этого нам нужно рекурсивно определить три последовательности:

  • вершин

  • деревьев

Эти последовательности можно определить следующим образом:

  • Для , пусть — вершина степени в с наименьшим индексом

  • Для , пусть — сосед в

  • Для , пусть — дерево, которое получили, когда удалили вершины и ребра

Рассмотрим следующее дерево:

eyJpZCI6IjExYmQ5OGY1Njg1YjgyNzUwNTMwYTA1Njk4OWY4ODIxLnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=4def25ae100a27939715999cb279263689150373009ab9a3743fe178423ac7e7

У нас есть две последовательности:

Рассмотрим код Прюфера .

У каждого дерева есть хотя бы две вершины степени , поэтому вершина никогда не будет удалена. Следовательно, .

Выберем . Удаляются только вершины степени , поэтому степень вершины в дереве на единицу больше, чем число вхождений среди .

Получается, вершины степени в — это те вершины, которые не встречаются в этом выражении:

Теперь — наименьший элемент из ], который не входит в множество. Такой элемент всегда существует, и у него не более членов.

Отсюда следует, что из последовательности можно восстановить:

Поэтому мы можем восстановить в таком порядке: .

Каждое дерево дает последовательность, с помощью которой можно восстановить уникальное дерево. В этом случае повторное присоединение к однозначно определено. Поэтому количество последовательностей и количество деревьев должны быть равны. Число последовательностей равно , так как каждый принимает различных значений.

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

Выводы

В этом уроке мы изучили еще один инструмент комбинаторики — теорему Кейли, которая помогает упростить подсчеты и свести их к уже известным объектам.

Чтобы разобраться в этом теореме, мы познакомились с такими фундаментальными понятиями, как биекция и код Прюфера. Эти термины будут полезны далее в курсе по комбинаторике и в других курсах по дискретной математике.


Аватары экспертов Хекслета

Остались вопросы? Задайте их в разделе «Обсуждение»

Вам ответят команда поддержки Хекслета или другие студенты

Об обучении на Хекслете

Для полного доступа к курсу нужен базовый план

Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.

Получить доступ
1000
упражнений
2000+
часов теории
3200
тестов

Открыть доступ

Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно

  • 130 курсов, 2000+ часов теории
  • 1000 практических заданий в браузере
  • 360 000 студентов
Отправляя форму, вы принимаете «Соглашение об обработке персональных данных» и условия «Оферты», а также соглашаетесь с «Условиями использования»

Наши выпускники работают в компаниях:

Логотип компании Альфа Банк
Логотип компании Aviasales
Логотип компании Yandex
Логотип компании Tinkoff

Используйте Хекслет по-максимуму!

  • Задавайте вопросы по уроку
  • Проверяйте знания в квизах
  • Проходите практику прямо в браузере
  • Отслеживайте свой прогресс

Зарегистрируйтесь или войдите в свой аккаунт

Отправляя форму, вы принимаете «Соглашение об обработке персональных данных» и условия «Оферты», а также соглашаетесь с «Условиями использования»
Изображение Тото

Задавайте вопросы, если хотите обсудить теорию или упражнения. Команда поддержки Хекслета и опытные участники сообщества помогут найти ответы и решить задачу