Виктор Алексеевич Клепцын

Асимптотические задачи комбинаторики

В.А.Клепцын планирует провести 4 занятия.

Многие интересные задачи в комбинаторике формулируются в терминах «как выглядит случайный большой объект» или «сколько есть таких объектов данного размера». К примеру, в случайной последовательности нулей и единиц большой длины n нулей и единиц примерно поровну, а в разложении случайной перестановки n элементов в произведение независимых циклов, скорее всего, есть «большой» цикл (имеющий сравнимую с n длину), а всего циклов порядка логарифма n.

Оказывается, что задачи «подсчитать количество» и «найти предельный вид» зачастую связаны друг с другом. Мы разберём такую связь, решив (лишь на физическом уровне строгости!) несколько таких задач:
1) Как выглядит типичное разбиение числа n в сумму невозрастающих слагаемых? Какова асимптотика количества таких разбиений (формула Харди-Рамануджана)?
2) Что такое аффинная длина, и как выглядит типичная ломаная, идущая из вершины (0,1) в вершину (1,0) единичного квадрата, если её вершины принадлежат решётке с шагом 1/n?
3) Как посчитать, сколькими способами на доминошки можно разрезать данную плоскую фигуру? Как выглядит типичное разбиение ацтекского бриллианта на доминошки? Откуда берётся «полярный круг», за которым все доминошки оказываются «замороженными»? И какое к этому отношение имеет угол кристалла и кубики, сложенные в углу комнаты?

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

Материалы

Литература

  1. А. М. Вершик, Статистическая механика комбинаторных разбиений и их предельные конфигурации, Функциональный анализ и его приложения, 30:2 (1996), 19--39.
  2. А. М. Вершик, С. В. Керов, Асимптотика максимальной и типичной размерностей неприводимых представлений симметрической группы, Функциональный анализ и его приложения, 19:1 (1985), 25--36.
  3. А. М. Вершик, Предельные формы типичных геометрических конфигураций и их приложения. В сб.: Глобус. Общематематический семинар. Выпуск 2, ред.: М. А. Цфасман, В. В. Прасолов. М.: МЦМНО, 2005, с. 103--125.
  4. Ф. Петров, Два элементарных подхода к предельным формам диаграмм Юнга, Записки научных семинаров ПОМИ, 370, ПОМИ, СПб., 2009, 111--131.
  5. H. Cohn, R. Kenyon, J. Propp, A variational principle for domino tilings, J. Amer. Math. Soc., 14(2001), no. 2, 297-346. (ArXiv:math/0008220)
  6. A. Okounkov, Limit shapes, real and imaginary

Organization Committee e-mail:
dubna@mccme.ru