Математические байки
الذهاب إلى القناة على Telegram
Рассказы про разную математику. Архив: http://dev.mccme.ru/~merzon/mirror/mathtabletalks/
إظهار المزيد4 361
المشتركون
لا توجد بيانات24 ساعات
+57 أيام
+3930 أيام
أرشيف المشاركات
4 359
Во-первых, можно через производящие функции. Несложно увидеть рекуррентное соотношение для чисел Каталана C_n:
24 مارس 2020, 07:27
4 359
Оно же число триангуляций [диагоналями] n+2-угольника. Ну и вообще у чисел Каталана очень много разных определений и свойств — но речь не об этом, а о том, как их посчитать.
24 مارس 2020, 07:27
4 359
===
В качестве паузы (чтобы писать не только о динамических системах) — короткий рассказ про совсем другое: про числа Каталана.
Допустим, нас интересует, сколькими способами можно расставить n открывающих и n закрывающих скобок так, чтобы в любом начальном подслове закрывающих скобок было не больше, чем открывающих. То есть (), (()), ()() можно, ())( или ())(()() нельзя.
Если нарисовать "по точкам" график разности "число открывающих скобок минус число закрывающих из первых k символов", то он состоит из отрезков, идущих под 45 градусов либо вправо-вверх, либо вправо-вниз. Соответственно, число Каталана это число таких путей, идущих из точки (0,0) в точку (2n,0) и не спускающихся ниже оси абсцисс по пути.
Оно же равно количеству деревьев на плоскости с n+1 вершиной, отмеченным корнем и "землёй" (или, равносильно, первым ребром из этой вершины): если обходить это дерево "снаружи", начиная с первого ребра — расстояние до корня как раз и будет меняться на +1/-1 на каждом шаге:
24 مارس 2020, 07:25
4 359
Но, наверное, в этом месте я хочу закончить рассказ об этой работе Фюрстенберга — и продолжить рассказ о других его работах в следующий раз.
23 مارس 2020, 12:39
4 359
То есть в подмножестве Z^m с положительной верхней плотностью есть подмножества, гомотетичные любому конечному "шаблону" (v_1,...,v_k).
23 مارس 2020, 12:38
4 359
У этой науки есть ещё обобщения — многомерная теорема Фюрстенберга и Кацнельсона и следующая из неё многомерная версия теоремы Семереди ; см. https://terrytao.wordpress.com/2008/02/10/254a-lecture-10-the-furstenberg-correspondence-principle/ —
23 مارس 2020, 12:37
4 359
На самом деле, теорема Фюрстенберга о кратном возвращении теореме Семереди даже и эквивалентна (см. второе предложение выше). Но самый технически сложный шаг работы Фюрстенберга (и о чём я пока не сказал ни слова) — это как теорему о кратном возвращении динамическими методами доказывать. И там начинают возникать слова "слабое перемешивание", "компактный фактор", и ещё разные — но вот туда я как раз не пойду.
23 مارس 2020, 12:37
4 359
Тот переход, что мы сейчас выполнили, называется принципом соответствия Фюрстенберга; опять-таки, я процитирую статью Шкредова:
23 مارس 2020, 12:36
4 359
А если вспомнить, как мы меру µ строили — усредняя сдвиги — то отсюда следует, что для того же d верхняя плотность тех m, для которых точки m, m+d,...,m+(k-1)d принадлежат A, положительна. В частности, такие прогрессии любой длины k есть.
23 مارس 2020, 12:28
4 359
положительна. Но это множество это последовательности, у которых на местах 0, d,...,(k-1)d стоят единицы.
23 مارس 2020, 12:28
4 359
После чего остаётся применить самый сложный шаг доказательства — теорему Фюрстенберга о кратном возвращении (Furstenberg Multiple Recurrence Theorem); я её процитирую по статье И.Д. Шкредова "Теорема Семереди и задачи об арифметических прогрессиях" (http://www.mi-ras.ru/~ishkredov/Paperru/12.pdf )
23 مارس 2020, 12:27
4 359
Поэтому мера µ_n(E) это доля элементов A среди отрезка 0,1,...,n-1. И по определению верхней плотности есть подпоследовательность моментов n_m, для которой µ_{n_m}(E) стремится к rho(A)>0.
Выделив сходящуюся подпоследовательность µ_{n_{m_j}} уже из µ_{n_m} — получим меру µ, которая и инвариантная, и такова, что µ(E)=\rho(A)>0.
23 مارس 2020, 12:26
4 359
Так вот: запустим процедуру Крылова-Боголюбова для нашего отображения и для начальной точки x_A. При этом число n принадлежит A тогда и только тогда, когда на нулевом месте у f^n(x_A) стоит 1 — то есть f^n(x_A) лежит в E.
23 مارس 2020, 12:25
