Теорема Кэли о числе деревьев

У этого термина существуют и другие значения, см. Теорема Кэли.

Полный список деревьев на 2, 3 и 4 пронумерованных вершинах: $2^{2-2}=1$ дерево с 2 вершинами, $3^{3-2}=3$ дерева с 3 вершинами и $4^{4-2}=16$ деревьев с 4 вершинами.

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

Количество деревьев на n пронумерованных вершинах оказывается также равным числу разложений n-цикла (12…n) в произведение (n-1) транспозиции, а также числу (соответствующим образом нормированных) многочленов степени n с заданными (n-1) критическими значениями общего положения. Наконец, это последнее является частным случаем топологической классификации разветвлённых накрытий сферы Римана — тем самым, подсчёт числа деревьев оказывается частным случаем вычисления чисел Гурвица, соответствующим случаю накрывающей поверхности рода 0.

Литература

• Ю. М. Бурман, записки курса «Критические значения многочленов»: [1], [2], [3], [4].
• М. Э. Казарян, записки курса «Геометрия, топология и комбинаторика разветвленных накрытий сферы».
• A. Cayley (1889). «A theorem on trees». Quart. J. Math 23: 376–378.
• T. Ekedahl, S. Lando, M. Shapiro, A. Vainshtein. Hurwitz numbers and Hodge integrals.