Формула Кэли - Cayleys formula

Полный список всех деревьев на 2,3,4 помеченных вершинах: ${\displaystyle 2^{2-2}=1}$ дерево с 2-мя вершинами, ${\displaystyle 3^{3-2}=3}$ деревья с 3 вершинами и ${\displaystyle 4^{4-2}=16}$ деревья с 4-мя вершинами.

В математика, Формула Кэли это результат теория графов названный в честь Артур Кэли. В нем говорится, что для каждого положительное число ${\displaystyle n}$, количество деревья на ${\displaystyle n}$ маркированный вершины является ${\displaystyle n^{n-2}}$.

Формула эквивалентно подсчитывает количество остовные деревья из полный график с помеченными вершинами (последовательность A000272 в OEIS ).

Доказательство

Известно множество доказательств формулы дерева Кэли.^[1]Одно из классических доказательств формулы использует Теорема Кирхгофа о матричном дереве, формула для количества остовных деревьев в произвольном графе, включающем детерминант из матрица. Последовательности Прюфера дать биективное доказательство формулы Кэли. Еще одно биективное доказательство Андре Жоял, находит взаимно однозначное преобразование между п-узловые деревья с двумя выделенными узлами и максимальными направленными псевдолеса. Доказательство двойной счет благодаря Джиму Питману подсчитывает двумя разными способами количество различных последовательностей ориентированных ребер, которые можно добавить к пустому графу на n вершинах, чтобы сформировать из него корневое дерево; видеть Двойной счет (метод доказательства) # Подсчет деревьев.

История

Формула была впервые открыта Карл Вильгельм Борхардт в 1860 г. и доказано детерминант.^[2] В короткой заметке 1889 года Кэли расширил формулу в нескольких направлениях, приняв во внимание степени вершин.^[3] Хотя он сослался на оригинальную статью Борхардта, название «формула Кэли» стало общепринятым в этой области.

Другие свойства

Формула Кэли сразу дает количество помеченных корневых леса на п вершины, а именно (п + 1)^{п − 1}.Каждый помеченный корневой лес можно превратить в помеченное дерево с одной дополнительной вершиной, добавив вершину с меткой п + 1 и соединяя его со всеми корнями деревьев в лесу.

Имеет тесную связь с коренными лесами и функции парковки, поскольку количество парковочных функций на п автомобили также (п + 1)^{п − 1}. Взаимосвязь между корневыми лесами и функциями парковки была дана М. П. Шютценбергер в 1968 г.^[4]

Обобщения

Следующее обобщает формулу Кэли на помеченные леса: Пусть Т_п,k быть количеством помеченных лесов на п вершины с k компоненты связности, такие что вершины 1, 2, ..., k все принадлежат разным связанным компонентам. Т_п,k = k п^{п − k − 1}.^[5]

Рекомендации

1. Айгнер, Мартин; Циглер, Гюнтер М. (1998). Доказательства из КНИГИ. Springer-Verlag. С. 141–146.
2. Борхардт, К.В. (1860 г.). "Uber eine Interpolationsformel für eine Art Symmetrischer Functionen und über Deren Anwendung". Математика. Abh. der Akademie der Wissenschaften zu Berlin: 1–20.
3. Кэли, А. (1889). «Теорема о деревьях». Кварта. J. Pure Appl. Математика. 23: 376–378.
4. Шютценбергер, М. П. (1968). «По проблеме перечисления». Журнал комбинаторной теории. 4: 219–221. МИСТЕР  0218257.
5. Такач, Лайош (март 1990 г.). «О формуле Кэли для подсчета лесов». Журнал комбинаторной теории, серия А. 53 (2): 321–323. Дои:10.1016/0097-3165(90)90064-4.