%% -*-mode: LaTeX; tex-main-file: "w.tex"; -*-

\title{Перечисление деревьев\прим{В тексте статьи наблюдается некоторый уклон в
  химию. Причина этого в том, что статья представляет собой обработку
  части курса лекций, прочитанных автором в Московском высшем
  химическом колледже весной 1993 года.}}
\author{С.\иниц{}В.\иниц{}Дужин}

\def\Aut{\mathop{\mathrm {Aut}}\nolimits}
\def\smaller{\footnotesize}
%%\newtheorem{theorem}{Теорема}
%%\newtheorem{corrol}{Следствие}
%
\affiliation{\noindent С.\иниц{}В.\иниц{}Дужин, ПОМИ
  им.~В.\иниц{}А.\иниц{}Стеклова РАН}
\begin{document}
%% {\def\thefootnote{}%{{\mathsurround=0pt ${}^\dagger$}}
%% \footnotetext{}

%% }


\begin{epigraph}{0.5}{Л.~Толстой. Анна Каренина}
  --- Счел ли ты деревья?

  --- Как счесть деревья? --- смеясь, сказал
 Степан Аркадьич,\dots--- Сочесть пески, лучи планет
 хотя и мог бы ум высокий\dots
\end{epigraph}

\section{Формулировка результатов}
%
{\it Деревом\/} называется связный граф, не имеющий циклов.
На рисунке~\ref{pic1} 
изображены все деревья с числом вершин, не превосходящим 5.
(Точный смысл этого утверждения заключается в том, что любое дерево,
имеющее не более 5 вершин, {\it изоморфно\/} одному из деревьев,
нарисованных на картинке, а никакие два из этих деревьев не изоморфны друг
другу.)

\begin{figure}
  \centerline{\mpfile{count}{1}}
  \caption{Деревья с числом вершин $\le5$}\label{pic1}
\end{figure}

%% \begin{center}
%% \unitlength=15pt
%% \begin{picture}(16,4)
%%   \put(0,0){\circle*{0.2}}
%%   \put(2,0){\circle*{0.2}}
%%   \put(2,1){\circle*{0.2}}
%%   \put(2,0){\line(0,1){1}}
%%   \put(4,0){\circle*{0.2}}
%%   \put(4,1){\circle*{0.2}}
%%   \put(4,2){\circle*{0.2}}
%%   \put(4,0){\line(0,1){2}}
%%   \put(6,0){\circle*{0.2}}
%%   \put(6,1){\circle*{0.2}}
%%   \put(6,2){\circle*{0.2}}
%%   \put(6,3){\circle*{0.2}}
%%   \put(6,0){\line(0,1){3}}
%%   \put(7.5,0){\circle*{0.2}}
%%   \put(7.5,1){\circle*{0.2}}
%%   \put(7.5,2){\circle*{0.2}}
%%   \put(8.5,1){\circle*{0.2}}
%%   \put(7.5,0){\line(0,1){2}}
%%   \put(7.5,1){\line(1,0){1}}
%%   \put(10.5,0){\circle*{0.2}}
%%   \put(10.5,1){\circle*{0.2}}
%%   \put(10.5,2){\circle*{0.2}}
%%   \put(10.5,3){\circle*{0.2}}
%%   \put(10.5,4){\circle*{0.2}}
%%   \put(10.5,0){\line(0,1){4}}
%%   \put(12,0){\circle*{0.2}}
%%   \put(12,1){\circle*{0.2}}
%%   \put(12,2){\circle*{0.2}}
%%   \put(12,3){\circle*{0.2}}
%%   \put(13,2){\circle*{0.2}}
%%   \put(12,0){\line(0,1){3}}
%%   \put(12,2){\line(1,0){1}}
%%   \put(14,1){\circle*{0.2}}
%%   \put(15,0){\circle*{0.2}}
%%   \put(15,1){\circle*{0.2}}
%%   \put(15,2){\circle*{0.2}}
%%   \put(16,1){\circle*{0.2}}
%%   \put(15,0){\line(0,1){2}}
%%   \put(14,1){\line(1,0){2}}
%% \end{picture}
%% \medskip

%% {\small{\bf Рис. 1.} Деревья с числом вершин $\le5$}
%% \medskip
%% \end{center}

%% \parbox{12.5cm}{\smaller
%% \subparagraph{Задача 1.} 
\begin{задача}
Докажите, что связный граф является деревом тогда
и только тогда, когда число его ребер на единицу меньше числа вершин.
\end{задача}
%% }
%% \medskip

Задача перечисления деревьев, \те нахождения формул для числа
$t_n$ различных деревьев с $n$ вершинами\т  одна из основных, и притом
самых красивых, задач перечислительной комбинаторики.
Впервые эту задачу поставил знаменитый английский математик
Артур Кэли (см. [1]) в связи с задачей определения числа изомеров предельных
углеводородов $C_nH_{2n+2}$.
Каждый такой изомер описывается способом соединения атомов углерода,
\те деревом с $n$ вершинами валентности, не превосходящей~4.
Надо сказать, что А.\иниц{}Кэли, найдя изящное рекуррентное соотношение для
числа всех деревьев, не нашел сколько\д{}нибудь удовлетворительной
формулы для числа предельных алканов\т  такая формула была впервые
получена венгерским математиком Д.\иниц{}Пойа в работе [2].

%% \parbox{12.5cm}{\smaller
%% \subparagraph{Задача 2.}
\begin{задача}
Попробуйте вывести эту формулу, дочитав этот текст до конца и
используя изложенные здесь методы.
\end{задача}
%% }
%% \medskip

Все известные науке способы перечисления деревьев основываются
на предварительном перечислении так называемых {\it корневых\/}
деревьев.

Корневым деревом называется дерево, в котором отмечена одна вершина,
называемая корнем.

\begin{figure}[h]
  \centerline{\mpfile{count}{2}}
  \caption{Корневые деревья с числом вершин $\le4$}\label{pic2}
\end{figure}

%% \begin{center}
%% \unitlength=15pt
%% \begin{picture}(20,4)
%%   \put(0,0){\circle*{0.2}}
%%   \put(0,0){\circle{0.3}}
%% %
%%   \put(2,0){\circle*{0.2}}
%%   \put(2,0){\circle{0.3}}
%%   \put(2,1){\circle*{0.2}}
%%   \put(2,0){\line(0,1){1}}
%% %
%%   \put(4,0){\circle*{0.2}}
%%   \put(4,0){\circle{0.3}}
%%   \put(4,1){\circle*{0.2}}
%%   \put(4,2){\circle*{0.2}}
%%   \put(4,0){\line(0,1){2}}
%% %
%%   \put(7,0){\circle*{0.2}}
%%   \put(7,0){\circle{0.3}}
%%   \put(6,1){\circle*{0.2}}
%%   \put(8,1){\circle*{0.2}}
%%   \put(7,0){\line(-1,1){1}}
%%   \put(7,0){\line(1,1){1}}
%% %
%%   \put(10,0){\circle*{0.2}}
%%   \put(10,0){\circle{0.3}}
%%   \put(10,1){\circle*{0.2}}
%%   \put(10,2){\circle*{0.2}}
%%   \put(10,3){\circle*{0.2}}
%%   \put(10,0){\line(0,1){3}}
%% %
%%   \put(12,0){\circle*{0.2}}
%%   \put(12,0){\circle{0.3}}
%%   \put(11,1){\circle*{0.2}}
%%   \put(11,2){\circle*{0.2}}
%%   \put(13,1){\circle*{0.2}}
%%   \put(12,0){\line(-1,1){1}}
%%   \put(12,0){\line(1,1){1}}
%%   \put(11,1){\line(0,1){1}}
%% %
%%   \put(16,0){\circle*{0.2}}
%%   \put(16,0){\circle{0.3}}
%%   \put(15,1){\circle*{0.2}}
%%   \put(16,1){\circle*{0.2}}
%%   \put(17,1){\circle*{0.2}}
%%   \put(16,0){\line(0,1){1}}
%%   \put(16,0){\line(-1,1){1}}
%%   \put(16,0){\line(1,1){1}}
%% %
%%   \put(19,0){\circle*{0.2}}
%%   \put(19,0){\circle{0.3}}
%%   \put(19,1){\circle*{0.2}}
%%   \put(18,2){\circle*{0.2}}
%%   \put(20,2){\circle*{0.2}}
%%   \put(19,0){\line(0,1){1}}
%%   \put(19,1){\line(-1,1){1}}
%%   \put(19,1){\line(1,1){1}}
%% \end{picture}
%% \medskip

%% {\small{\bf Рис. 2.} Корневые деревья с числом вершин $\le4$}
%% \medskip
%% \end{center}

%% \parbox{12.5cm}{\smaller
%% \subparagraph{Задача 3.} 
\begin{задача}
Деревья и корневые деревья естественно возникают в
различных, иногда весьма отдаленных друг от друга областях математики.
Вот пример, недавно использованный Е.\иниц{}В.\иниц{}Бабаевым (МГУ)
в его топологической теории структуры химических молекул.
Проверьте, что различные, с точностью до гомеоморфизма,
расположения $n$ непересекающихся окружностей на сфере перечисляются
деревьями с $n+1$ вершиной, а различные расположения $n$ непересекающихся
окружностей на плоскости перечисляются корневыми деревьями с
$n+1$ вершиной.
(Указание: области, на которые окружности делят поверхность,
соответствуют вершинам дерева; при этом неограниченная часть плоскости
отвечает корню.)
\end{задача}
%% }
%% \medskip

\track{Корневые деревья считаются одинаковыми} (изоморфными), если\linebreak между ними
существует изоморфизм, при котором корень переходит в корень.
Сколько есть различных способов отметить корень в данном дереве?
Столько, сколько у данного дерева неподобных (существенно различных)
вершин, \те вершин, не переводимых друг в друга посредством автоморфизмов
дерева как графа. Точное определение числа неподобных вершин\т 
это число орбит в множестве вершин $V(G)$ данного дерева $\Gamma$ при действии
группы автоморфизмов $\Aut(\Gamma)$.

Пусть $t_n$\т  число неизоморфных деревьев с $n$ вершинами,
а $T_n$\т  число неизоморфных корневых деревьев с $n$ вершинами.
Значения $t_n$ и $T_n$ для малых $n$  приведены в нижеследующей
таблице:

\begin{center}\def\arraystretch{1.2}
\begin{tabular}{|c|*{7}{c|}}
\hline
$n$  & 1 & 2 & 3 & 4 & 5 &  6 &  7 \\
\hline
$t_n$ & 1 & 1 & 1 & 2 & 3 &  6 & 11 \\
\hline
$T_n$ & 1 & 1 & 2 & 4 & 9 & 20 & 48 \\
\hline
\end{tabular}
\end{center}

Глядя на эту таблицу, трудно угадать какую-либо закономерность,
управляющую поведением чисел $t_n$ и $T_n$.
Чтобы найти такую закономерность, оказывается чрезвычайно полезным
изучать числа $t_n$ и $T_n$ не по отдельности, а объединенными
в формальные степенные ряды (<<производящие функции>>)
\begin{align*}
  t(x) &= \sum_{n=1}^\infty t_nx^n = x+x^2+x^3+2x^4+\dots\\[4pt]
  T(x) &= \sum_{n=1}^\infty T_nx^n = x+x^2+2x^3+4x^4+\dots
\end{align*}

В терминах производящих функций рекуррентные соотношения между
коэффициентами $T_n$ и $t_n$ допускают следующую компактную
запись.

\begin{theorem}
$\displaystyle
T(x)=x\exp\sum_{k=1}^\infty\frac{T(x^k)}{k}\DD.
$
\end{theorem}

\begin{theorem}
$\displaystyle
t(x)=T(x)-\frac{1}{2}(T(x)^2-T(x^2)). 
$
\end{theorem}

%% \parbox{12.5cm}{\smaller
%% \subparagraph{Задача 4.}
\begin{задача}
Считая известным лишь начальный отрезок разложения
$T(x)=x+x^2+2x^3+\dots$, найдите по теореме 1 значение $T_4$,
а затем по теореме 2 значения $t_i$ для $i\le4$.
\end{задача}
%% }
%% \medskip

Для доказательства теоремы 1 мы воспользуемся теорией перечисления Пойа.
Предварительно напомним ее основные положения.

\section{Теория перечисления Пойа}
%
Теория перечисления Пойа имеет целью нахождение числа сложных
комбинаторных конфигураций в условиях действия группы подстановок.
Она развивается в следующих предпосылках.

Имеется некоторое конечное множество $M$, элементы которого
называются <<позициями>>. На множестве позиций задано действие
конечной группы $G$.

Позиции можно заполнять <<фигурами>>, \те элементами некоторого,
возможно бесконечного, множества $\Phi$.
Каждой фигуре из множества $\Phi$ приписан некоторый <<вес>>,
являющийся неотрицательным целым числом, и для каждого $n\ge0$
известно число $F_n$ фигур веса $n$. Производящая функция
$F(x)=\sum_{n=0}^\infty F_n x^n$ называется <<ряд, перечисляющий
фигуры по их весам>>.

В некоторых ситуациях вместо позиций удобнее говорить об
<<объектах>>, а вместо фигур\т  о свойствах этих объектов.

{\it Конфигурацией\/} называется расстановка фигур по позициям,
\те отображение $f\colon M\to\Phi$. {\it Вес\/} конфигурации\т  это
сумма весов всех расставленных фигур:
$$
  w(f)=\sum_{\mu\in M} w(f(\mu)),
$$
где через $w$ обозначена функция веса.

Действие группы $G$ на множестве $M$ естественным образом порождает
ее действие на множестве конфигураций (фигуры, расставленные по позициям,
переставляются вместе с позициями). Конфигурации, эквивалентные относительно
действия группы $G$, имеют равные веса.
Пусть $K_n$\т  число конфигураций веса $n$, различных с точки зрения
действия группы $G$, \те число $G$\д{}орбит в множестве конфигураций,
имеющих вес $n$.

Теория перечисления Пойа объясняет, как найти числа $K_n$, зная
числа~$F_n$.

Оказывается, что эту связь удобнее всего сформулировать в виде
соотношения между производящими функциями $F(x)$ и
$K(x)$, используя специальный многочлен $Z_G$ от нескольких переменных,
который определяется группой $G$  и ее действием на множестве
$M$ и называется {\it цикловой индекс\/} группы $G$.

По определению,
$$
  Z_G(y_1,y_2,\dots,y_m)=\frac{1}{|G|} \sum_{g\in G}
  y_1^{b_1(g)}y_2^{b_2(g)}\ldots y_m^{b_m(g)},
$$
где $b_i(g)$\т  число циклов длины $i$, входящих в разложение
подстановки множества $M$, которое отвечает элементу группы $g$.
(Таким образом,\linebreak каждый моном
$y_1^{b_1(g)}y_2^{b_2(g)}\ldots y_m^{b_m(g)}$
войдет в сумму с коэффициентом, равным числу элементов
группы $G$, действие которых на множестве $M$ имеет одно и то же
разложение на циклы.)
Число переменных, от которых зависит многочлен $Z_G$, определяется
наибольшей длиной цикла среди встречающихся при рассматриваемом
действии группы; во всяком случае, оно не превосходит числа
элементов множества $M$.

Ну вот, мы дали все определения, необходимые для того, чтобы
выписать, наконец, основную формулу теории перечисления Пойа.
После таких титанических усилий формула выглядит очень коротко
и просто (трудно в ученье\т  легко в бою, говорил Суворов).

\begin{theorem}[Формула перечисления Пойа]
$$
  K(x) = Z_G(F(x),F(x^2),\dots,F(x^m)).
$$
Или словами\textup: 
перечисляющий ряд для конфигураций получается при подстановке
перечисляющего ряда для фигур в цикловой индекс группы.
\end{theorem}

Обратите внимание на способ подстановки функции $F(x)$ в многочлен
$Z_G$: каждая переменная $y_k$ заменяется на выражение $F(x^k)$
(не путать с $F(x)^k$!).

Стандартным примером конфигурации является ожерелье из $n$ бусинок
двух цветов, скажем белых и красных, рассматриваемое с точностью до
самосовмещений в пространстве.
В этом случае множество фигур состоит из двух элементов (красная и
белая бусинка), которым можно приписать веса 0 и 1 соответственно.
Многочлен, перечисляющий фигуры, имеет вид $1+x$.
Множество позиций представляет собой набор вершин правильного
$n$-угольника, на котором действует группа всех его движений $D_n$.

%% \parbox{12.5cm}{\smaller
%% \subparagraph{Задача 5.}
\begin{задача}
Чтобы набить руку, напишите многочлен, перечисляющий двуцветные
ожерелья из 4 и 5 бусинок. Ответ проверьте при помощи здравого смысла.
\end{задача}
%% }
%% \medskip

Другой, особенно важный для химиков пример возникает в следующей
ситуация.
Множество позиций есть некоторое множество точек в пространстве,
образующее пространственную форму молекулы (например, вершины
некоторого многогранника $M$). $G$\т  группа вращений этого многогранника.
Фигуры\т  это атомы или группы атомов, которые имеют одинаковую
валентность и могут располагаться в вершинах многогранника $M$.
В этом случае конфигурации\т  это изомеры замещения данного состава.

\lt0{800}{%
Единственная трудность, которая возникает в этой химической ситуации,
заключается в том, что для полного перечисления молекул по количеству
входящих в них атомов разного вида необходимо, вообще\linebreak говоря,
вводить векторные веса и производящие функции многих переменных.
Например, если изучаются молекулы, состоящие из атомов трех типов,
то перечисляющий многочлен для фигур будет $x+y+z$, а коэффициент
при мономе $x^py^qz^r$ в перечисляющем ряде для конфигураций есть число
конфигураций, состоящих из $p$ атомов первого типа, $q$ атомов второго 
типа и $r$ атомов третьего типа.}

%% \parbox{12.5cm}{\smaller
%% \subparagraph{Задача 6.}
\begin{задача}
Напишите многочлен, который перечисляет изомеры, имеющие форму
октаэдра и состоящие из шести четырехвалентных атомов типа $A$, $B$ и $C$.
\end{задача}
%% }

\section{Доказательства}
%
Для доказательства теоремы 1 заметим, что при отбрасывании корня
корневое дерево с $n+1$ вершиной распадается на несколько корневых
деревьев с суммарным числом вершин $n$. Эти части однозначно,
с точностью до перестановки, определены данным деревом.
Обратно, из нескольких корневых деревьев всегда можно составить
новое большое корневое дерево. При этом дерево с 1 вершиной получается,
если составить вместе 0 деревьев.

Постараемся переформулировать это простое наблюдение
как некоторое свойство производящей функции $T(x)$, используя
теорию перечисления Пойа.

В качестве множества фигур у нас будет выступать множество всех
корневых деревьев. Весом дерева мы будем считать число вершин в нем.
Тогда перечисляющий ряд для фигур есть в точности производящая
функция для числа корневых деревьев $T(x)$.

Рассмотрим составление нового корневого дерева со степенью корня
$r$ как образование конфигурации из $r$ фигур.
Множество позиций есть множество ребер, выходящих из корня большого
дерева. Это множество состоит из $r$ элементов, и на нем действует
полная группа подстановок $S_r$.
Вес дерева, составленного из компонент, рассматриваемого как
конфигурация, есть по определению сумма весов составляющих его
фигур, \те на 1 меньше числа вершин в нем. Таким образом,
перечисляющий ряд для конфигураций по весам есть
$\sum_{n=0}^\infty T_{n+1}^{(r)}x^n$, где $T_{n+1}^{(r)}$ есть
число корневых деревьев с данной степенью корня $r$.
По формуле Пойа
$$
\sum_{n=0}^\infty T_{n+1}^{(r)}x^n =\frac {1}{ r!}Z_{S_r}(T(x),T(x^2),\dots).
$$
Чтобы получить соотношение для числа всех корневых деревьев,
надо просуммировать полученное равенство по всем $r$ от 0 до
бесконечности. (Значению 0 отвечает, как мы уже говорили, дерево
с 1 вершиной; при этом группа $S_0$ есть единичная группа,
действующая на пустом множестве, а ее цикловой индекс есть
константа 1\т  в отличие от группы $S_1$, которая тоже единичная,
но действует на одноэлементном множестве и имеет цикловой индекс,
равный $y_1$.)

Суммирование дает:
$$
\sum_{n=0}^\infty T_{n+1}x^n
 = \sum_{r=0}^\infty\frac{1}{ r!}Z_{S_r}(T(x),T(x^2),\dots).
$$

Для суммы цикловых индексов всех симметрических групп существует
формула, которая доказывается сравнением коэффициентов при
одинаковых мономах в левой и правой части равенства.

%% \parbox{12.5cm}{\smaller
%% \subparagraph{Задача 7.}
\begin{задача}
Докажите формулу
$$
 \sum_{r=0}^\infty\frac{1}{r!}Z_{S_r}(y_1,y_2,\dots)=
 \exp\sum_{k=1}^\infty\frac{y_k}{k}\DD.
$$
\end{задача}
%% }
%% \medskip

Теорема 1 непосредственно вытекает из утверждения задачи 7 и предыдущего
соотношения.

\begin{corollary}
Имеет место следующая рекуррентная формула для числа корневых
деревьев\textup:
$$
T_n =\frac {1}{ n-1}\sum_{m=1}^n \Big(\sum_{p\mid m}pT_p\Big)T_{n-m}\DD.
$$
\textup(Внутренняя сумма распространяется на все делители $p$ числа
$m$.\textup) 
\end{corollary}

\begin{ТП}{Доказательство следствия}
Ряд $T(x)$ можно продифференцировать почленно:
$$
 T'(x)=\sum_{n=1}^\infty nT_n x^{n-1}
      =\sum_{n=0}^\infty (n+1)T_{n+1} x^n
$$
Теперь возьмем производную от обеих частей уже доказанного равенства
$$
T(x)=x\exp\sum_{k=1}^\infty\frac{T(x^k)}{k}\DD,
$$\enlargethispage{-5pt}
заменяя там, где надо, выражение $\exp\sum_{k=1}^\infty\frac{T(x^k)}{k}$
на $T(x)/x$. Получим:
$$
xT'(x)-T(x) = T(x) \sum_{k=1}^\infty x^k T'(x^k).
$$
Подставив сюда найденное выше выражение для $T'$, находим:
$$
\sum_{n=1}^\infty(n-1)T_n x^n=
 \sum_{q=1}^\infty T_q x^q\cdot \sum_{k=1}^\infty x^k
 \bigl(\sum_{p=1}^\infty pT_p x^{(p-1)k}\bigr).
$$
Меняя здесь порядок суммирования, можно переписать это соотношение
как
$$
\sum_{n=1}^\infty(n-1)T_n x^n=
 \sum_{k,p,q} pT_pT_q x^{q+kp}=
 \sum_{n=1}^\infty\sum_{q+kp=n} pT_pT_q x^n.
$$
(Последний знак суммы означает, для данного $n$, суммирование по всем
тройкам целых чисел $k$, $p$, $q$, удовлетворяющим соотношению
$q+kp\double =n$.)
Наконец, приравняем коэффициенты при $x^n$ в левой и правой части
последнего равенства:
$$
(n-1)T_n = \sum_{q+kp=n} pT_pT_q
 = \sum_{m=1}^n \bigl(\sum_{p\mid m}pT_p\bigr)T_{n-m},
$$
где новый индекс суммирования $m$ соответствует  старому $kp$.
Следствие доказано.
\end{ТП}


%% \parbox{12.5cm}{\smaller
%% \subparagraph{Задача 8.}
\begin{задача}
 Запрограммируйте полученную формулу на компьютере и найдите
числа $T_n$ для $n\le15$.
\end{задача}
%% }
%% \medskip

%% \parbox{12.5cm}{\smaller
%% \subparagraph{Задача 9.}
\begin{задача}
Попробуйте найти прямое комбинаторное доказательство этой
формулы, \те смысл разбиения числа $(n-1)T_n$ на слагаемые,
указанные в правой части формулы.
\end{задача}
%% }
%% \medskip

%% \parbox{12.5cm}{\smaller
%% \subparagraph{Задача 10.}
\begin{задача}
  При помощи тождественных преобразований со степенными рядами
покажите, что теорема 1 эквивалентна следующей формуле А.\иниц{}Кэли:
$$
T(x)= x\prod_{n=1}^\infty (1-x^n)^{-T_n}.
$$
\end{задача}
%% }

%% \bigskip
Перейдем к доказательству теоремы 2, которая устанавливает связь
между числом деревьев и корневых деревьев.
Доказательство, которое будет дано, использует понятие {\it симметричного
ребра\/} графа и понятие {\it реберно\д{}корневого дерева\/}, и мы вначале
их объясним.

Ребро $e$ некоторого графа $\Gamma$ называется симметричным,
если существует автоморфизм графа, меняющий местами концевые
вершины $e$.

%% \parbox{12.5cm}{\smaller
%% \subparagraph{Задача 11.}
\begin{задача}
 Докажите, что дерево не может иметь более одного
симметричного ребра.
\end{задача}
%% }
%% \medskip

Таким образом, все деревья делятся на два типа: имеющие одно
симметричное ребро и не имеющие ни одного симметричного ребра.
(Укажите примеры тех и других).

Оказывается, такое разделение играет важную роль в подсчете
числа существенно различных (неподобных) вершин и ребер дерева.
(В п.~1 мы говорили, что связь между числом деревьев и корневых
деревьев осуществляется путем подсчета числа неподобных вершин.)

А именно, имеет место следующая лемма.

\begin{Title}{Лемма (\Narrow{0.025}{0.005}{теорема о характеристике
      неподобия для деревьев}).} 
Пусть $p$\т  число неподобных вершин\textup,
а $q$\т  число неподобных ребер некоторого дерева.
Эти числа связаны между собой так\textup:

$p=q$\textup, если дерево обладает симметричным ребром\textup,

$p=q+1$\textup, если дерево не обладает симметричным ребром.
\end{Title}


%% \subparagraph{Доказательство леммы.}
\begin{proof}
По формуле Бернсайда для числа орбит при действии группы
автоморфизмов графа $A=\Aut(\Gamma)$ на множестве вершин:
$$
  p =\frac {1}{ |A|} \sum_{\alpha\in A} v(\alpha),
$$
где $v(\alpha)$\т  число вершин, неподвижных под действием
автоморфизма $\alpha$.

Аналогично, для действия $A$ на множестве ребер:
$$
  q = \frac{1}{ |A|} \sum_{\alpha\in A} e(\alpha),
$$
где $e(\alpha)$\т число ребер, неподвижных под действием
$\alpha$.

Утверждение леммы вытекает из следующих наблюдений.

\smallskip

(i) Если дерево не обладает симметричным ребром, то ребро
может остаться на месте под действием автоморфизма, только если оба
его конца остаются на месте. Следовательно, число ребер, которые
сдвигаются, равно числу вершин, которые сдвигаются. А поскольку
общее число вершин на 1 больше, мы получаем $v(\alpha)=e(\alpha)+1$
для любого $\alpha$.

\smallskip

(ii) Если дерево имеет симметричное ребро, то группа автоморфизмов
распадается на две равные части: автоморфизмы, сохраняющие оба конца
симметричного ребра, и автоморфизмы, переставляющие эти концы.
Для автоморфизмов первого типа будет $v(\alpha)=e(\alpha)+1$,
а для автоморфизмов второго типа, наоборот, $v(\alpha)=e(\alpha)-1$
(на самом деле, как нетрудно проверить, в этом случае
$v(\alpha)=0$, $e(\alpha)=1$). Следовательно, суммы в обеих формулах
Бернсайда совпадут.

\smallskip

Лемма доказана.
%% \medskip
\end{proof}

%% \parbox{12.5cm}{\smaller
%% \subparagraph{Упражнение.} 
\begin{Упр}
Проверьте утверждение леммы для деревьев,
изображенных на рисунке 1.
\end{Упр}
%% }
%% \medskip

Чтобы вывести теорему 2 из доказанной леммы, перепишем ее утверждение
в виде тождества
$$
  1 = p-(q-s),
$$
где, как и выше, $p$ и $q$ обозначают, соответственно, число неподобных 
вершин и ребер некоторого дерева, а $s$ есть число симметричных ребер
в этом дереве.

Теперь просуммируем обе части этого тождества по всем деревьям
с данным числом вершин $n$. Что мы при этом получим?
В левой части равенства получится, очевидно, просто число всех
деревьев с $n$ вершинами $t_n$. Первое слагаемое правой части
даст в точности число всех корневых деревьев $T_n$.

\vskip0pt plus2pt

А каков гносеологический смысл суммы чисел $q-s$, \те чисел
{\it несимметричных\/} ребер, по всем деревьям с данным числом вершин?
Чтобы его установить, нам как раз и потребуется заявленное раньше
понятие реберно\д{}корневого дерева.
По аналогии с обычными корневыми (или вершинно\д{}корневыми) деревьями,
{\it реберно\д{}корневое\/} дерево\т  это дерево, в котором отмечено одно
ребро, называемое, естественно, корневым ребром.
(Проверьте для разминки, что число реберно\д{}корневых деревьев
с 4 вершинами равно 3, что коренным образом отличается от
числа вершинно\д{}корневых деревьев с 4 вершинами.)

Теперь мы готовы к тому, чтобы объяснить смысл суммы $\sum(q-s)$,
которая нас так заинтриговала. Это число $L_n$ реберно\д{}корневых деревьев
с $n$  вершинами, у которых запрещается брать в качестве корня
симметричное ребро. Давайте их перечислим.
Для этого подумаем: к чему приводит удаление корневого ребра?
Правильно, к распадению дерева на две (ровно на две!) части
с таким же общим числом вершин. Эти части, как нетрудно понять,
естественным образом снабжены структурой корневого (именно
вершинно\д{}корневого!) дерева.
Если при этом не трогать симметричных ребер (не брать их в качестве
корней\т  согласно уговору, который дороже денег),
то мы получим такое выражение числа $L_n$ через числа $T_k$:
$$
  L_n = \sum_{\substack{k+l=n\\[1pt] k<l}}T_kT_l,
$$
(суммирование только по парам неравных чисел!).
Тот же факт можно выразить на языке производящих функций,
для чего достаточно рассмотреть произведение ряда $T(x)$ сам на себя
в количестве (только!) двух экземпляров.
Немного поразмыслив, вы поймете, что формула
$$
  L(x) = \frac{1}{2} \bigl(T(x)^2-T(x^2) \bigr)
$$
как раз и выражает необходимое соотношение (вычитание $T(x^2)$\т 
это запрет на одинаковые индексы $k$ и $l$, \те запрет на симметричные
корни; двойка в знаменателе\т  дань тому факту, что перестановка
частей при составлении реберно\д{}корневого дерева не меняет результат
этого действия).\jr

%% \parbox{12.5cm}{\smaller
%% \subparagraph{Задача 12.}
\begin{задача}
 Используя доказанную теорему и результат задачи 8, найдите
значения $t_n$ для $n\le15$.
\end{задача}
%% }


%% \bigskip
%% \centerline{\bf Литература}
%% \bigskip
\begin{thebibliography}{5}
\bibitem{d1} A.~Cayley. \emph{Mathematical Papers\/}. Cambridge, 1891--1897:
v.3, 242--246 (On the theory of the analytical forms called trees),
v.9, 202--204 (On the math. theory of isomers),
v.11, 365--367 (On the analytical forms called trees),
v.13, 26--28 (A theorem on trees).


\bibitem{d2} G.~P\'olya. \emph{Kombinatorische Anzahlbestimmungen
  f\"ur Gruppen, 
Graphen und chemische Verbindungen}~/\!/  Acta Math.  B.~68, 1937.
S.~145--254.

\bibitem{d3} Ф.~Харари, Э.~Палмер. Перечисление графов. М.: Мир, 1977.


\bibitem{d4} В.~В.~Белов, Е.~М.~Воробьев, В.~Е.~Шаталов. Теория графов. М.,
Высшая школа, 1976.
  \end{thebibliography}

\end{document}
