Модифицированный треугольник

Еремин Геннадий
опубликовано 26 May 2015 21:55

 

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

Повторим на рис. 10 треугольник Дика. Зафиксируем единичные диагональные метки положительного квадранта – верхняя грань треугольника Дика – и закрепим эти точки на координатной сетке.

треугольникДля примера, узел (8,8)  с единичной меткой «пришпилен» кнопкой, и от кнопки проведена изолиния к узлу (16,0). Дополнительно выделены цветом тройка узлов, связанных уравнением динамики:  d_{9,3} \!=\! d_{8,2} \!+\! d_{8,4}.

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

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

Напомним, в (немодифицированном) треугольнике Дика при прокладке ломаных линий (путей Дика) по оси абсцис откладывается текущая позиция  i  в скобочном наборе,  0\! \le \!i\! \le \!2n, где  n – число пар скобок. По оси ординат следует разбаланс скобок  j  (или глубина вложенности – превышение числа левых скобок над правыми). В модифици­рованной матрице вторая координата точек сохраняет свое значение и смысл, но меняется первая координата: здесь она указывает на изолинию треугольника Дика.

В такой постановке координаты  i, j, n  связаны координатным уравнением

(1)   \begin{equation*}  i + j - 2n = 0, \;\;\;  0 \le j \le  i  \le  2n  \end{equation*}

В уравнении (1) переменная  n  означает все тоже – число пар скобок в скобочных наборах, но вырос статус этой переменной, она становится равноправной координатой наряду с  i  и  j.

Очевидно, переход от рис. 10 к рис. 11 сопровождается лишь сменой координатной сетки  i\! \times \!j  на сетку  n\! \times \!j.  В первом случае переменные  i  и  j первичные(независимые), а вторична (зависима) переменная  n \!=\! (i \!+\! j)/2. Во втором варианте первичны переменные   и  j, вторична переменная  i \!=\! 2n \!-\! j.

Узлы диагонали положи­тельного квадранта сохраняют свои позиции на обоих рисунках. Для каждого из этих узлов все три координаты совпадают, т.е.  i \!=\! j \!=\! n.

На модифицированном треугольнике Дика также можно выделить своего рода изолинии – это группы разрозненных (изоморфных) узлов с одинаковым значением i. Изоморфные узлы составляют столбец в исходном треугольнике.

Абсцисса  n – новая переменная в новой координатной сетке. Переменная n удачно согласуется с индексами чисел Каталана, поскольку они разместились в нулевой строке в соответствии со своими индексами, т.е.  d_{n,0} \!=\! c_n  для всех n (оставим прежнее обозначение динамики, так как значения меток и их сущность не изменились). Таким образом, на модифици­рованной оси абсцисс получаем последовательность чисел Каталана в чистом виде; диагональ положительного квадранта, по-прежнему, состоит из единиц.

Динамика Дика в модифицированном виде выглядит следующим образом:

(2)   \begin{equation*} d_{n,j} = d_{n-1,j-1} + d_{n,j+1}, \;\; j\! >\!0 \end{equation*}

На рис. 11 выделенная тройка узлов подтверждает уравнение (2):  d6.3 = 5,2 + d6,4. Выпишем очевидные метки  n-ого столбца:

dn,0 = dn,1 = cn,   dn,2 = cncn-1,   dn,n-1 ­= n,  dn,n ­= 1.

Из модифицированного уравнения динамики (2) нетрудно вывести следующее свойство: сумма меток  n-ого столбца равна  (n+1)-ому числу Каталана или

    \[c_{n+1} = \sum_{j=0}^{n} d_{n,j}.\]

Нетрудно видеть, в модифицированной матрице каждый столбец самодостаточен. Иначе говоря, нетрудно перейти от любого столбца к соседнему (справа или слева). Если известен один столбец, можно выстроить весь модифицированный треугольник. Манипу­лирование столбцами позволило ускорить расчеты, например, при вычислении обратных меток в задачах идентификации.

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

Модифицированны­й опорный треугольник фиксируется верхним определяющим узлом, поскольку ограничен его координатами. Назовем треугольник с определяющим узлом  (n,n)   модифицированным n-тре­уголь­ником или просто n-треуголь­ником (если нет разночтений).

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

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

Модифицированные пути Дика теряют свою непрерывность, и здесь мы уже не может говорить о ломаных линиях, разве что о нарезке участков подъема из первичных путей. Модифицированный путь заканчивается выходом к конечному столбцу  n-треугольника, поскольку далее следует скачок непосредственно к оси абсцисс, размер скачка варьируется от 1 до n. Повторим, модифицированный путь Дика заканчивается последним звеном подъема.

путьНа рис. 12 показан модифицированный треугольник с определяющим узлом (8,8). Для скобочного набора (()(())(()()))() проложен модифи­цированный путь Дика, который был рассмотрен ранее в перво­начальном виде здесь. Разрывы показаны тонкой линией, поскольку эти отрезки не являются частью пути. В такой модели теряется наглядность работы с зеркалами, поскольку новый опорный треугольник несимметричен.

Узлам внешней диагонали соответствуют зеркальные точки из конечного столбца  n-треугольника , т.е. (j, j)\! \thicksim \!(n, j). Смещаясь по строке от краев к центру, мы получаем новые зеркала, или  (j \!+\! \Delta, j)\! \thicksim \!(n \!-\! \Delta, j). Смещение \Delta принимает значения от 0 до n \!-\! j. Заменяя  j \!+\! \Delta \!=\! k,  получим общий вид зеркала  (k, j)\! \thicksim \!(n\!-\!k\!+\!j, j), \; 0\! \le \!k\! \le \!n.

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

Каждое звено спада, предшествующее звену подъема, вызывает скачкообразное перемещение или бросок по скобочному ряду. И это же звено спада на модифици­рованном пути преобразуется в разрыв функции 1-го рода. Очевидно, разрывы в путях на модифицированном треугольнике полностью идентичны прыжкам по ряду Дика. Разрывы в модифицированных путях и прыжки по ряду непосредственно взаимосвязаны, природа их аналогична.

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

Полиномы Дика оптимальным образом вписываются в новую модель. Полученное ранее полиномиальное уравнение

pj (n) = pj-1 (n) – pj-2 (n–1),   j > 1,

уже ориентировано на обновленную координатную сетку n\! \times \!j , поскольку в этой системе координат параметр полиномов  n  стано­вится независимой переменной.

Некоторые особенности связаны с матрицей коэффициентов полиномов. Полино­миальная матрица строится в несколько иной системе координат: по оси абсцисс откладывается разбаланс скобок j, а по оси ординат – величина  n  в убывающем порядке, начиная с некоторого фиксированного значения.

Клин Дика, как и любая часть модифицированного треугольника, уплотняется в новой координатной сетке. На рис. 13 цветом выделен сегмент – клин Дика – (немоди­фициро­ванного) опорного треугольника из рассмотренного ранее примера (рис. 9).  Клин порожден узлом с независимыми координатами  i =15,  j = 9. Узел лежит на изолинии с номером  n = (15+9)/2 = 12.

клин

На соседнем рис. 14 показаны тот же узел и тот же сегмент в новой координатной сетке  n\! \times \!j. Независимые координаты узла  n =12,   j = 9. Третья координата зависимая  i \!=\! 2\! \times \!12\! - \!9 \!=\! 15. Как видим, клин Дика в упакованном формате очень даже соответствует своему названию.

Модифицированный треугольник Дика первоначально строился для практических нужд. Здесь экономится память, удобно работать с данными, при необходимости просто меняется размерность задачи (нетрудно нарастить или сократить длину путей Дика). Но использование координатной сетки  n\! \times \!j  позволяет не только уплотнить треугольник Дика, такая конструкция на наш взгляд более удобна для моделирования динамики скобочных последовательностей.

Трехмерная решетка Дика. С каждым узлом (модифицированного или немодифицированного) треугольника Дика  связаны три равноправные координаты, удовлетворяющие координатному уравне­­нию (1). Две координаты всегда независимы, вопрос заключается в том, какую из трех переменных назначить зависимой. В стандартном треугольнике Дика (рис. 10) зависима переменная  n – число пар скобок, в описанном модифицированном треугольнике (рис. 11) зависима другая переменная  i – текущая позиция в скобочном наборе.

Теоретически можно назначить зависимой и переменную  j – разбаланс скобок (превышение числа левых скобок над правыми). Посмотрим, как выглядит треугольник Дика в координатной сетке  i\! \times \!n. Очевидно, диагональные узлы, по-прежнему, останутся на своих местах с идентичными координатами  i \!=\! j \!=\! n, а нисходящие диагонали трансформируются в горизонтальные линии.

путьНа рис. 15 показан опорный треугольник с клином Дика из последних двух рисунков, но уже в третьей координатной сетке. Полученная конст­рукция плотная, без нулевых узлов. Но, конечно, такая модель непрактична и беспо­лезна, по крайней мере, в нашем случае.

Наверное, в общем случае не так важно, какая  именно модель выбирается для представления данных. Главное удобство работы с информацией. Единое представление для системы взаимо­свя­занных много­плановых задач порой и невозможно. И это естественно, разнообразие применяемых моделей позволяет всесторонне исследовать объекты.

Очевидно, на рисунках 10, 11 и 15 мы имеем три проекции некоторой конструкции трехмерного пространства (3D). Эта конструкция размещена в положительном сегменте 3D (координаты x,y,z неотрицательны) и имеет вид бесконечной плоской сплошной решетки. Для каждой точки (x,y,z) такой трехмерной решетки выполняются два условия:

    \[x \ge y, \quad x + y = 2z.\]

Стержнем решетки является центральный луч сегмента, исходящий из начала координат и проходящий через точки (k,k,k), k \ge 0, с единичными метками. Трехмерную решетку логично назвать решеткой Дика.


<<<<<  Полиномы Дика  ||  Сервис on-line  >>>>>

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