Формула Келі

Усі дерева з 2,3,4 поміченими вершинами

В теорії графів формула Келі обчислює кількість неорієнтованих дерев з n поміченими вершинами. Згідно з даною формулою кількість таких дерев рівна

${\displaystyle n^{n-2}.\,}$.

Формула названа на честь відомого англійського математика Артура Келі, який вивів її у 1889 році.

Доведення

Існує кілька доведень даного твердження. Подане нижче належить американському математику Джеймсу Пітману.

Для доведення формули ми двома різними способами обчислимо кількість послідовностей орієнтованих ребер, якими можна доповнити пустий граф з n поміченими вершинами до кореневого дерева з n поміченими вершинами. Перший спосіб полягає в наступному: обирається будь-яке неорієнтоване дерево з n поміченими вершинами. Позначимо їх кількість T_n(саме це число нам треба обчислити). Далі з n вершин обираємо один корінь. Після цього однозначно визначається орієнтація всіх ребер дерева і залишається лиш вибрати певну послідовність з цих n-1 ребер. Тож остаточно необхідна кількість рівна

${\displaystyle T_{n}n(n-1)!=T_{n}n!.}$

Інший спосіб полягає в покроковому додаванні орієнтованих ребер і обчисленні кількості варіантів на кожному кроці. Після n − k кроків отримується ліс з k кореневих дерев. Початковою вершиною наступного ребра може бути будь-яка з n вершин, а кінцевою котрась з кореневих вершин за винятком кореневої вершини дерева до якого належить початкова вершина. Отже загальна кількість можливих способів рівна n(k − 1). Щоб отримати необхідну кількість слід перемножити кількість варіантів на кожному з n-1 кроків:

${\displaystyle \prod _{k=2}^{n}n(k-1)=n^{n-1}(n-1)!=n^{n-2}n!.}$

Очевидно обидва одержані результати повинні бути рівними, тож ми отримуємо тотожність:

${\displaystyle \displaystyle T_{n}n!=n^{n-2}n!}$

і як наслідок:

${\displaystyle \displaystyle T_{n}=n^{n-2}}$,

що й слід було довести.

Для термінології дивіться:

• Теорія графів 
• Дерево (структура даних) 
• Дерево (теорія графів)

Література

• Р. Уилсон (1977). Введение в теорию графов. Москва: Мир.
• M. Aigner, G. Ziegler (1998). Proofs from the book. Springer Verlag.