ar
Feedback

لا تقع ضحية للمخادعين! تيليمتريو يكتشف ويُميّز هذه القنوات 👉 إذا كنت تريد رؤية العلامة، اشترك

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

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

الذهاب إلى القناة على Telegram

Рассказы про разную математику. Архив: http://dev.mccme.ru/~merzon/mirror/mathtabletalks/

إظهار المزيد
4 361
المشتركون
لا توجد بيانات24 ساعات
+57 أيام
+3930 أيام
أرشيف المشاركات
photo content
24 مارس 2020, 07:28

Во-первых, можно через производящие функции. Несложно увидеть рекуррентное соотношение для чисел Каталана C_n:
24 مارس 2020, 07:27

Оно же число триангуляций [диагоналями] n+2-угольника. Ну и вообще у чисел Каталана очень много разных определений и свойств — но речь не об этом, а о том, как их посчитать.
24 مارس 2020, 07:27

photo content
24 مارس 2020, 07:26

=== В качестве паузы (чтобы писать не только о динамических системах) — короткий рассказ про совсем другое: про числа Каталана. Допустим, нас интересует, сколькими способами можно расставить n открывающих и n закрывающих скобок так, чтобы в любом начальном подслове закрывающих скобок было не больше, чем открывающих. То есть (), (()), ()() можно, ())( или ())(()() нельзя. Если нарисовать "по точкам" график разности "число открывающих скобок минус число закрывающих из первых k символов", то он состоит из отрезков, идущих под 45 градусов либо вправо-вверх, либо вправо-вниз. Соответственно, число Каталана это число таких путей, идущих из точки (0,0) в точку (2n,0) и не спускающихся ниже оси абсцисс по пути. Оно же равно количеству деревьев на плоскости с n+1 вершиной, отмеченным корнем и "землёй" (или, равносильно, первым ребром из этой вершины): если обходить это дерево "снаружи", начиная с первого ребра — расстояние до корня как раз и будет меняться на +1/-1 на каждом шаге:
24 مارس 2020, 07:25

Но, наверное, в этом месте я хочу закончить рассказ об этой работе Фюрстенберга — и продолжить рассказ о других его работах в следующий раз.
23 مارس 2020, 12:39

То есть в подмножестве Z^m с положительной верхней плотностью есть подмножества, гомотетичные любому конечному "шаблону" (v_1,...,v_k).
23 مارس 2020, 12:38

photo content
23 مارس 2020, 12:38

У этой науки есть ещё обобщения — многомерная теорема Фюрстенберга и Кацнельсона и следующая из неё многомерная версия теоремы Семереди ; см. https://terrytao.wordpress.com/2008/02/10/254a-lecture-10-the-furstenberg-correspondence-principle/ —
23 مارس 2020, 12:37

На самом деле, теорема Фюрстенберга о кратном возвращении теореме Семереди даже и эквивалентна (см. второе предложение выше). Но самый технически сложный шаг работы Фюрстенберга (и о чём я пока не сказал ни слова) — это как теорему о кратном возвращении динамическими методами доказывать. И там начинают возникать слова "слабое перемешивание", "компактный фактор", и ещё разные — но вот туда я как раз не пойду.
23 مارس 2020, 12:37

photo content
23 مارس 2020, 12:36

Тот переход, что мы сейчас выполнили, называется принципом соответствия Фюрстенберга; опять-таки, я процитирую статью Шкредова:
23 مارس 2020, 12:36

А если вспомнить, как мы меру µ строили — усредняя сдвиги — то отсюда следует, что для того же d верхняя плотность тех m, для которых точки m, m+d,...,m+(k-1)d принадлежат A, положительна. В частности, такие прогрессии любой длины k есть.
23 مارس 2020, 12:28

положительна. Но это множество это последовательности, у которых на местах 0, d,...,(k-1)d стоят единицы.
23 مارس 2020, 12:28

photo content
23 مارس 2020, 12:28

Итак — для некоторого d мера µ множества
23 مارس 2020, 12:28

photo content
23 مارس 2020, 12:27

После чего остаётся применить самый сложный шаг доказательства — теорему Фюрстенберга о кратном возвращении (Furstenberg Multiple Recurrence Theorem); я её процитирую по статье И.Д. Шкредова "Теорема Семереди и задачи об арифметических прогрессиях" (http://www.mi-ras.ru/~ishkredov/Paperru/12.pdf )
23 مارس 2020, 12:27

Поэтому мера µ_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

Так вот: запустим процедуру Крылова-Боголюбова для нашего отображения и для начальной точки x_A. При этом число n принадлежит A тогда и только тогда, когда на нулевом месте у f^n(x_A) стоит 1 — то есть f^n(x_A) лежит в E.
23 مارس 2020, 12:25