Но давайте вернёмся к собственно подсчёту разбиений. Ответ про их количество оказывается тоже удивительным (и вдвойне — что получается посчитать их точно, а не только найти асимптотику).
Теорема (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...
Собственно, трём взглядам на разбиения АБ и трём доказательствам этой теоремы и посвящена брошюра Е. Смирнова, что я упоминал — так что тут я дальше не пойду. Правда, покажу (без объяснения) одну из картинок — про модель "квадратного льда", с которой ацтекский бриллиант оказывается связанным:
Зато — нам этого ответа уже хватит, чтобы понять, что _угловые_ доминошки действительно должны быть ориентированы так, как предсказывает теорема о полярном круге:
Действительно, пусть мы закрыли угловую клетку горизонтальной доминошкой:
Тогда у клетки B остался только один сосед — так что и её придётся закрывать горизонтальной доминошкой:
И в результате остаётся неразбитым опять АБ — но порядка (n-1). А у него разбиений (по той же теореме) 2^{n(n-1)/2}.
То есть _доля_ тех разбиений, где угловая доминошка ориентирована "не как надо", равна
2^{n(n-1)/2} / 2^{n(n+1)/2} = 1/2^n
То есть _доля_ тех разбиений, где угловая доминошка ориентирована "не как надо", равна
2^{n(n-1)/2} / 2^{n(n+1)/2} = 1/2^n
(потому что разница двух треугольных чисел в показателе как раз равна n).
Понятно, что начиная с n=10, мы событий столь малой вероятности практически не увидим.
Ну и это подсказывает общую точку зрения: мы видим такую картинку, как выше, не потому, что что-либо иное совсем запрещено — а потому, что их просто сильно меньше, чем всех.
Точно так же, как выкинуть 10 орлов из 100 подбрасываний не запрещено — но число способов это сделать сильно-сильно меньше, чем общее число вариантов.
Точно так же, как выкинуть 10 орлов из 100 подбрасываний не запрещено — но число способов это сделать сильно-сильно меньше, чем общее число вариантов.
И кстати, это же подсказывает, что "наивные" методы построения случайного разбиения не пройдут: нельзя, например, взять какую-нибудь свободную клетку, подкинуть монетку, чтобы решить, куда пойдёт из неё доминошка, и перейти к следующей свободной клетке. Потому что при _равномерном_ выборе разбиения шанс, что доминошка в левом углу вертикальная, должен быть близок к 1. А вовсе не, скажем, 1/2.