Two combinatorial identities related to enumeration of graphs

Abstract

From the explicit formula for the number of labeled, series-parallel, 2-connected graphs with a given number of vertices obtained by the author, two combinatorial identities are derived. Also, proofs of these identities independent of the enumeration of graphs are given.

Full Text

Определение 1 (см.[4 с. 118]) Цикломатическим числом связного графа называется увеличенная на единицу разность между числом ребер графа и числом его вершин.

Определение 2 $k$ —Циклический граф $—$ это граф с цикломатическим числом, равным $k$

Определение 3 (см.[7]) Граф называется последовательно—параллельным, если он не содержит подразбиения полного графа $K_4$.

Последовательно—параллельные графы применяются при поcтроении надежных коммуникационных сетей (см. [9]).

В [3] получена явная формула для числа помеченных последовательно—параллельных $2$ —связных графов с заданным числом вершин. В данной заметке из этой формулы выведены два комбинаторных тождества, a также приведено не зависящее от перечисления графов доказательство полученных тождеств.

Теорема 1. Верны следующие комбинаторные тождества:

$\sum _{i=1}^n\sum _{j=n+1}^{n+i}{\left(-1\right)}^j\frac{{\left(j+1\right)}^{i-1}}{\left(i-1\right)}\left(\begin{array}{c}n\\ i\end{array}\right)\left(\begin{array}{c}n+i\\ j\end{array}\right)\left(\begin{array}{c}j\\ n+1\end{array}\right)=n\mathrm{,}n\ge 3$,  (1)

${\displaystyle \sum _{i\mathrm{<mo>=</mo>2}}^n}{\displaystyle \sum _{j\mathrm{<mo>=</mo>}n+2}^{n+i}}{\mathrm{<mo\; stretchy="false">(</mo>}-\mathrm{1<mo\; stretchy="false">)</mo>}}^j\frac{{\mathrm{<mo\; stretchy="false">(</mo>}j+\mathrm{1<mo\; stretchy="false">)</mo>}}^{i-1}}{\mathrm{<mo\; stretchy="false">(</mo>}i-\mathrm{1<mo\; stretchy="false">)</mo><mo>!</mo>}}\left(\begin{array}{c}n\\ i\end{array}\right)\left(\begin{array}{c}n+i\\ j\end{array}\right)\left(\begin{array}{c}j\\ n+2\end{array}\right)\mathrm{<mo>=</mo>}\frac{n\mathrm{<mo\; stretchy="false">(</mo>}n-\mathrm{1<mo\; stretchy="false">)</mo><mo\; stretchy="false">(</mo>}n+\mathrm{3<mo\; stretchy="false">)</mo><mo\; stretchy="false">(</mo>}n+\mathrm{4<mo\; stretchy="false">)</mo>}}{12}\mathrm{,}n\ge 4.$  (2)

Доказательство. В [3] для числа $B_k\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}$ помеченных последовательно—параллельных $k$ —циклических $2$ —связных графов с $n$ вершинами при $n\ge k+2$ получено выражение

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

Так как полный граф $K_4$ является трициклическим, то все унициклические и бициклические $2$ —связные графы не содержат в качестве подграфа подразбиения $K_4$ и потому являются последовательно—параллельными графами.

Унициклический $2$ —связный граф $—$ это простой цикл с помеченными вершинами. Число таких циклов известно (см. [8, с. 20]); следовательно, $B_1\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo><mo\; stretchy="false">(</mo>}n-\mathrm{1<mo\; stretchy="false">)</mo><mo>!</mo><mo>/</mo>2}$, и при $k\mathrm{<mo>=</mo>1}$ из (3) получим

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

Э. Райт доказал (см. [10]), что число помеченных бициклических блоков с $n$ вершинами равно $\mathrm{<mo\; stretchy="false">(</mo>}n-\mathrm{3<mo\; stretchy="false">)</mo><mo\; stretchy="false">(</mo>}n+\mathrm{2<mo\; stretchy="false">)</mo><mo>/</mo>24}$; при $k\mathrm{<mo>=</mo>2}$ из (3) получим

${\displaystyle \sum _{i\mathrm{<mo>=</mo>2}}^{n-2}}{\displaystyle \sum _{j\mathrm{<mo>=</mo>}n}^{n+i-2}}{\mathrm{<mo\; stretchy="false">(</mo>}-\mathrm{1<mo\; stretchy="false">)</mo>}}^j\frac{{\mathrm{<mo\; stretchy="false">(</mo>}j+\mathrm{1<mo\; stretchy="false">)</mo>}}^{i-2}}{i\mathrm{<mo>!</mo>}}\left(\begin{array}{c}n-3\\ i-1\end{array}\right)\left(\begin{array}{c}n+i-2\\ j\end{array}\right)\left(\begin{array}{c}j+1\\ n+1\end{array}\right)\mathrm{<mo>=</mo>}\frac{\mathrm{<mo\; stretchy="false">(</mo>}n-\mathrm{3<mo\; stretchy="false">)</mo><mo\; stretchy="false">(</mo>}n+\mathrm{2<mo\; stretchy="false">)</mo>}}{12}\mathrm{,}n\ge 4.$  (5)

Преобразуем тождества (4) и (5). Заменим $n$ на $n+2$; поскольку

$\left(\begin{array}{c}n-1\\ i-1\end{array}\right)\mathrm{<mo>=</mo>}\frac{i}{n}\left(\begin{array}{c}n\\ i\end{array}\right)\mathrm{,}\left(\begin{array}{c}j+1\\ n+2\end{array}\right)\mathrm{<mo>=</mo>}\frac{j+1}{n+2}\left(\begin{array}{c}j\\ n+1\end{array}\right)\mathrm{,}$

тождество (4) эквивалентно тождеству (1), а тождество (5) эквивалентно тождеству (2).

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

Обозначим левую часть тождества (1) через $L\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}$. Поскольку $\left(\begin{array}{c}n\\ k\end{array}\right)\mathrm{<mo>=</mo>0}$ при $0\le n\mathrm{<mo><</mo>}k$, то нижний индекс во внутренней сумме можно заменить на $0$. С помощью метода коэффициентов (см. [5, с. 8]) имеем

$\frac{{\mathrm{<mo\; stretchy="false">(</mo>}j+\mathrm{1<mo\; stretchy="false">)</mo>}}^{i-1}}{\mathrm{<mo\; stretchy="false">(</mo>}i-\mathrm{1<mo\; stretchy="false">)</mo><mo>!</mo>}}\mathrm{<mo>=</mo>}Coe{f}_z{e}^{\mathrm{<mo\; stretchy="false">(</mo>}j+\mathrm{1<mo\; stretchy="false">)</mo>}z}{z}^{-i}\mathrm{,}$

$L\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{\displaystyle \sum _{i\mathrm{<mo>=</mo>1}}^n}\left(\begin{array}{c}n\\ i\end{array}\right)Coe{f}_z{e}^z{z}^{-i}{\displaystyle \sum _{j\mathrm{<mo>=</mo>0}}^{n+i}}{\mathrm{<mo\; stretchy="false">(</mo>}-\mathrm{1<mo\; stretchy="false">)</mo>}}^j{e}^{jz}\left(\begin{array}{c}n+i\\ j\end{array}\right)\left(\begin{array}{c}j\\ n+1\end{array}\right)\mathrm{.}$

В силу комбинаторного тождества

${\displaystyle \sum _{j\mathrm{<mo>=</mo>0}}^m}\left(\begin{array}{c}m\\ j\end{array}\right)\left(\begin{array}{c}j\\ l\end{array}\right)x^j\mathrm{<mo>=</mo>}\left(\begin{array}{c}m\\ l\end{array}\right)x^l{\mathrm{<mo\; stretchy="false">(</mo>1}+x\mathrm{<mo\; stretchy="false">)</mo>}}^{m-l}$ , (6)

(см. [6, с. 625]) имеем

$L\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{\displaystyle \sum _{i\mathrm{<mo>=</mo>1}}^n}\left(\begin{array}{c}n\\ i\end{array}\right)Coe{f}_z{e}^z{z}^{-i}\left(\begin{array}{c}n+i\\ n+1\end{array}\right){\mathrm{<mo\; stretchy="false">(</mo>}-\mathrm{1<mo\; stretchy="false">)</mo>}}^{n+1}{e}^{\mathrm{<mo\; stretchy="false">(</mo>}n+\mathrm{1<mo\; stretchy="false">)</mo>}z}{\mathrm{<mo\; stretchy="false">(</mo>1}-z\mathrm{<mo\; stretchy="false">)</mo>}}^{i-1}\mathrm{<mo>=</mo>}$

$\mathrm{<mo>=</mo>}{\displaystyle \sum _{i\mathrm{<mo>=</mo>1}}^n}\left(\begin{array}{c}n\\ i\end{array}\right)\left(\begin{array}{c}n+i\\ n+1\end{array}\right){\mathrm{<mo\; stretchy="false">(</mo>}-\mathrm{1<mo\; stretchy="false">)</mo>}}^{n-1}Coe{f}_z\frac{1}{z}{e}^{\mathrm{<mo\; stretchy="false">(</mo>}n+\mathrm{2<mo\; stretchy="false">)</mo>}z}{\left(\frac{1-e^z}{z}\right)}^{i-1}\mathrm{.}$

Введем обозначение

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

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

$Coe{f}_z\frac{f\mathrm{<mo\; stretchy="false">(</mo>}z\mathrm{<mo\; stretchy="false">)</mo>}}{z}\mathrm{<mo>=</mo>}\underset{z\to 0}{{\displaystyle \lim }}f\mathrm{<mo\; stretchy="false">(</mo>}z\mathrm{<mo\; stretchy="false">)</mo>,}L\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{\displaystyle \sum _{i\mathrm{<mo>=</mo>1}}^n}\left(\begin{array}{c}n\\ i\end{array}\right)\left(\begin{array}{c}n+i\\ n+1\end{array}\right){\mathrm{<mo\; stretchy="false">(</mo>}-\mathrm{1<mo\; stretchy="false">)</mo>}}^{n-1}{\mathrm{<mo\; stretchy="false">(</mo>}-\mathrm{1<mo\; stretchy="false">)</mo>}}^{i-1}\mathrm{.}$

Используем теперь комбинаторное тождество

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

(см. [8, с. 619]). Так как в $L\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}$ под знаком суммы второй биномиальный коэффициент равен нулю при $i\mathrm{<mo>=</mo>0}$, то окончательно получим

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

Для тождества (2) опять с помощью метода коэффициентов имеем

$L\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{\displaystyle \sum _{i\mathrm{<mo>=</mo>2}}^n}\left(\begin{array}{c}n\\ i\end{array}\right)Coe{f}_z{e}^z{z}^{-i}{\displaystyle \sum _{j\mathrm{<mo>=</mo>0}}^{n+i}}{\mathrm{<mo\; stretchy="false">(</mo>}-\mathrm{1<mo\; stretchy="false">)</mo>}}^j{e}^{jz}\left(\begin{array}{c}n+i\\ j\end{array}\right)\left(\begin{array}{c}j\\ n+2\end{array}\right)\mathrm{.}$

В силу комбинаторного тождества (6) найдем

$L\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{\displaystyle \sum _{i\mathrm{<mo>=</mo>2}}^n}\left(\begin{array}{c}n\\ i\end{array}\right)Coe{f}_z{e}^z{z}^{-i}\left(\begin{array}{c}n+i\\ n+2\end{array}\right){\mathrm{<mo\; stretchy="false">(</mo>}-\mathrm{1<mo\; stretchy="false">)</mo>}}^n{e}^{\mathrm{<mo\; stretchy="false">(</mo>}n+\mathrm{2<mo\; stretchy="false">)</mo>}z}{\mathrm{<mo\; stretchy="false">(</mo>1}-e^z\mathrm{<mo\; stretchy="false">)</mo>}}^{i-2}\mathrm{<mo>=</mo>}$

$\mathrm{<mo>=</mo>}{\displaystyle \sum _{i\mathrm{<mo>=</mo>2}}^n}\left(\begin{array}{c}n\\ i\end{array}\right)\left(\begin{array}{c}n+i\\ n+2\end{array}\right){\mathrm{<mo\; stretchy="false">(</mo>}-\mathrm{1<mo\; stretchy="false">)</mo>}}^{n}Coe{f}_z\frac{1}{z^2}{e}^{\mathrm{<mo\; stretchy="false">(</mo>}n+\mathrm{3<mo\; stretchy="false">)</mo>}z}{\left(\frac{1-e^z}{z}\right)}^{i-2}\mathrm{.}$

Введем обозначение

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

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

$Coe{f}_z\frac{fz}{z^2}\underset{\mathrm{z}\to 0}{\lim }{f}^{\text{'}}zn+e^{n+z}{\left(\frac{1-e^z}{z}\right)}^{i-2}+$

$+\mathrm{<mo\; stretchy="false">(</mo>}i-\mathrm{2<mo\; stretchy="false">)</mo>}{e}^{\mathrm{<mo\; stretchy="false">(</mo>}n+\mathrm{3<mo\; stretchy="false">)</mo>}z}{\left(\frac{1-e^z}{z}\right)}^{i-3}\frac{-z{e}^z+e^z-1}{z^2}\mathrm{<mo>=</mo><mo\; stretchy="false">(</mo>}-{\mathrm{1<mo\; stretchy="false">)</mo>}}^i\left(n+3+\frac{i-2}{2}\right)\mathrm{,}$

$L\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{\displaystyle \sum _{i\mathrm{<mo>=</mo>2}}^n}\left(\begin{array}{c}n\\ i\end{array}\right)\left(\begin{array}{c}n+i\\ n+2\end{array}\right){\mathrm{<mo\; stretchy="false">(</mo>}-\mathrm{1<mo\; stretchy="false">)</mo>}}^{n+i}\left(n+2+\frac{i}{2}\right)\mathrm{<mo>=</mo>}{L}_1\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}+L_2\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>.}$

Еще раз применим комбинаторное тождество (7):

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

Так как $i\left(\begin{array}{c}n\\ i\end{array}\right)\mathrm{<mo>=</mo>}n\left(\begin{array}{c}n-1\\ i-1\end{array}\right)$, в силу тождества (7) имеем

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

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

Окончательно получим

$L\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo><mo\; stretchy="false">(</mo>}n+\mathrm{2<mo\; stretchy="false">)</mo>}\left(\begin{array}{c}n\\ 2\end{array}\right)+\frac{n}{2}\left(\begin{array}{c}n+1\\ 3\end{array}\right)\mathrm{<mo>=</mo>}\frac{1}{12}n\mathrm{<mo\; stretchy="false">(</mo>}n-\mathrm{1<mo\; stretchy="false">)</mo><mo\; stretchy="false">(</mo>}n+\mathrm{3<mo\; stretchy="false">)</mo><mo\; stretchy="false">(</mo>}n+\mathrm{4<mo\; stretchy="false">)</mo>.}$

Отметим, что для чисел помеченных последовательно—параллельных трициклических и тетрациклических блоков известны выражения в виде многочленов от числа вершин графа (см. [1] и [2], соответственно). Поэтому из формулы (3) при $k\mathrm{<mo>=</mo>3}$ и $k\mathrm{<mo>=</mo>4}$ можно получить еще два тождества типа (1). Однако степень многочленов от $n$ в правой части тождеств быстро растет; при $k\mathrm{<mo>=</mo>4}$ она равна $9$.

Автор благодарит профессора В. К. Леонтьева за обсуждение работы.