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

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

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

История

Теорема названа в честь Артура Кэли, который доказал её в 1889 году. Сам Кэли признавал, что то же утверждение было доказано раньше Карлом Борхардом и в эквивалентной формулировке ещё раньше в статье Джеймса Джозефа Сильвестра 1857 года.

В своей статье Кэли по сути доказывает более общее утверждение. Если раскрыть скобки выражения

${(x_1+\dots +x_n)}^{n-2}\cdot (x_1\cdot x_2\cdot \dots \cdot x_n),$

то коэффициент при одночлене вида $x_1^{d_1}\cdots x_n^{d_n}$ будет равен числу деревьев, у которых степени вершин равны степеням переменных данного терма: $d_1,\dots ,d_n$.

Кэли подробно разбирает случай $n=6$ и заявляет, что доказательство легко обобщается.

Формулировки

Две эквивалентные формулировки:

• Число различных деревьев на $n$ вершинах, пронумерованных числами от $1$ до $n$ равно $n^{n-2}$.

• Число остовных деревьев в полном графе $K_n$ равно $n^{n-2}$.

Связанные утверждения

• Количество деревьев на $n$ пронумерованных вершинах оказывается также равным числу разложений $n$-цикла $(1\dots n)$ в произведение $n-1$ транспозиции.

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

О доказательствах

• Формула Кэли немедленно следует из свойств кода Прюфера — способа однозначного кодирования $n$-вершинного помеченного дерева упорядоченной последовательностью из $n-2$ номеров его вершин.

• Формула Кэли также легко выводится из матричной теоремы о деревьях.

• Одно из доказательств строится на следующем соотношении

  $a(x)=x\cdot e^{a(x)}$

на экспоненциальную производящую функцию

$a(x)=a_1\cdot x+\frac{1}{2}\cdot a_2\cdot x^2+\dots +\frac{1}{n!}\cdot a_n\cdot x^n+\dots$

где $a_n$ обозначает число корневых деревьев на $n$ данных вершинах. По теореме Лагранжа об обращении рядов, из этого соотношения следует, что $a_n=n^{n-1}$. Последнее влечёт формулу Кэли поскольку для каждого остовного дерева есть ровно $n$ способов выбрать корневую вершину.

Вариации и обобщения

• Количество способов связывания графа, состоящего из $m$ несвязных компонент, каждая размером $x_i$ вершин, равно

  $T[x_m]=x_1\cdot x_2\dots x_m\cdot (x_1+x_2+\dots +x_m{)}^{m-2}=[x_m]!n^{m-2}$

  Здесь $n=x_1+x_2+\dots +x_m$ - общее количество вершин графа.

  Если каждая компонента состоит из одной вершины $(x_i=1)$, то $n=m$, и формула дает исходное число Кэли $n^{n-2}$.

• Число остовных деревьев в полном двудольном графе $K_{m,n}$ равно

  $T(K_{m,n})=m^{n-1}\cdot n^{m-1}.$

• Матричная теорема о деревьях даёт выражение числа остовных деревьев графа как определитель лапласиана (матрицы Кирхгофа) графа.

Литература

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