С.Н. Перепечко

Количество совершенных паросочетаний в одном семействе ленточных графов

Рассматривается задача подсчёта совершенных паросочетаний в двухпараметрическом семействе графов, полученных из прямоугольных решёток путём наложения периодических граничных условий по одной из сторон решётки. Построен набор линейных рекуррентных соотношений для числа паросочетаний при фиксированном значении одного из параметров. Вычислены оценки сверху на порядки этих соотношений. Изучена асимптотика числа паросочетаний как при фиксированном значении одного из параметров, так и для случая, когда оба параметра велики и равны друг другу.

КЛЮЧЕВЫЕ СЛОВА: совершенные паросочетания, задача о димерах, производящие функции, рекуррентные соотношения