"Записки научных семинаров ПОМИ"
Том 421, стр. 5-18
Разбиения на домино и определители
В. Аксенов, К. Кохась
НИУ ИТМО,
Кронверкский пр. 49,
197101 С.-Петербург, Россия
С.-Петербургский
государственный университет,
Университетский пр. 28, Старый Петергоф,
198504 С.-Петербург, Россия
kpk@arbital.ru
- Аннотация: Для произвольной ограниченной односвязной клетчатой фигуры $F$ на
плоскости рассмотрим двойственный граф (вершины соответствуют клеткам,
рёбра -- соседним по стороне клеткам). В статье изучаются связи между
определителем матрицы смежности этого графа и разбиениями фигуры $F$
на домино. В частности, мы показываем, что если все разбиения фигуры
$F$ на домино разбиваются на пары, в которых количество вертикальных
домино отличается на 1, то $\det A_F =0$. Если же все разбиения кроме
одного разбиваются на такие пары, то $\det A_F=(-1)^s$, где $s$ --
половина площади фигуры.
Библ. -- 7 назв.
- Ключевые слова: разбиения на домино, пфаффиан, комбинаторная линейная алгебра
[domino tilings, pfaffian, combinatorial linear algebra]
Полный текст(.pdf)