Замощения доминошками. Семинар 1

Нас будет интересовать следующая задача: сколькими способами данную фигуру на клетчатой бумаге можно разрезать на прямоугольники $2\times1$ — или, что то же самое, замостить доминошками без наложений? Более общим образом, можно не ограничиваться фигурами на клетчатой бумаге, а вместо этого рассмотреть произвольный двудольный граф и посчитать для него число совершенных паросочетаний, т.е. количество способов разбить вершины на пары, соединенные ребром.
Мы рассмотрим несколько разных подходов к этой задаче. Мы начнем с метода конденсации Доджсона, который во многих случаях позволяет производить подсчёты индуктивно; с его помощью мы разберемся с ромбом на клетчатой бумаге (также известным как ацтекский бриллиант) и выясним, сколькими способами можно разбить равноугольный шестиугольник на единичные ромбы с углами в 60 и 120 градусов (lozenge tilings) — последнее оказывается эквивалентной подсчету числа плоских разбиений, они же — трехмерные диаграммы Юнга.
Далее мы перейдем к случаю произвольного двудольного планарного графа, обсудим алгоритм Фишера-Кастелейна-Темперли, позволяющий вычислить количество совершенных паросочетаний за полиномиальное время, и выразим их число как квадратный корень из определителя некоторой матрицы, построенной по графу. В качестве приложения этих результатов мы получим формулу Кастелейна о числе замощений прямоугольника $n\times m$: оно оказывается равным
$$ \prod_{0\leq i\leq m+1}\prod_{0\leq j\leq n+1}\left(\cos^2\frac{\pi i}{m+1}+\cos^2\frac{\pi j}{n+1}\right)^{1/4}. $$
Если позволят время и энтузиазм участников, в конце курса можно будет поговорить про асимптотические вопросы — как выглядят «типичные» замощения тех или иных фигур.
Первая половина курса планируется элементарной и доступной для школьников. Для понимания второй половины нужно владеть основами линейной алгебры: знать, что такое определитель, собственные векторы и собственные значения.