Изменения

Можно доказать формулу двумя способами:. * ''Доказательство 1Первый способ.''  Так как между помеченными деревьями порядка <tex>n</tex> и последовательностями длины <tex>n - 2</tex> из чисел от <tex>1</tex> до <tex>n</tex> существует биекция ([[Коды Прюфера|Код Прюфера]]), <br> то количество помеченных деревьев совпадает с количеством последовательностей длины <tex>n - 2</tex> из чисел от <tex>1</tex> до <tex>n</tex> = <tex>n^{n - 2}</tex>.* ''Доказательство 2Второй способ.'' С помощью [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа |матрицы Кирхгофа]] для полного графа на <tex>n</tex> вершинах. Число помеченных деревьев порядка <tex>n</tex>, очевидно, равно числу остовов в полном графе <tex>K_n</tex>, которое есть <tex>n^{n-2}</tex> по следствию теоремы Кирхгофа.

==См. также==*[[Матрица Кирхгофа]]*[[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]]*[[Связь матрицы Кирхгофа и матрицы инцидентности]]*[[Коды Прюфера]] == Источники информации==* # [http://rain.ifmo.ru/cat/view.php/theory/graph-general/cayley-2008 Дискретная математика: Алгоритмы. Формула Кэли]