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

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

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

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

${\displaystyle {(x_{1}+\dots +x_{n})}^{n-2}\cdot (x_{1}\cdot x_{2}\cdot \ldots \cdot x_{n}),}$

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle 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 }$

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

• Доказательство Марка Цукреа^[4] опирается на биномиальную теорему Абеля и двойной подсчёт.

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

  ${\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}}$

  Здесь ${\displaystyle n=x_{1}+x_{2}+\dots +x_{m}}$ — общее количество вершин графа.

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

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

  ${\displaystyle 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.