New identities from enumeration of graphs

Abstract

In this paper, three new combinatorial identities related to the enumeration of labeled connected graphs with a given number of endpoints are presented. We give a proof of these identities independent of the enumeration of graphs. For one of the identities, a course of the proof based on formulas for enumerating graphs is outlined.

Full Text

Комбинаторные тождества часто возникают при перечислении графов (см. [2-4]). Из формул перечисления помеченных связных графов с заданным числом концевых вершин (см. [1, 9, 10]) следует несколько новых тождеств. В статье приведены доказательства трех таких тождеств, не зависящие от перечисления графов. Для одного из тождеств намечен ход доказательства с помощью формул для перечисления графов. 

Теорема 1  При $n\ge 3$ верно комбинаторное тождесто

                                              ${\displaystyle \sum _{i\mathrm{<mo>=</mo>0}}^{n-3}}{\displaystyle \sum _{j\mathrm{<mo>=</mo>3}}^{n-i}}{\mathrm{<mo\; stretchy="false">(</mo>}-\mathrm{1<mo\; stretchy="false">)</mo>}}^i\frac{{\mathrm{<mo\; stretchy="false">(</mo>}n-i\mathrm{<mo\; stretchy="false">)</mo>}}^{n-j-1}}{i\mathrm{<mo>!</mo><mo\; stretchy="false">(</mo>}n-i-j\mathrm{<mo\; stretchy="false">)</mo><mo>!</mo>}}\mathrm{<mo>=</mo>}\frac{1}{n}\mathrm{.}$                                (1)

Proof. Обозначим левую часть тождества (1) через $L_1\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}$. После замены индекса суммирования во внешней сумме $s\mathrm{<mo>=</mo>}n-i$, $i\mathrm{<mo>=</mo>}n-s$ имеем

                                    $L_1\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{\displaystyle \sum _{s\mathrm{<mo>=</mo>3}}^n}{\displaystyle \sum _{j\mathrm{<mo>=</mo>3}}^s}{\mathrm{<mo\; stretchy="false">(</mo>}-\mathrm{1<mo\; stretchy="false">)</mo>}}^{n-s-1}\frac{s^{n-j-1}}{\mathrm{<mo\; stretchy="false">(</mo>}n-s-\mathrm{1<mo\; stretchy="false">)</mo><mo>!</mo><mo\; stretchy="false">(</mo>}s-j\mathrm{<mo\; stretchy="false">)</mo><mo>!</mo>}}\mathrm{.}$

 Изменим теперь порядок суммирования в двойной сумме:

                                        $L_1\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{\displaystyle \sum _{j\mathrm{<mo>=</mo>3}}^n}{\displaystyle \sum _{s\mathrm{<mo>=</mo>}j}^n}{\mathrm{<mo\; stretchy="false">(</mo>}-\mathrm{1<mo\; stretchy="false">)</mo>}}^{n-s}\frac{s^{n-j-1}}{\mathrm{<mo\; stretchy="false">(</mo>}n-s\mathrm{<mo\; stretchy="false">)</mo><mo>!</mo><mo\; stretchy="false">(</mo>}s-j\mathrm{<mo\; stretchy="false">)</mo><mo>!</mo>}}\mathrm{.}$

После замены индекса суммирования во внутренней сумме $p\mathrm{<mo>=</mo>}s-j$, $s\mathrm{<mo>=</mo>}p+j$ и ввода биномиального коэффициента получим

                             $L_1\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{\displaystyle \sum _{j\mathrm{<mo>=</mo>3}}^n}\frac{1}{\mathrm{<mo\; stretchy="false">(</mo>}n-j\mathrm{<mo\; stretchy="false">)</mo><mo>!</mo>}}{\displaystyle \sum _{p\mathrm{<mo>=</mo>0}}^{n-j}}{\mathrm{<mo\; stretchy="false">(</mo>}-\mathrm{1<mo\; stretchy="false">)</mo>}}^{n-j-p}\left(\begin{array}{c}n-j\\ p\end{array}\right){\mathrm{<mo\; stretchy="false">(</mo>}p+j\mathrm{<mo\; stretchy="false">)</mo>}}^{n-j-1}\mathrm{.}$

Используем известное комбинаторное тождество (см. [7, с. 609, формула 15])

                          ${\displaystyle \sum _{p\mathrm{<mo>=</mo>0}}^m}{\mathrm{<mo\; stretchy="false">(</mo>}-\mathrm{1<mo\; stretchy="false">)</mo>}}^p\left(\begin{array}{c}m\\ p\end{array}\right){\mathrm{<mo\; stretchy="false">(</mo>}p+a\mathrm{<mo\; stretchy="false">)</mo>}}^q\mathrm{<mo>=</mo>0,}q\mathrm{<mo>=</mo>0,1,}\dots \mathrm{,}m-\mathrm{1,}m\ge 1.$

В нашем случае найдем

             $L_1\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\frac{1}{n}+{\displaystyle \sum _{j\mathrm{<mo>=</mo>3}}^{n-1}}\frac{{\mathrm{<mo\; stretchy="false">(</mo>}-\mathrm{1<mo\; stretchy="false">)</mo>}}^{n-j}}{\mathrm{<mo\; stretchy="false">(</mo>}n-j\mathrm{<mo\; stretchy="false">)</mo><mo>!</mo>}}{\displaystyle \sum _{p\mathrm{<mo>=</mo>0}}^{n-j}}{\mathrm{<mo\; stretchy="false">(</mo>}-\mathrm{1<mo\; stretchy="false">)</mo>}}^{n-j-p}\left(\begin{array}{c}n-j\\ p\end{array}\right){\mathrm{<mo\; stretchy="false">(</mo>}p+j\mathrm{<mo\; stretchy="false">)</mo>}}^{n-j-1}\mathrm{<mo>=</mo>}\frac{1}{n}+{\displaystyle \sum _{j\mathrm{<mo>=</mo>3}}^{n-1}}\mathrm{0<mo>=</mo>}\frac{1}{n}\mathrm{.}$

Теорема 2 При $n\ge 4$ верно комбинаторное тождесто

                                       ${\displaystyle \sum _{i\mathrm{<mo>=</mo>1}}^{n-3}}{\displaystyle \sum _{j\mathrm{<mo>=</mo>3}}^{n-i}}{\mathrm{<mo\; stretchy="false">(</mo>}-\mathrm{1<mo\; stretchy="false">)</mo>}}^{i-1}\frac{{\mathrm{<mo\; stretchy="false">(</mo>}n-i\mathrm{<mo\; stretchy="false">)</mo>}}^{n-j-1}}{\mathrm{<mo\; stretchy="false">(</mo>}i-\mathrm{1<mo\; stretchy="false">)</mo><mo>!</mo><mo\; stretchy="false">(</mo>}n-i-j\mathrm{<mo\; stretchy="false">)</mo><mo>!</mo>}}\mathrm{<mo>=</mo>}n-3\mathrm{.}$                         (2)

Proof. Обозначим левую часть тождества (2) через $L_2\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}$. После замены индекса суммирования во внешней сумме $s\mathrm{<mo>=</mo>}n-i$, $i\mathrm{<mo>=</mo>}n-s$ имеем

                                    $L_2\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{\displaystyle \sum _{s\mathrm{<mo>=</mo>3}}^{n-1}}{\displaystyle \sum _{j\mathrm{<mo>=</mo>3}}^s}{\mathrm{<mo\; stretchy="false">(</mo>}-\mathrm{1<mo\; stretchy="false">)</mo>}}^{n-s-1}\frac{s^{n-j-1}}{\mathrm{<mo\; stretchy="false">(</mo>}n-s-\mathrm{1<mo\; stretchy="false">)</mo><mo>!</mo><mo\; stretchy="false">(</mo>}s-j\mathrm{<mo\; stretchy="false">)</mo><mo>!</mo>}}\mathrm{.}$

Изменим теперь порядок суммирования в двойной сумме:

                                    $L_2\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{\displaystyle \sum _{j\mathrm{<mo>=</mo>3}}^{n-1}}{\displaystyle \sum _{s\mathrm{<mo>=</mo>}j}^{n-1}}{\mathrm{<mo\; stretchy="false">(</mo>}-\mathrm{1<mo\; stretchy="false">)</mo>}}^{n-s-1}\frac{s^{n-j-1}}{\mathrm{<mo\; stretchy="false">(</mo>}n-s-\mathrm{1<mo\; stretchy="false">)</mo><mo>!</mo><mo\; stretchy="false">(</mo>}s-j\mathrm{<mo\; stretchy="false">)</mo><mo>!</mo>}}\mathrm{.}$

После замены индекса суммирования во внутренней сумме $p\mathrm{<mo>=</mo>}s-j$, $s\mathrm{<mo>=</mo>}p+j$ и ввода биномиального коэффициента получим

                     $L_2\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{\displaystyle \sum _{j\mathrm{<mo>=</mo>3}}^{n-1}}\frac{1}{\mathrm{<mo\; stretchy="false">(</mo>}n-j-\mathrm{1<mo\; stretchy="false">)</mo><mo>!</mo>}}{\displaystyle \sum _{p\mathrm{<mo>=</mo>0}}^{n-j-1}}{\mathrm{<mo\; stretchy="false">(</mo>}-\mathrm{1<mo\; stretchy="false">)</mo>}}^{n-j-p-1}\left(\begin{array}{c}n-j-1\\ p\end{array}\right){\mathrm{<mo\; stretchy="false">(</mo>}p+j\mathrm{<mo\; stretchy="false">)</mo>}}^{n-j-1}\mathrm{.}$

Используем известное комбинаторное тождество (см. [7, с. 609, формула 16])

                                          ${\displaystyle \sum _{p\mathrm{<mo>=</mo>0}}^m}{\mathrm{<mo\; stretchy="false">(</mo>}-\mathrm{1<mo\; stretchy="false">)</mo>}}^p\left(\begin{array}{c}m\\ p\end{array}\right){\mathrm{<mo\; stretchy="false">(</mo>}p+a\mathrm{<mo\; stretchy="false">)</mo>}}^m\mathrm{<mo>=</mo><mo\; stretchy="false">(</mo>}-{\mathrm{1<mo\; stretchy="false">)</mo>}}^{m}m\mathrm{<mo>!</mo>.}$

В нашем случае найдем

                         $L_2\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{\displaystyle \sum _{j\mathrm{<mo>=</mo>3}}^{n-1}}\frac{{\mathrm{<mo\; stretchy="false">(</mo>}-\mathrm{1<mo\; stretchy="false">)</mo>}}^{n-j-1}}{\mathrm{<mo\; stretchy="false">(</mo>}n-j-\mathrm{1<mo\; stretchy="false">)</mo><mo>!</mo>}}{\mathrm{<mo\; stretchy="false">(</mo>}-\mathrm{1<mo\; stretchy="false">)</mo>}}^{n-j-1}\mathrm{<mo\; stretchy="false">(</mo>}n-j-\mathrm{1<mo\; stretchy="false">)</mo><mo>!</mo><mo>=</mo>}{\displaystyle \sum _{j\mathrm{<mo>=</mo>3}}^{n-1}}\mathrm{1<mo>=</mo>}n-3.$

Пусть $S_p\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{,}k\mathrm{<mo\; stretchy="false">)</mo>}$ $—$ нецентральные числа Стирлинга второго рода (см. [8]). Для них известна производящая функция и следующие выражения:

              ${\displaystyle \sum _{n\mathrm{<mo>=</mo>0}}^{\infty }}{S}_p\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{,}k\mathrm{<mo\; stretchy="false">)</mo>}\frac{z^n}{n\mathrm{<mo>!</mo>}}\mathrm{<mo>=</mo>}\frac{1}{k\mathrm{<mo>!</mo>}}{e}^{pz}{\mathrm{<mo\; stretchy="false">(</mo>}{e}^z-\mathrm{1<mo\; stretchy="false">)</mo>}}^k\mathrm{,}{S}_p\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{,}k\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\frac{1}{k\mathrm{<mo>!</mo>}}{\displaystyle \sum _{l\mathrm{<mo>=</mo>0}}^k}{\mathrm{<mo\; stretchy="false">(</mo>}-\mathrm{1<mo\; stretchy="false">)</mo>}}^{k-l}\left(\begin{array}{c}k\\ l\end{array}\right){\mathrm{<mo\; stretchy="false">(</mo>}l+p\mathrm{<mo\; stretchy="false">)</mo>}}^n\mathrm{,}$

                                      $S_p\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{,}k\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>0}\text{при}k\mathrm{<mo>></mo>}n\mathrm{,}{S}_p\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{,}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>1.}$

Лемма 1  

                                            $S_p\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{,}n-\mathrm{1<mo\; stretchy="false">)</mo><mo>=</mo>}n\left(p+\frac{1}{2}\mathrm{<mo\; stretchy="false">(</mo>}n-\mathrm{1<mo\; stretchy="false">)</mo>}\right)\mathrm{.}$

Proof. Используем метод коэффициентов (см. [6]):

             $S_p\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{,}n-\mathrm{1<mo\; stretchy="false">)</mo><mo>=</mo>}\frac{n\mathrm{<mo>!</mo>}}{\mathrm{<mo\; stretchy="false">(</mo>}n-\mathrm{1<mo\; stretchy="false">)</mo><mo>!</mo>}}Coe{f}_z{e}^{pz}{\mathrm{<mo\; stretchy="false">(</mo>}{e}^z-\mathrm{1<mo\; stretchy="false">)</mo>}}^{n-1}{z}^{n-1}\mathrm{<mo>=</mo>}nCoe{f}_z{e}^{pz}{\mathrm{<mo\; stretchy="false">(</mo>}\frac{e^z-1}{z}\mathrm{<mo\; stretchy="false">)</mo>}}^{n-1}\frac{1}{z^2}\mathrm{.}$

Пусть

                                                   $f\mathrm{<mo\; stretchy="false">(</mo>}z\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{e}^{pz}{\left(\frac{e^z-1}{z}\right)}^{n-1}\mathrm{.}$

Для вычета функции $F\mathrm{<mo\; stretchy="false">(</mo>}z\mathrm{<mo\; stretchy="false">)</mo>}$ в полюсе $z\mathrm{<mo>=</mo>}a$ порядка $n$ известна формула (см. [5, c. 84])

                                 $Coe{f}_{z}F\mathrm{<mo\; stretchy="false">(</mo>}z\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\frac{1}{\mathrm{<mo\; stretchy="false">(</mo>}n-\mathrm{1<mo\; stretchy="false">)</mo><mo>!</mo>}}\underset{z\to a}{{\displaystyle \lim }}\frac{d^{n-1}}{d{z}^{n-1}}\mathrm{<mo\; stretchy="false">[</mo><mo\; stretchy="false">(</mo>}z-a{\mathrm{<mo\; stretchy="false">)</mo>}}^{n}F\mathrm{<mo\; stretchy="false">(</mo>}z\mathrm{<mo\; stretchy="false">)</mo><mo\; stretchy="false">]</mo>.}$

Функция $f\mathrm{<mo\; stretchy="false">(</mo>}z\mathrm{<mo\; stretchy="false">)</mo>}$ аналитична в нуле; по формуле для вычета в полюсе второго порядка найдем

             $S_p\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{,}n-\mathrm{1<mo\; stretchy="false">)</mo><mo>=</mo>}nCoe{f}_z\frac{f\mathrm{<mo\; stretchy="false">(</mo>}z\mathrm{<mo\; stretchy="false">)</mo>}}{z^2}\mathrm{<mo>=</mo>}n\underset{z\to 0}{{\displaystyle \lim }}{f}^{\prime }\mathrm{<mo\; stretchy="false">(</mo>}z\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}$

                      $\mathrm{<mo>=</mo>}n\underset{z\to 0}{{\displaystyle \lim }}\left[p{e}^{pz}{\mathrm{<mo\; stretchy="false">(</mo>}\frac{e^z-1}{z}\mathrm{<mo\; stretchy="false">)</mo>}}^{n-1}{e}^{pz}\mathrm{<mo\; stretchy="false">(</mo>}n-\mathrm{1<mo\; stretchy="false">)</mo><mo\; stretchy="false">(</mo>}\frac{e^z-1}{z}{\mathrm{<mo\; stretchy="false">)</mo>}}^{n-2}\frac{e^{z}z-\mathrm{<mo\; stretchy="false">(</mo>}{e}^z-\mathrm{1<mo\; stretchy="false">)</mo>}}{z^2}\right]\mathrm{<mo>=</mo>}$

                   $\mathrm{<mo>=</mo>}n\mathrm{<mo\; stretchy="false">[</mo>}p+\mathrm{<mo\; stretchy="false">(</mo>}n-\mathrm{1<mo\; stretchy="false">)</mo>}\underset{z\to 0}{{\displaystyle \lim }}\frac{z+z^2-z-\frac{1}{2}{z}^2+o\mathrm{<mo\; stretchy="false">(</mo>}{z}^2\mathrm{<mo\; stretchy="false">)</mo>}}{z^2}\mathrm{<mo\; stretchy="false">]</mo><mo>=</mo>}n\left(p+\frac{1}{2}\mathrm{<mo\; stretchy="false">(</mo>}n-\mathrm{1<mo\; stretchy="false">)</mo>}\right)\mathrm{.}$

Теорема 3  При $n\ge 5$ верно комбинаторное тождество

                          ${\displaystyle \sum _{i\mathrm{<mo>=</mo>2}}^{n-3}}{\displaystyle \sum _{j\mathrm{<mo>=</mo>3}}^{n-i}}{\mathrm{<mo\; stretchy="false">(</mo>}-\mathrm{1<mo\; stretchy="false">)</mo>}}^i\frac{{\mathrm{<mo\; stretchy="false">(</mo>}n-i\mathrm{<mo\; stretchy="false">)</mo>}}^{n-j-1}}{\mathrm{<mo\; stretchy="false">(</mo>}i-\mathrm{2<mo\; stretchy="false">)</mo><mo>!</mo><mo\; stretchy="false">(</mo>}n-i-j\mathrm{<mo\; stretchy="false">)</mo><mo>!</mo>}}\mathrm{<mo>=</mo>}\frac{1}{6}\mathrm{<mo\; stretchy="false">(</mo>}n-\mathrm{3<mo\; stretchy="false">)</mo><mo\; stretchy="false">(</mo>}n-\mathrm{4<mo\; stretchy="false">)</mo><mo\; stretchy="false">(</mo>2}n-\mathrm{1<mo\; stretchy="false">)</mo>.}$            (3)

Proof. Обозначим левую часть тождества (3) через $L_3\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}$. После замены индекса суммирования во внешней сумме $s\mathrm{<mo>=</mo>}n-i$, $i\mathrm{<mo>=</mo>}n-s$ имеем

                                     $L_3\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{\displaystyle \sum _{s\mathrm{<mo>=</mo>3}}^{n-2}}{\displaystyle \sum _{j\mathrm{<mo>=</mo>3}}^s}{\mathrm{<mo\; stretchy="false">(</mo>}-\mathrm{1<mo\; stretchy="false">)</mo>}}^{n-s}\frac{s^{n-j-1}}{\mathrm{<mo\; stretchy="false">(</mo>}n-s-\mathrm{2<mo\; stretchy="false">)</mo><mo>!</mo><mo\; stretchy="false">(</mo>}s-j\mathrm{<mo\; stretchy="false">)</mo><mo>!</mo>}}\mathrm{.}$

Изменим теперь порядок суммирования в двойной сумме:

                                     $L_3\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{\displaystyle \sum _{j\mathrm{<mo>=</mo>3}}^{n-2}}{\displaystyle \sum _{s\mathrm{<mo>=</mo>}j}^{n-2}}{\mathrm{<mo\; stretchy="false">(</mo>}-\mathrm{1<mo\; stretchy="false">)</mo>}}^{n-s}\frac{s^{n-j-1}}{\mathrm{<mo\; stretchy="false">(</mo>}n-s-\mathrm{2<mo\; stretchy="false">)</mo><mo>!</mo><mo\; stretchy="false">(</mo>}s-j\mathrm{<mo\; stretchy="false">)</mo><mo>!</mo>}}\mathrm{.}$

После замены индекса суммирования во внутренней сумме $p\mathrm{<mo>=</mo>}s-j$, $s\mathrm{<mo>=</mo>}p+j$ получим

             $L_3\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{\displaystyle \sum _{j\mathrm{<mo>=</mo>3}}^{n-2}}\frac{1}{\mathrm{<mo\; stretchy="false">(</mo>}n-j-\mathrm{2<mo\; stretchy="false">)</mo><mo>!</mo>}}{\displaystyle \sum _{p\mathrm{<mo>=</mo>0}}^{n-j-2}}{\mathrm{<mo\; stretchy="false">(</mo>}-\mathrm{1<mo\; stretchy="false">)</mo>}}^{n-j-p-2}\left(\begin{array}{c}n-j-2\\ p\end{array}\right){\mathrm{<mo\; stretchy="false">(</mo>}p+j\mathrm{<mo\; stretchy="false">)</mo>}}^{n-j-1}\mathrm{<mo>=</mo>}$

                    $\mathrm{<mo>=</mo>}{\displaystyle \sum _{j\mathrm{<mo>=</mo>3}}^{n-2}}{S}_j\mathrm{<mo\; stretchy="false">(</mo>}n-j-\mathrm{1,}n-j-\mathrm{2<mo\; stretchy="false">)</mo><mo>=</mo>}{\displaystyle \sum _{j\mathrm{<mo>=</mo>3}}^{n-2}}\mathrm{<mo\; stretchy="false">(</mo>}n-j-\mathrm{1<mo\; stretchy="false">)</mo><mo\; stretchy="false">(</mo>}j+\frac{1}{2}\mathrm{<mo\; stretchy="false">(</mo>}n-j-\mathrm{2<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo><mo>=</mo>}$

                           $\mathrm{<mo>=</mo>}\frac{1}{6}\mathrm{<mo\; stretchy="false">(</mo>2}{n}^3-15n^2+31n-\mathrm{12<mo\; stretchy="false">)</mo><mo>=</mo>}\frac{1}{6}\mathrm{<mo\; stretchy="false">(</mo>}n-\mathrm{3<mo\; stretchy="false">)</mo><mo\; stretchy="false">(</mo>}n-\mathrm{4<mo\; stretchy="false">)</mo><mo\; stretchy="false">(</mo>2}n-\mathrm{1<mo\; stretchy="false">)</mo>.}$

Суммирование последовательности и разложение на множители многочлена выполнено с помощью пакета программ Maple.

В качестве примера наметим ход доказательства тождества (2) с помощью формул для перечисления графов.

Обозначим через $C_k\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{,}m\mathrm{<mo\; stretchy="false">)</mo>}$ число помеченных связных графов с $n$ вершинами, из которых $k$ концевых, и $m$ ребрами, а через $C\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{,}m\mathrm{<mo\; stretchy="false">)</mo>}$ - число помеченных связных графов с $n$ вершинами и $m$ ребрами. Мун (см. [9]) получил формулу

                             $C_k\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{,}m\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{\displaystyle \sum _{i\mathrm{<mo>=</mo>}k}^{n-1}}{\mathrm{<mo\; stretchy="false">(</mo>}-\mathrm{1<mo\; stretchy="false">)</mo>}}^{i-k}\left(\begin{array}{c}i\\ k\end{array}\right)\left(\begin{array}{c}n\\ i\end{array}\right){\mathrm{<mo\; stretchy="false">(</mo>}n-i\mathrm{<mo\; stretchy="false">)</mo>}}^{i}C\mathrm{<mo\; stretchy="false">(</mo>}n-i\mathrm{,}m-i\mathrm{<mo\; stretchy="false">)</mo>.}$               (4)

Унициклический граф - это связный граф с $n$ вершинами и $n$ ребрами. Известна формула для числа $C\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{,}n\mathrm{<mo\; stretchy="false">)</mo>}$ помеченных унициклических графов с $n$ вершинами (см. [10, c. 20]):

                                              $C\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{,}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\frac{1}{2}{\displaystyle \sum _{i\mathrm{<mo>=</mo>3}}^n}\frac{n\mathrm{<mo>!</mo>}}{\mathrm{<mo\; stretchy="false">(</mo>}n-i\mathrm{<mo\; stretchy="false">)</mo><mo>!</mo>}}{n}^{n-i-1}\mathrm{.}$                                 (5)

Выражение для числа $C_k\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{,}n\mathrm{<mo\; stretchy="false">)</mo>}$ помеченных унициклических графов с $n$ вершинами, из которых $k$ концевых, найдено в [1]:

                                    $C_k\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{,}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\frac{1}{2}\frac{n\mathrm{<mo>!</mo>}}{k\mathrm{<mo>!</mo>}}{\displaystyle \sum _{p\mathrm{<mo>=</mo>3}}^{n-k}}{S}_p\mathrm{<mo\; stretchy="false">(</mo>}n-p-\mathrm{1,}n-p-k\mathrm{<mo\; stretchy="false">)</mo>.}$

Учитывая, что $S_p\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{,}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>1}$, имеем

                                                   $C_1\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{,}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\frac{1}{2}n\mathrm{<mo>!</mo><mo\; stretchy="false">(</mo>}n-\mathrm{3<mo\; stretchy="false">)</mo><mo>;</mo>}$                                     (6)

подставляя (5) и (6) в формулу Муна (4) при $k\mathrm{<mo>=</mo>1}$, $m\mathrm{<mo>=</mo>}n$, получим тождество (2).

Отметим, что аналогичным путем можно получить еще ряд тождеств типа (1)$–$(3), но степень многочлена от $n$ в правой части тождества быстро растет и при $k\mathrm{<mo>=</mo>3}$ уже равна $5$.