Ну давайте.
Доказательство, которое я очень люблю и многие годы рассказываю в
разных курсах — это доказательство принадлежит не самому Кэли.
Его идея принадлежит Прюферу.
Ну я уже сказал, что есть не одна сотня доказательств,
поэтому я лично по прошествии, ну скольких, 150-ти (уже даже больше) лет
с момента доказательства Кэли имею право выбрать любое из них.
И вот я беру доказательство Прюфера.
Идея этого доказательства она очень симпатичная.
Нужно установить взаимнооднозначное соответствие между множеством всех
деревьев на n вершинах и множеством последовательностей натуральных чисел.
Ну смотрите, вот давайте, действительно,
рассмотрим множество всех последовательностей
натуральных чисел,
принадлежащих множеству 1, 2, ..., n,
ну и таких, что каждое из этих последовательностей имеет длину (n – 2).
Ну давайте я вот здесь вот допишу.
Множество всех последовательностей натуральных...
Давайте так: множество всех последовательностей длины (n – 2),
которые состоят из натуральных чисел, принадлежащих множеству 1, 2, ..., n.
Ну это очень простое комбинаторное упражнение — посчитать,
что количество этих последовательностей, конечно, равняется n в степени (n – 2).
Просто на каждую позицию последовательностей мы можем поставить
любое из этих n чисел, поскольку длина последовательности (n – 2),
и у нас никто еще не отменял комбинаторное правило умножения, то вместе получаем,
что этих последовательностей n в степени (n – 2).
Но это совершенно очевидно.
Вот. Другое дело, совершенно непонятно сходу: а
с какой стати множество деревьев находится во
взаимнооднозначном соответствии с множеством таких последовательностей?
Конечно, если мы установим установим такое взаимнооднозначное соответствие,
то мы и докажем, что количество деревьев — это n в степени (n – 2).
Я в этом месте люблю вспоминать, как в Москву однажды приехал такой замечательный
математик Петер Франкл венгерского происхождения, живущий сейчас в Японии.
Такой большой классик комбинаторики, замечательный в молодости,
в юности победитель международных олимпиад,
а сейчас один из ведущих шоу на японском телевидении.
Вообще, очень колоритная личность.
Он приезжал в лекцией в Яндекс по нашему приглашению и
рассказывал математику, жонглировал формулами,
а потом вдруг прекращал это дело и говорил: «Давайте передохнем».
Брал шарики или булавы и начинал ими тоже жонглировать.
Но почему я в этом месте про него вспоминаю?
Да, очень забавный, очень колоритный тип.
Но вспоминаю я вот почему.
Он начал свою лекцию с рассказа про некоторое комбинаторное утверждение,
которое доказывалось ровно с помощью такой же идеи, что мы устанавливаем какое-то
взаимнооднозначное соответствие и за счет этого доказываем некоторую формулу.
Но он почему-то очень долго это объяснял, и я думаю, что вот эта аналогия,
о которой он говорил, она действительно очень симпатичная.
Он говорил, что древние люди они не умели считать.
И поэтому когда они хотели проверить,
что их бараны, которых они отправили пастись на пастбища, не
потерялись и вернулись все в целостности и сохранности обратно в стойло,
они делали так: они выпускали очередного барана и клали в коробку камень,
ну или куда-то там откладывали в сторону камень.
Выпускали очередного барана — откладывали в сторону камень.
И так вот сколько баранов вышло, столько камней в коробке и лежало.
Ну и обратно, когда бараны эти возвращались, они, наоборот,
перекладывали камни в другое место.
И если в итоге переложенных камней было просто общее количество,
то они были уверены, что, слава богу, бараны вернулись.
Вот. Там правда произошел забавный казус.
Франкл захотел рассказывать лекцию по-русски.
Такой забавный момент, но он действительно довольно прилично говорит по-русски.
Он, вообще, полиглот.
Он и по-французски может, и по-английски, там, по какому угодно, по-венгерски,
естественно, по-японски.
Но он рассказывал лекцию по-русски, нам как-то по-японски все равно не с руки,
это понятно.
Вот. И он забыл, как будет «баран».
Ну забыл слово «баран».
Он нарисовал что-то такое очень смешное.
Что-то такое.
Я рисую очень плохо, и он рисовал очень плохо.
Что-то такое.
С рожками.
И спросил: «Вот я забыл, как это называется».
Ему сказали: «Козел».
И дальше он рассуждал про этих козлов.
Ну как-то вот неудачно совершенно, потому что потом вечером мы пошли в ресторан,
и кончилось дело тем, что он спросил, а нет ли у них козла на ужин, имея в виду,
конечно, баранину.
Вот такая вот была печальная история.
Ну, короче говоря, идея доказательства ровна такая, как он ее озвучивал.
Надо просто каждому дереву на n вершинах однозначно сопоставить некоторую вот такую
последовательность натуральных чисел.
Это и будет тот самый камень, который соответствует барану.
То есть дерево — это баран или козел, если хотите,
а камень — это вот такая последовательность.
Иными словами, мы хотим, можно по-другому сказать, закодировать каждое дерево
ну не от пьянства, конечно, а закодировать его последовательностью чисел натуральных.
Вот.
Поэтому зачастую говорят не просто фамилию Прюфера, а говорят «коды Прюфера».
Сейчас я опишу, как строятся коды Прюфера.