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

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

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

История

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

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

[math]\displaystyle{ {(x_1+\dots+x_n)}^{n-2} \cdot (x_1 \cdot x_2 \cdot \ldots \cdot x_n), }[/math]

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

Кэли подробно разбирает случай [math]\displaystyle{ n=6 }[/math] и заявляет, что доказательство легко обобщается.

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

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

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

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

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

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

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

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

• Формула Кэли немедленно следует из свойств кода Прюфера — способа однозначного кодирования [math]\displaystyle{ n }[/math]-вершинного помеченного дерева упорядоченной последовательностью из [math]\displaystyle{ n-2 }[/math] номеров его вершин.

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

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

  [math]\displaystyle{ a(x)=x\cdot e^{a(x)} }[/math]

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

[math]\displaystyle{ a(x)=a_1\cdot x+\tfrac12\cdot a_2\cdot x^2+\dots+\tfrac1{n!}\cdot a_n\cdot x^n+\dots }[/math]

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

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

• Количество способов связывания графа, состоящего из [math]\displaystyle{ m }[/math] несвязных компонент, каждая размером [math]\displaystyle{ x_i }[/math] вершин, равно

  [math]\displaystyle{ 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} }[/math]

  Здесь [math]\displaystyle{ n = x_1 + x_2 + \dots + x_m }[/math] - общее количество вершин графа.

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

• Число остовных деревьев в полном двудольном графе [math]\displaystyle{ K_{m,n} }[/math] равно

  [math]\displaystyle{ T(K_{m,n}) = m^{n-1}\cdot n^{m-1}. }[/math]

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

Литература

• Ю. М. Бурман, записки курса «Критические значения многочленов»: [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.