Математические байки

Тут уже можно и сделать аллюзию на диаграммы Юнга (такие же кубики в углу, но двумерной комнаты, они же число способов разбить число n в сумму натуральных слагаемых без учёта порядка) — и вспомнить формулу МакМагона для подсчёта числа таких "заполнений кубиками" в комнате размера axbxc (мне, опять-таки, вспоминается — другая — брошюра Е. Смирнова, https://www.mccme.ru/free-books/dubna/smirnov-asm.pdf , см. лекцию 3 ) — ну, в общем, я же уже говорил про годовой курс?

— и картинка становится "кубиками" в трёхмерном пространстве (собранными в углу комнаты).

Достаточно раскрасить ромбики в разбиении (а они тут будут трёх возможных направлений, так что красим в три цвета) —

Пусть мы разбиваем область на треугольной решётке — скажем, просто большой правильный шестиугольник — на "доминошки"-ромбики из двух соседних треугольников:

Так как же можно нарисовать случайное разбиение? (А картинки выше действительно были выбраны равновероятно среди всех — ну, точнее, равновероятно в пределах точности компьютерного датчика случайных чисел.) Оказывается, для АБ есть сразу несколько способов это сделать — но прежде, чем их описывать, мне хочется дополнительно мотивировать разбиения на доминошки как объекта изучения. Тут, на самом деле, можно много чего сказать (примерно на годовой спецкурс — легко), но простейшая мотивация — это переход с квадратной решётки на треугольную.

Нет, конечно, я не то, чтобы вру, но сгущаю краски — можно и считать, и генерировать "бегущим профилем", и это сразу нас вернёт в разумные количества. Но до n=200 даже так, "грубой силой", не дотянуться.

Более того, это же подсказывает, что нет у нас шансов и выбрать случайное разбиение, сначала перечислив их все: уже для n=10, их количество это 2^{n(n+1)/2} = 2^55, и получается совсем не тот объём информации, который можно хранить на компьютере (учитывая, что каждый ещё и задавать надо, и это не один бит — получается порядок эксабайт(!))...

И кстати, это же подсказывает, что "наивные" методы построения случайного разбиения не пройдут: нельзя, например, взять какую-нибудь свободную клетку, подкинуть монетку, чтобы решить, куда пойдёт из неё доминошка, и перейти к следующей свободной клетке. Потому что при _равномерном_ выборе разбиения шанс, что доминошка в левом углу вертикальная, должен быть близок к 1. А вовсе не, скажем, 1/2.

Ну и это подсказывает общую точку зрения: мы видим такую картинку, как выше, не потому, что что-либо иное совсем запрещено — а потому, что их просто сильно меньше, чем всех. Точно так же, как выкинуть 10 орлов из 100 подбрасываний не запрещено — но число способов это сделать сильно-сильно меньше, чем общее число вариантов.

Понятно, что начиная с n=10, мы событий столь малой вероятности практически не увидим.

(потому что разница двух треугольных чисел в показателе как раз равна n).

И в результате остаётся неразбитым опять АБ — но порядка (n-1). А у него разбиений (по той же теореме) 2^{n(n-1)/2}. То есть _доля_ тех разбиений, где угловая доминошка ориентирована "не как надо", равна 2^{n(n-1)/2} / 2^{n(n+1)/2} = 1/2^n

Более того, такая же лесенка пойдёт и вниз:

А тогда и клетку C, и так далее: пошла "лесенка":