Двойной счёт

Очередной параграф, довольно простой, почти закрывающая тему элементарной комбинаторики в этой главе (к комбинаторике я буду возвращаться в дальнейшем многократно, но только уже когда будет введены понятия анализа и алгебры).

Читать как всегда лучше в pdf, для кармы будет полезно помогать на GitHub.

Напомню, что в графе степенью вершины мы назвали количество рёбер, ей инцидентных.

Теорема. Пусть  — множество вершин некоторого графа,  — количество его рёбер. Тогда

Доказательство. Мы можем пересчитать все рёбра графа двумя способами: собственно, пересчитывая сами рёбра (получим в этом случае ), либо же пересчитывая вершины и складывая степени . В этом случае, правда, получится, что каждое ребро мы учтём два раза, поскольку каждое ребро инцидентно ровно двум вершинам.

Это элементарное доказательство является простейшим примером доказательства методом двойного счёта. Приём этот выглядит всегда одинаково: мы берём некоторый набор объектов и считаем его двумя разными способами, получая в итоге одно и то же значение, но записанное в разном виде. По большому счёту рекурсивные формулы для вычисления числа сочетаний, чисел Белла и чисел Стирлинга, а так же формулы их сумм, доказывались нами именно методом двойного счёта, только мы не произносили этого слова. Остаток этого параграфа мы посвятим разбору ещё нескольких подобных примеров.

Теорема.

Доказательство. Пусть у нас имеется мужчин и женщин. Нам надо выбрать из них группу человек. Очевидно, что это можно сделать способами. С другой стороны, мы можем отдельно рассмотреть все варианты, когда мы выбираем мужчин и женщин, что даёт нам левую часть.

Следствие.
\end{corollary}
Доказательство. Достаточно положить и заметить, что .

Теорема.

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

Теорема.

Доказательство. Справа, как мы увидели в конце прошлого параграфа, перечислено количество сюръекций . Однако, их можно перечислить и по-другому. Пусть  — некоторая сюръекция, тогда прообразы , , ... не пусты и задают некоторое разбиение множества на подмножеств. Таких разбиений существует штук. В то же время если  — некоторая перестановка на , то так же задаёт то же самое разбиение множества , хотя сюръекция уже будет другой. Поскольку мы имеем таких перестановок , общее количество сюръекций может быть так же определено как .

Определение. Граф называется связным, если в нём существует путь между любыми двумя вершинами.

Определение. Деревом называется связный граф без циклов.

Деревья часто применяются в компьютерных системах поиска. Самый распространённый вариант — это двоичные деревья поиска, которые представляют собой следующую структуру: каждая вершина дерева обладает некоторым значением и, возможно, тремя гранями, называемых ветвями. Одна ветвь ведёт в направлении корня, другая ветвь, называемая левой, ведёт ко всем вершинам со значениями, меньшими чем текущее, а вторая ветвь, называемая правой, ведёт к большим значениям. Если предположить, что значения — это строки, то их порядок может восприниматься как алфавитный. Пример такого бинарного дерева поиска представлен на рисунке 3.11.

Предположим, что в дереве на рисунке 3.11 так же в каждом узле дерева записан телефон, и что мы захотели найти телефон Ольги. Если бы мы просматривали все телефоны подряд, то в случае их упорядоченности по алфавиту, прежде чем мы наткнулись бы на Олин телефон, нам пришлось бы проверить шесть записей. Однако, вместо этого мы могли бы искать телефон в дереве, двигаясь от корня: вначале мы увидели бы, что имя "Ольга" должно идти после имени Николай, что значит, что мы должны искать по правой ветви от корня, где мы встречаем имя Роман. Ольга идёт раньше Романа по алфавиту, поэтому мы продолжаем искать её в левой ветви, где и находим её телефон. Итого нам потребовалось три шага поиска: вдвое быстрее чем при последовательном переборе.

Упражнение. Пусть мы ищем телефон Фиофанта. Покажите, что при последовательном поиске нам потребовалось бы 7 шагов, чтобы убедиться, что такого телефона нет, а при поиске в дереве всего 3 шага.

Упражнение. Пусть у нас теперь имеется дерево, в котором записано 2147483647 телефонных номеров. Например, это может база данных ФСБ или ещё какая. Покажите, что используя бинарное дерево поиска, мы можем найти любой телефон (или убедиться, что его нет в базе) максимум за 31 шаг.

Последнее упражнение показывает, что использование деревьев может здорово упростить поиск информации (зачастую ускорение получается в миллионы раз). Собственно очень похожим образом устроены почти все базы данных, и без деревьев не было бы ни компании Гугл, ни, наверное, вообще компьютерной техники в современном её виде. Чтобы уметь анализировать скорость работы алгоритмов, нам прежде всего необходимо уметь пересчитывать все деревья.

Бинарные деревья — это в общем-то частный случай дерева. Как перечислить все возможные деревья поиска мы поймём позже в нашем курсе (мы изучим общие подходы), а пока что же мы перечислим просто все возможные деревья с вершинами. При изучении следующего доказательства важно иметь ввиду следующие уточнения постановки задачи, которые мы подразумеваем:

1. Дерево не обладает корнем; все вершины равнозначны;
2. Вершины деревьев имеют определённые метки (данные), то есть даже если два дерева имеют одинаковую форму внешне, но вершины имеют разные именования, мы рассматриваем эти деревья как различные;
3. Каждая вершина может иметь произвольное количество инциентных рёбер.

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

Пример функции

x	1	2	3	4	5
f(x)	4	1	1	2	4

Теорема. Существует деревьев с вершинами.

Доказательство. Подсчитаем количество функций двумя способами. С одной стороны количество таких функций , это тривиальная теорема, рассмотренная нами в § 3.1. Попробуем теперь подсчитать количество функций , сопоставив каждой функции некоторое дерево. Это довольно сложное рассуждение, поэтому будем рассматривать его на примере функции , значения которой заданы в таблице 3.2. Пусть

то есть это множество таких элементов из , что применяя к ним последовательно несколько раз, мы в какой-то момент получим тот же . Для функции из нашего примера .

Если упорядочить по возрастанию элементы и рассмотреть ограничение на нём , то эта функция будет действовать как перестановка , которую мы можем записать строкой (в примере будет ). Теперь, выбрав в качестве вершин графа элементы , мы можем соединить вершины из в порядке, заданном перестановкой. Элементы пока правда остаются изолированными. Чтобы сформировать из них дерево, для каждого значения , если добавим ребро . Для функции из примера это будут рёбра 31 и 54. Получившееся дерево изображено на рисунке 3.12.

Надо теперь показать, что и для каждого дерева мы можем задать функцию. Это делается в полной аналогии: вначале выбираем в дереве условные «начало» и «конец» (внимание!) и находим путь от начала к концу. Вершины этого пути задают множество , а последовательность вершин перестановку . Для вершин , не вошедших в этот путь, в качестве значения выбираем следующую вершину по пути от до «конца» дерева.

Остаётся лишь заметить, что заданная конструкция даёт нам не просто дерево, а дерево с выбранными «началом» и «концом». У дерева с вершинами есть способов определить начало и конец, поэтому количество произвольных деревьев в раз меньше, чем количество функций . (По-хорошему так же надо более чётко указать, что соответствие деревьев и функций в данном случае действительно однозначное, но это не сложно и я оставляю это в качестве упражнения читателю).