===

А сегодняшний рассказ будет про один из моих любимых сюжетов — про асимптотическую комбинаторику.

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

Игрушечный пример — последовательности нулей и единиц. Их 2^n, а в типичной последовательности нулей и единиц примерно поровну. Наконец, отклонение от среднего числа имеет типичный порядок \sqrt{n}, и описывается центральной предельной теоремой — если на \sqrt{n} поделить, то частное ведёт себя (асимптотически) как случайная величина, распределённая по Гауссу.

(Собственно, мы даже это уже в этом канале обсуждали — см. сообщение выше)

Чтобы получалась более комбинаторно-геометрическая картинка, можно превратить последовательность 0 и 1 в путь, идущий по квадратной решётке вправо при 0 и вверх при 1. Тогда при большом n путь, скорее всего, будет идти рядом с диагональю.

Можно нарисовать картинки — только я разверну решётку на 45 градусов; путь тогда будет идти вправо-вверх и вправо-вниз, а в среднем просто вправо.

Вот 30 шагов:

Вот 100:

Вот 300 (уже без решётки, иначе она превратится в сплошной чёрный фон):

Ну и наконец, вот 3000 —

А вот растянутая в корень из n раз по вертикали картинка — как раз отвечающая на вопрос про поведение типичных отклонений (n=1000):

Это уже — (одномерное) броуновское движение (а точнее, его график как функции от времени).

Пожалуй, самый сейчас известный пример из асимптотической комбинаторики — это ацтекский бриллиант.

Вот тут есть рассказ о нём по-французски —
http://images.math.cnrs.fr/Pavages-aleatoires-par-touillage (но с языком можно справиться как Google Translate-ом, так и просто посмотреть на красивые картинки), ему посвящён вот этот математический постер — http://sorciersdesalem.math.cnrs.fr/Posters/PosterCercleArctique.png ; но я про него коротко расскажу с самого начала.

А по-русски про него можно подробно прочитать в дубнинской брошюре Е. Смирнова, "Три взгляда на ацтекский бриллиант",
https://www.mccme.ru/free-books/dubna/smirnov-aztec.pdf