Формула Кэли

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

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

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

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

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

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

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