То же самое можно сделать и для разбиений (опять таки, областей без дырок) на квадратной решётке — а в качестве элементарной перестройки выступает переразбиение квадрата 2x2.

Так вот, возвращаясь к ацтекскому бриллианту. Вообще, картинки, которые я показывал, нарисованы с использованием специфики именно ацтекского бриллианта. А именно, одно из доказательств теоремы о числе разбиений позволяет ещё и по честно-равномерному разбиению АБ порядка (n-1), дополнительно несколько раз подбросив монетку, получить честно-равномерное разбиение АБ порядка n. И завязано это как раз на функцию высоты (которая достраивает картинку до трёхмерной) — рассматриваемую в одном случае в чёрных, а в другом в белых вершинах. Но в эту технику я не пойду, именно потому, что она завязана на конкретику АБ.

Но можно себе представить другой способ порождать случайные разбиения — с помощью случайного блуждания.

А именно: рассмотрим граф, вершинами которого являются _все_ разбиения АБ, а рёбра соединяют разбиения, отличающиеся на элементарную перестройку.

Этот граф, конечно, объект чисто абстрактный: для порядка n=100 у него 2^{5050} вершин, что немного многовато.

Зато рёбер из каждой вершины выходит не так много — не больше 2n^2=20.000, что вполне компьютерно-реалистично.

И можно рассмотреть блуждание по такому графу — приходим в вершину, уходим по случайно выбранному ребру, оттуда опять по случайно выбранному ребру, и так далее.

Так вот — если так "побродить" достаточно долго, то получается (почти) равновероятное распределение на том, куда мы в принципе можем прийти. И это и есть один из способов генерации случайного разбиения. Но тут нужно быть аккуратным и в том, как генерировать, и в том, когда останавливаться (а ещё есть красивые слова "coupling from the past", которые позволяют гарантировать, что получаемое разбиение совсем честно случайно).

И это, кажется, хороший момент, чтобы сделать паузу в рассказе...

Добрался до Лиона, и теперь могу показать кусочки их математической фрески в лучшем качестве:

Воздушный шар с расслоением Хопфа —

Солнце, универсально накрывающее сферу без трёх точек —

Дикий узел —

Кстати — вот одно из совершенно потрясающих рассуждений в комплексном анализе (увы — для тех, кто его уже немного знает), теорема Пикара. Целая (голоморфная на C) функция, не принимающая хотя бы два значения, константа.
Потому что — универсальная накрывающая над C без двух точек это диск. Непрерывное отображение можно поднять до отображения универсальных накрывающих. А универсальная накрывающая над C без двух точек (=над сферой без трёх) это диск.
И если мы начали с целой функции, бьющей в C без двух точек — то получаем отображение из C в диск, то есть ограниченную целую функцию. А ограниченная целая функция — константа.

Часы в чайной комнате UMPA тоже соответствующие —

Но давайте я продолжу этот рассказ. Итак, пусть у нас есть абы какой связный граф G. Рассмотрим вот такой процесс на нём: мы начинаем из какой-то вершины, и каждый раз переходим в случайно выбранного соседа этой вершины.

Вообще, такие процессы называются _цепями Маркова_. "Такие" — это значит, что есть множество состояний, для каждого состояния задано, с какой вероятностью в какое состояние мы переходим, причём эта вероятность зависит только от того, где мы сейчас, но не от того, где мы были раньше. Ну и — чтобы процесс был задан полностью, нужно ещё задать начальное распределение (где и с какой вероятностью мы начинаем; например, можно начать просто в заданной точке).