На самом деле, теорема Фюрстенберга о кратном возвращении теореме Семереди даже и эквивалентна (см. второе предложение выше). Но самый технически сложный шаг работы Фюрстенберга (и о чём я пока не сказал ни слова) — это как теорему о кратном возвращении динамическими методами доказывать. И там начинают возникать слова "слабое перемешивание", "компактный фактор", и ещё разные — но вот туда я как раз не пойду.
У этой науки есть ещё обобщения — многомерная теорема Фюрстенберга и Кацнельсона и следующая из неё многомерная версия теоремы Семереди ; см. https://terrytao.wordpress.com/2008/02/10/254a-lecture-10-the-furstenberg-correspondence-principle/ —
What's new
254A, Lecture 10: The Furstenberg correspondence principle
In this lecture, we describe the simple but fundamental Furstenberg correspondence principle which connects the “soft analysis” subject of ergodic theory (in particular, recurrence theo…
То есть в подмножестве Z^m с положительной верхней плотностью есть подмножества, гомотетичные любому конечному "шаблону" (v_1,...,v_k).
Но, наверное, в этом месте я хочу закончить рассказ об этой работе Фюрстенберга — и продолжить рассказ о других его работах в следующий раз.
===
В качестве паузы (чтобы писать не только о динамических системах) — короткий рассказ про совсем другое: про числа Каталана.
Допустим, нас интересует, сколькими способами можно расставить n открывающих и n закрывающих скобок так, чтобы в любом начальном подслове закрывающих скобок было не больше, чем открывающих. То есть (), (()), ()() можно, ())( или ())(()() нельзя.
Если нарисовать "по точкам" график разности "число открывающих скобок минус число закрывающих из первых k символов", то он состоит из отрезков, идущих под 45 градусов либо вправо-вверх, либо вправо-вниз. Соответственно, число Каталана это число таких путей, идущих из точки (0,0) в точку (2n,0) и не спускающихся ниже оси абсцисс по пути.
Оно же равно количеству деревьев на плоскости с n+1 вершиной, отмеченным корнем и "землёй" (или, равносильно, первым ребром из этой вершины): если обходить это дерево "снаружи", начиная с первого ребра — расстояние до корня как раз и будет меняться на +1/-1 на каждом шаге:
В качестве паузы (чтобы писать не только о динамических системах) — короткий рассказ про совсем другое: про числа Каталана.
Допустим, нас интересует, сколькими способами можно расставить n открывающих и n закрывающих скобок так, чтобы в любом начальном подслове закрывающих скобок было не больше, чем открывающих. То есть (), (()), ()() можно, ())( или ())(()() нельзя.
Если нарисовать "по точкам" график разности "число открывающих скобок минус число закрывающих из первых k символов", то он состоит из отрезков, идущих под 45 градусов либо вправо-вверх, либо вправо-вниз. Соответственно, число Каталана это число таких путей, идущих из точки (0,0) в точку (2n,0) и не спускающихся ниже оси абсцисс по пути.
Оно же равно количеству деревьев на плоскости с n+1 вершиной, отмеченным корнем и "землёй" (или, равносильно, первым ребром из этой вершины): если обходить это дерево "снаружи", начиная с первого ребра — расстояние до корня как раз и будет меняться на +1/-1 на каждом шаге:
Оно же число триангуляций [диагоналями] n+2-угольника. Ну и вообще у чисел Каталана очень много разных определений и свойств — но речь не об этом, а о том, как их посчитать.
Во-первых, можно через производящие функции. Несложно увидеть рекуррентное соотношение для чисел Каталана C_n:
Если собрать их в производящую функцию,
F(z)=\sum_n C_n z^n,
то в правой части рекуррентного соотношения стоят коэффициенты F(z)^2 — которые ещё нужно сдвинуть на одну степень. Поэтому оно превращается в квадратное уравнение на производящую функцию:
F(z)-1=z F^2(z).
F(z)=\sum_n C_n z^n,
то в правой части рекуррентного соотношения стоят коэффициенты F(z)^2 — которые ещё нужно сдвинуть на одну степень. Поэтому оно превращается в квадратное уравнение на производящую функцию:
F(z)-1=z F^2(z).
(знак в числителе должен быть минусом, потому что иначе числитель не обратится в ноль при z=0, а у нас не может быть особенности вида 1/z).
И, наконец, разложив (1-4z)^{1/2} по биному Ньютона для нецелой степени — где нецелый биномиальный коэффициент определяется как
(конечно же, бином Ньютона для нецелой степени это то же самое, что и ряд Тейлора) — и немного переписав получившееся произведение (1/2)*(1/2)*(3/2)*(5/2)*...*4^n/n!, получаем явный ответ
И это, конечно, очень техничный способ получить ответ. Но мне больше всего нравится другой способ — который я узнал из лекции А. А. Кириллова на "Студенческих чтениях НМУ" (предшественник семинара "Глобус").
Давайте находить сразу для всех точек (n,k) число способов добраться до них ломаными (с шагами (1,1) и (1,-1)), не спускаясь ниже оси абсцисс. Только развернём картинку на 90 градусов по часовой стрелке — чтобы ломаные шли вниз-вправо или вниз-влево.