Замощения ромбиками и их случайные перестройки, занятие 3

Замощение — это представление одной фигуры в виде объдинения фигур из данного (обычно конечного) набора, без пробелов и перекрытий. Задачи о замощениях плоскости и других фигур часто очень нетривиальны, и возникают во многих областях математики. Мы будем заниматься замощениями многоугольников, нарисованных на треугольной решетке, ромбами трех типов. Каждый ромб в нашем наборе — объединение двух правильных треугольников, соседних по стороне, например как на картинке ниже.
Первым делом мы подсчитаем, сколькими способами можно замостить некоторые многоугольники, в том числе, шестиугольник (кстати, для общего многоугольника формула неизвестна). Число замощений шестиугольника дается красивой формулой МакМагона, которой больше ста лет. (В Кембриджском Университете Перси МакМагон, по некоторым источникам, соревновался с Рамануджаном в подсчете числа разбиений — МакМагон приводил точные значения, а Рамануджан пользовался асимптотической формулой.)
Подсчет замощений естественно обобщить, вводя дополнительные параметры. Производящие функции замощений некоторых многоугольников — это замечательные симметрические многочлены Шура, встречающиеся почти во всех областях математики.
Замощений данного достаточно большого многоугольника очень много (порядка экспоненты от площади). В конце 20 века, с появлением компьютеров, математики смогли увидеть, как выглядит замощение, выбранное совершенно случайно из этого гигантского набора.
Эти примеры вызвали новый интерес к замощениям, уже с вероятностной стороны, что привело к новым красивым результатам. Как на практике получить картинку случайного замощения? Нельзя просто так выписать все возможные замощения и выбрать одно из них — на это не хватит памяти ни у одного компьютера. Оказывается, решение лежит в области «случайных перестроек» замощений — начинаем с одного, и случайно его меняем. Если это делать правильно, то после большого числа шагов получим искомую случайную картинку.
1. Замощения шестиугольника ромбиками трех типов. Различные описания замощений. Элементарный подсчет в частных случаях. Формула МакМагона и ее q-версия.
2. Уточненный подсчет замощений со многими параметрами. Рекуррентное соотношение. Многочлены Шура.
3. Поведение больших случайных замощений.
4. Марковские цепи и обратимость.
5. Случайные перестройки замощений.