В математике формула Кэли является результатом теории графов имени Артура Кэли . Он утверждает, что для каждого положительного целого числа количество деревьев на помеченных вершинах равно .
Формула эквивалентно подсчитывает количество остовных деревьев полного графа с помеченными вершинами (последовательность 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 принадлежат различным компонентам связности. Тогда Т п , k знак равно k п п - k - 1 . [5]
