Количество помеченных деревьв — различия между версиями
(→Количество помеченных деревьев.) |
|||
Строка 8: | Строка 8: | ||
== Количество помеченных деревьев. == | == Количество помеченных деревьев. == | ||
{{Теорема | {{Теорема | ||
− | |author=Формула Кэли | + | |author=Формула Кэли |
|statement=Число помеченных деревьев порядка <tex>n</tex> равно <tex>n^{n - 2}</tex>. | |statement=Число помеченных деревьев порядка <tex>n</tex> равно <tex>n^{n - 2}</tex>. | ||
|proof= | |proof= |
Версия 21:54, 8 октября 2010
Помеченное дерево.
Определение: |
Помеченное дерево порядка n - дерево порядка | , вершинам которого взаимно однозначно соответствуют числа от 1 до n.
Количество помеченных деревьев.
Теорема (Формула Кэли): |
Число помеченных деревьев порядка равно . |
Доказательство: |
Доказательство 1. С помощью кодов Прюфера.
|