2. Начала динамики

Еремин Геннадий
опубликовано 6 May 2015 13:49

Пути Дика

Со словами Дика связывают пути Дика на плоскости. Каждой правильной скобочной последова­тельности взаимно-однозначно соответствует непрерывная ломаная линия, состав­ленная из единичных диагональных звеньев (векторов), и которая, во-первых, начинается и заканчивается на оси абсцисс и, во-вторых, не пересекает ось абсцисс. Левой скобке соответствует звено подъема или восходящий вектор, правой скобке  – звено спада или нисходящий вектор.

Пути Дика рисуют на целочисленной решетке в положительном квадранте, каждый путь начинается в начале координат. В такой решетке по оси абсцисс откладывают номера позиций скобок, а по оси ординат – разбаланс скобок (превышение числа левых скобок над правыми). Разбаланс в i-ой позиции может меняться от 0, когда первые i знаков слова Дика образуют правильную скобочную последовательность, и до величины i, если в на­чаль­ном фрагменте только левые скобки.

Пример 2.1. На рис. 1 приведен пример пути Дика, который мы позаимствовали из книги С.Ландо. Под осью абсцисс показана соответствующая скобочная последо­вательность  ((()(()()))). По мере продвижения слева направо вдоль скобок с каждой левой скобкой растет высота ломаной линии, увеличивается разбаланс. Правые скобки уменьшают разбаланс.

путь Дика

Ломаная кривая на рисунке достигает высоты 4. В слове Дика 6 пар скобок, и максимальная высота 6 соответствует начальной последовательности (((((()))))). Треугольник с надстроенной пунктиром «макушкой» (начальный путь Дика) назовем опорным треугольником. Все ломаные линии длины 12 не выходят за пределы такого опорного треугольника. Узлы координатной сетки, отмеченные прозрачными точками, недоступны (недостижимы, запрещены) для ломаных линий. Для каждого достижимого узла сумма координат четна. Очевидно, размежевание доступных и запрещенных узлов сохраняется при расширении опорного треугольника.

В дальнейшем под n будем понимать число пар скобок в словах Дика. Количество путей Дика из 2n звеньев равно числу Каталана  cn. Именно столько путей можно провести от начала координат до точки (2n,0) в опорном треугольнике высотой n. В связи с этим на рисунке рядом с узлом (12,0) поставлена метка c_6 \!=\! 132. Аналогичным образом помечены числами Каталана еще пять узлов на оси абсцисс.

Поставим метки другим узлам опорного треугольника. Метка равна числу путей из точки (0,0) в данный узел, поэтому запрещенным узлам соответствует метка 0. К узлам диагонали координатной сетки ведет единственный путь из восходящих векторов (группа смежных левых скобок в начальном фрагменте слова Дика). На рис. 1 мы пометили единицей узлы диагонали, включая начало координат (и это логично).

Проставленные метки очевидны, их значения не вызывают сомнений. С увеличением числа пар скобок по оси абсцисс выстраивается последовательность Каталана, а по диагонали координатной сетки – череда единиц. Чтобы разобраться с внутренними узлами опорного треугольника, необходимо проанализировать взаимные связи звеньев в ломаных линиях, т.е. динамику Дика.

фрагментНа рис. 2 показан фрагмент пути, в котором за группой восходящих звеньев следует нисходящее звено (в соответствующем фрагменте слова Дика за группой смежных левых скобок следует правая скобка). В этом случае конечный узел получил бы, как и диагональные узлы, единичную метку, если бы находился на оси абсцисс. Но к внутреннему узлу снизу можно подвести восходящее звено (показано зеленым цветом) от соседнего узла с меткой, например, k. И тогда метка внутреннего узла равна  1+k, поскольку к такому узлу можно продолжить все пути, оканчивающиеся в обоих дочерних узлах.

Такая ситуация типична для всех точек внутри опорного треугольника: в каждый узел можно провести как восходящий так и нисходящий вектор из соседних узлов с меньшей абсциссой. И метка такого узла равна сумме меток упомянутых соседних узлов. Метки ниже оси абсцисс и выше диагонали положительного квадранта равны нулю, поэтому рассмотренное правило справедливо для всей координатной сетки. Таким образом, для произвольного узла (i, \!j) его метка или динамика определяется следующим равенством или уравнением динамики:

    \[ d_{i,j} = d_{i-1,j-1} + d_{i-1,j+1}, \;\; j>0.\]

Пользуясь уравнением динамики и приняв начальное значение d_{0,0} \!=\! 1 (отправная точка), легко рассчитать динамику всей координатной сетки.

Треугольник Дика

В каждой i-ой позиции слова Дика разбаланс скобок не может превысить величину i, поэтому совокупность значимых (ненулевых) узлов целочисленной решетки образует треугольную матрицу (см. рис. 3), которая более известна как треугольник Каталана. Такая конструкция часто рассматривается в связке с треугольником Паскаля (таблица биномиальных коэффициентов), у которого аналогичное уравнение динамики.

треугольникПоскольку мы пришли к полученной матрице, отталкиваясь от слов Дика, через пути Дика и динамику Дика, то логично назвать эту таблицу треугольником Каталана-Дика, а проще треугольником Дика, как это сделано, например, здесь.

В дальнейшем будем различать треугольник Дика (бесконечная таблица) и опорный треугольник – ограниченный начальный фрагмент таблицы, равнобедренный треугольник с высотой, равной  n – фиксированному числу пар скобок в словах Дика.

фрагментНа рис. 4 показан фраг­мент треугольника Дика – опорный треугольник для  n\!=\!6. Треугольник симметричный, внешняя восходящая диагональ (единичные метки) и внешняя нисходящая диагональ (метки 1, 6, 20 и т.д.) содержат одинаковое количество узлов. Для каждого узла (i, j) существует симметричная или зеркальная точка (2n\!-\!i, j) со своим, в общем случае, иным значением динамики. Далее зеркальную пару (или зеркало)  a и b  будем обозначать a\! \thicksim \!b.

Вдоль высоты разместились самосимметричные узлы (n,j). В нашем примере – это четыре узла в центре треугольника с метками 1, 5, 9, 5. Несложно показать: сумма квадратов меток самосимметричных узлов равна количеству путей Дика (действительно, 1+25+81+25 = 132).

Все пути Дика начинаются в точке (0,0) и заканчиваются в точке (2n,0). Если изменить (инвертировать) ориентацию путей, поместив их начало в точку (2n,0), и пересчитать обратную динамику, то зеркала (i, j) и (2n\!-\!i, j) обменяются метками, т.е.  d^{-1}_{i, j} \!=\! d_{2n-i, j}.  Естественно, в самосимметричных узлах прямые и обратные метки совпадают, или  d^{-1}_{n, j} \!=\! d_{n, j}.

Напомним, метка d_{i, j} указывает на число путей ведущих из начала координат в узел (i,\! j), но тогда обратная метка  d^{-1}_{i, j} равна количеству путей от конечной точки (2n,0) к узлу (i,\! j). Следовательно, число путей Дика, проходящих через узел (i,\! j), равно произведению обеих меток  d_{i, j} d^{-1}_{i, j}.  Если просуммировать такие произведения по всем узлам произвольного вертикального сечения в опорном треугольнике, то получим число Каталана  cn. Отсюда следует разложение числа Каталана на сумму квадратов меток высоты опорного треугольника. Теперь сформулируем свойство треугольника Дика:

Свойство 2.1. Сумма квадратов чисел в n-ом сечении треугольника Дика равна cn.


<<<<<  Последовательности  ||  Идентификация  >>>>>

Добавить комментарий