WikiSort.ru - Не сортированное

Теорема Кэли о числе деревьев — явное выражение для числа деревьев с данным числом пронумерованных вершин.

История

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

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

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

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

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

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

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

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

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

• Формула Кэли немедленно следует из свойств кода Прюфера — способа однозначного кодирования ${\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]

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

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

  ${\displaystyle m^{n-1}\cdot n^{m-1}.}$

• Матричная теорема о деревьях даёт выражение на число остовных деревьев графа через определитель определённой матрицы построенной по графу.

Примечания

Литература

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