|
|
Летняя школа «Современная математика», 2013
27 июля 2013 г. 12:45, г. Дубна
|
|
|
|
|
|
Асимптотические задачи комбинаторики. Дополнительная лекция
В. А. Клепцын |
Количество просмотров: |
Эта страница: | 137 | Видеофайлы: | 60 |
|
Аннотация:
Многие интересные задачи в комбинаторике формулируются в терминах «как выглядит случайный большой объект» или «сколько есть таких объектов данного размера». К примеру, в случайной последовательности нулей и единиц большой длины $n$ нулей и единиц примерно поровну, а в разложении случайной перестановки $n$ элементов в произведение независимых циклов, скорее всего, есть «большой» цикл (имеющий сравнимую с $n$ длину), а всего циклов порядка логарифма $n$.
Оказывается, что задачи «подсчитать количество» и «найти предельный вид» зачастую связаны друг с другом. Мы разберём такую связь, решив (лишь на физическом уровне строгости!) несколько таких задач:
- Как выглядит типичное разбиение числа n в сумму невозрастающих слагаемых? Какова асимптотика количества таких разбиений (формула Харди–Рамануджана)?
- Что такое аффинная длина, и как выглядит типичная ломаная, идущая из вершины $(0,1)$ в вершину $(1,0)$ единичного квадрата, если её вершины принадлежат решётке с шагом $1/n$?
- Как посчитать, сколькими способами на доминошки можно разрезать данную плоскую фигуру? Как выглядит типичное разбиение ацтекского бриллианта на доминошки? Откуда берётся «полярный круг», за которым все доминошки оказываются «замороженными»? И какое к этому отношение имеет угол кристалла и кубики, сложенные в углу комнаты?
Курс предназначен для студентов и школьников, знакомых с началами анализа.
Website:
http://www.mccme.ru/dubna/2013/courses/kleptsyn.htm
Цикл лекций
|
|