Подсчет числа пронумерованных деревьев

Выполнил Горбунов Дмитрий,

школа-интернат «Интеллектуал», 7 класс,

руководитель Сгибнев Алексей Иванович

Графом называется набор точек, некоторые из которых соединены линиями. Точки называются вершинами графа, а соединяющие линии – рёбрами.

Граф называется связным, если из любой вершины можно по рёбрам «пройти» в любую другую вершину. Нетрудно доказать, что наименьшее количество рёбер, при котором граф с n вершинами может быть связным, равно n – 1. (См., например, В.М. Гуровиц, В.В. Ховрина «Графы». М., МЦНМО, 2009.)

Деревом называется связный граф с n вершинами и n-1 рёбрами.

Задача. Какое количество деревьев можно построить на n пронумерованных вершинах?

Очевидно, что на 1 вершине можно построить лишь 1 дерево с 0 ребрами. На 2 вершинах – 1 дерево. На 3 вершинах – 3 дерева. На 4 – 16. Ниже показаны способы для таких количеств вершин.

Пусть n = 5. Теперь прямой подсчет уже достаточно сложен. Подсчитаем количество неизоморфных деревьев. Их три:

Первое из них можно пронумеровать 5 способами, второе – способами, третье – тоже способами. Сложим все это: 5 + 60 + 60 = 125. Соберем данные в таблицу:

Выдвигаем гипотезу.

Теорема. Количество деревьев, которые можно построить на n вершинах, равно n^{n –2}.

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

Определения. Помеченным деревом называется дерево, в котором выделены две вершины, одну из них будем называть левым концом, а другую – правым. (Например, можно отмечать левый конец кружочком, а правый – квадратом.)

Пусть F_n – количество помеченных деревьев на n вершинах, а K_n – количество деревьев на n вершинах графа.

Для доказательства потребуется лемма.

Лемма. F_n = K_nn ².

Доказательство. Действительно, берем количество деревьев и выбираем одну из вершин n способами и другую – n способами. Итого – K_nn ² = F_n, ч.т.д.

Доказательство теоремы. По лемме 1 F_n = K_nn ². Если мы докажем, что F_n = nⁿ, то

Рассмотрим множество помеченных деревьев на n вершинах и множество ориентированных графов, у которых:

1) из каждой вершины идет ровно одно ребро;

2) между двумя вершинами не более двух ребер;

3) разрешены петли.

Количество способов построить такой ориентированный граф – nⁿ, поскольку из первой вершины ребро можно провести n способами (петля и n – 1 вершина), из второго – тоже n и т.д., в результате получается nⁿ.

Докажем, что множества помеченных деревьев и ориентированных графов равномощны. Рассмотрим какой-либо ориентированный граф и попробуем превратить его в помеченное дерево. Введем новое множество M ₁, в которое включим все вершины циклов графа, причем номера вершин идут в порядке возрастания. Введем функцию f (x) – номер вершины, в которую идет ребро из вершины с номером x. Пусть M ₁ = { a, b, c, d, …, z } и M ₂ = { f (a), f (b), f (c), …, f (z)}. Соединим все вершины множества M ₂ ребрами: из f (a) в f (b), из f (b) в f (c) и т.д. При этом отметим f (a) левым концом, а f (z) – правым. Все остальные вершины (не включенные в множество М ₂) соединим точно так же, как и в ориентированном графе. Получилось помеченное дерево, так как мы убрали все циклы.

Нетрудно получить и обратный результат – из дерева сделать ориентированный граф. Возьмем P – путь из левого конца в правый и включим его без изменений в множество M ₂. Расположим числа в множестве P в порядке возрастания и включим результат в множество M ₁. M ₁ = { a, b, c, d, …, z }. M ₂ = { f (a), f (b), f (c), …, f (z)}. Строим циклы ориентированного графа по этим двум множествам. Оставшиеся вершины подключаем так же, как они подключены к вершинам циклов, по направлению к ним. Получился ориентированный граф.

Таким образом, мы установили взаимнооднозначное соответствие, поскольку из каждого помеченного дерева получается ориентированный граф, а из него получается то же самое помеченное дерево. Из двух ориентированных графов не может получиться одно и то же дерево, так как тогда это дерево дает 2 ориентированных графа, а этого быть не может. Аналогично и с деревьями – из двух помеченных деревьев не может получиться один ориентированный граф, так как из него тогда получается два дерева. Противоречие. Значит, установлено взаимно однозначное соответствие, а значит, эти множества равномощны. Теорема доказана.

Комментарий руководителя о ходе работы. Дима за несколько дней угадал формулу с помощью последовательного перебора помеченных деревьев с 1, 2, 3, 4 и т.д. вершинами. Затем около месяца безуспешно пытался её доказать (я ему особенно не помогал, чтобы он почувствовал сложность задачи). Когда Дима начал уставать, я стал давать ему подсказки, стараясь навести на то решение, которое знал сам. Однако в результате он придумал другое доказательство. Угаданная формула подсказывает путь доказательства: построить биекцию с множеством из n элементов, каждый из которых принимает одно из n значений. Дима нашёл такое множество и смог пройти этим путём. И это поучительная демонстрация того, что когда учитель не пытается всё жёстко распланировать, может «вырасти» что-то новое для него самого!

Комментарий математический. Эта формула называется теоремой Кэли. Её доказательство с помощью кодирования и обобщение задачи см.: Сгибнев А.И., Нетрусова Н.М. О работе семинара учебно-исследовательских работ школьников по математике // Полином. 2009. № 2. С. 95.

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

Выполнил Власенко Дмитрий,

школа-интернат «Интеллектуал», 9 класс

Руководитель: Шноль Дмитрий Эммануилович

Цели этой проектной работы:

§ Изучить последовательности, задаваемые рекуррентной формулой a_n+2 = ka_n+1+la_n, где k ≠ 0, l ≠ 0.

§ Отдельно изучить периодические последовательности этого вида.

Чтобы задать последовательность этого вида, кроме рекуррентной формулы надо задать два её начальных члена a₀ и a₁ (обычно последовательности определяются для натуральных номеров, но в этом случае удобно её начинать с нулевого члена).

Пока я в основном изучил последовательности, у которых начальные члены a₀ = 0 и a₁ = 1. Для них:

§ Получена формула n-го члена:

§ Доказано (двумя способами: по индукции и подстановкой в формулу n-го члена) следующее утверждение:

Пусть последовательность задана формулой . Тогда все члены последовательности , заданной формулой , равны (То есть , а ).

Последовательность можно называть последовательностью, сопряжённой с (по аналогии с комплексными числами).

§ Доказано, что последовательность является периодической тогда и только тогда, когда выполняются следующие условия:

1) l = –1;

2) –2 < k <2.

3)

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

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

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

ИСТОРИИ

Шноль Д.Э.

Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор...

Что будет с Землей, если ось ее сместится на 6666 км? Что будет с Землей? - задался я вопросом...

ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования...

ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: