Миникурс (онлайн) Е.Ю. Смирнова «Паросочетания на графах, конденсация и ацтекский бриллиант». Part 1

Аннотация: Всякий, кто ходил на математический кружок, знает, что если из доски 8х8 вырезать два противоположных угла, то оставшуюся фигуру нельзя замостить в один слой доминошками 2х1. Более интересно изучать фигуры, которые замостить можно; про них можно выяснять, сколькими способами это можно сделать (подумайте, например, сколько существует способов замостить прямоугольник 2 x n). Мы выясним, сколькими способами можно замостить доминошками «ацтекский бриллиант», т. е. ромб на клетчатой бумаге.

У этой задачи есть множество решений; мы обсудим два из них. Первое основано на подсчете так называемых статистических сумм для паросочетаний на графах (или, как говорят физики, димерных конфигураций). Второе решение использует прием под названием “конденсация Доджсона”, названный так в честь английского математика XIX века, более известного как писатель Льюис Кэрролл. Если останется время, мы посмотрим, какие еще комбинаторные задачи можно решать этими же двумя методами.

Никаких предварительных знаний, выходящих за рамки школьной программы, не требуется.

Скачать видео