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

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

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

История

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

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

${(x_{1}+\dots +x_{n})}^{n-2}\cdot (x_{1}\cdot x_{2}\cdot \ldots \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+{\tfrac {1}{2}}\cdot a_{2}\cdot x^{2}+\dots +{\tfrac {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.