И вот он, красивый эффект — "теорема о полярном круге": снаружи от вписанной окружности все доминошки оказываются "заморожены".
Её доказали Jockush, Propp и Shor; см. — https://arxiv.org/abs/math/9801068
Её доказали Jockush, Propp и Shor; см. — https://arxiv.org/abs/math/9801068
arXiv.org
Random Domino Tilings and the Arctic Circle Theorem
In this article we study domino tilings of a family of finite regions called Aztec diamonds. Every such tiling determines a partition of the Aztec diamond into five sub-regions; in the four outer...
Кстати, у них в работе есть и картинка без раскраски:
Возвращаясь к ацтекскому бриллианту — одну красивую картинку мы увидели, но вот что за нею стоит?
Оказывается, что стоит довольно много.
Оказывается, что стоит довольно много.
Начать с того, что я продекларировал, что разбиение выбрано равновероятно из всех возможностей — но совершенно не сказал, как это сделано. И даже не сказал, сколько их вообще.
К равновероятному выбору мы ещё вернёмся — а пока посмотрим, сколько их должно быть.
Во-первых, сделаем оценку сверху: площадь АБ порядка n равна 2n(n+1); половина её это чёрные клетки, так что их n(n+1). Собственно, если нарисовать первые сколько-то АБ, то это видно "на глаз":
(picture credit: картинка из статьи в Images de Maths, которую я упоминал выше)
Так вот — разбиение кодируется набором направлений доминошек, закрывающих эти клетки. Значит, всего разбиений не больше, чем
4^{n(n+1)}.
Так вот — разбиение кодируется набором направлений доминошек, закрывающих эти клетки. Значит, всего разбиений не больше, чем
4^{n(n+1)}.
Во-вторых, сделаем теперь оценку снизу. В ацтекский бриллиант порядка n=2m-1 (и n=2m) можно вписать честный квадрат размера 2mx2m, "срезав уголки".
Уголки можно разрезать на доминошки просто параллельно линии отреза — а квадрат размера 2mx2m разрезать на m^2 квадратов размера 2x2.
Уголки можно разрезать на доминошки просто параллельно линии отреза — а квадрат размера 2mx2m разрезать на m^2 квадратов размера 2x2.
Каждый из этих квадратов разрезается на доминошки двумя способами — и вот мы получили оценку снизу как 2^{m^2}, то есть примерно как 2^{n^2/4}.
И оценка сверху, и оценка снизу экспоненциальные по площади АБ. То есть естественно ожидать, что асимптотика будет exp(c n^2), где c — некоторая, пока неизвестная нам, константа.
Вообще — такие ситуации, когда число вариантов экспоненциально по числу задействованных объектов (квадратиков или доминошек, в данном случае), встречаются исключительно часто. А множитель в экспоненте обычно тогда называют энтропией.
Игрушечный пример — тоже разбиения на доминошки, но прямоугольника 2xn. Упражнение: их количество это (n+1)-е число Фибоначчи.
Учитывая то, как растут числа Фибоначчи — энтропией будет логарифм золотого сечения.
Учитывая то, как растут числа Фибоначчи — энтропией будет логарифм золотого сечения.
Но аналогия тут идёт сильно дальше — и соседняя огромная область это статистическая физика. Где будут, например, возможные конфигурации атомов — в количестве, экспоненциальном по числу задействованных атомов.
Непрерывное математическое образование
http://book.etudes.ru/
Кстати, в качестве рекламы — (IMHO, очень хороший) текст Окунькова как раз о статистической физике: http://book.etudes.ru/toc/patternhappen/
book.etudes.ru
Как случается закономерность / Статьи — Математическая составляющая
Девочка плачет: шарик улетел.Её утешают, а шарик летит…Булат Окуджава Наполненные гелием воздушные шары в моём детстве были редкостью и завораживали нас своим стремлением ввысь. Теперь, конечно, ими никого не удивишь, но всё равно грустно смотреть вслед...
Но давайте вернёмся к собственно подсчёту разбиений. Ответ про их количество оказывается тоже удивительным (и вдвойне — что получается посчитать их точно, а не только найти асимптотику).
Теорема (N. Elkies, G. Kuperberg, M. Larsen, J. Propp): Количество разбиений АБ порядка n равно 2^{n(n+1)/2}.
См.: https://arxiv.org/abs/math/9201305
См.: https://arxiv.org/abs/math/9201305
arXiv.org
Alternating sign matrices and domino tilings
We introduce a family of planar regions, called Aztec diamonds, and study the ways in which these regions can be tiled by dominoes. Our main result is a generating function that not only gives the...