Полиномы Дика

Еремин Геннадий
опубликовано 28 May 2015 18:39

Рассмотренные алгоритмы активно работают с метками узлов треугольника Дика. Поэтому при расчетах на компьютере важно минимизировать машинное время, затрачиваемое на вычисление меток, учитывая в первую очередь размеры обрабатываемых чисел. Например, число Каталана с индексом 100 содержит 57 десятичных знаков, вот это число:

c100 =  896 519 947 090 131 496 687 170 070 074 100 632 420 837 521 538 745 909 320.

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

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

путь ДикаМетки двух верхних и двух нижних узлов изолинии   известны:

dn,n = 1,  dn+1,n-1 = nd2n-1,1 = d2n,0 = cn.

Остальные метки можно рассчитать в соответствии с уравнением динамики, постепенно продвигаясь по цепочке от начальной точки (0,0). Повторим уравнение динамики

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

Но динамику можно рассчитывать иначе (порой, значительно быстрее), отталкиваясь от чисел Каталана. Решим уравнение (1) относительно второго слагаемого:

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

Выражение (2) можно  назвать разностным уравнением динамики Дика. В сответствии с уравнением (2) вычислить метку узла (i,j) можно, продвигаясь вверх по изолинии от узла (i\!+\!\!j,0). Вот несколько равенств:

d_{i,0}=c_n, \;\; n=i/2  (i четно);
d_{i,1}=c_n, \;\; n=(i\!+\!1)/2  (i нечетно);
d_{i,2}=c_n-c_{n-1}, \;\; n=(i\!+\!2)/2  (i четно);
d_{i,3}=c_n-2c_{n-1}, \;\; n=(i\!+\!3)/2 (i нечетно);
d_{i,4}=c_n-3c_{n-1}+c_{n-2}, \;\; n=(i\!+\!4)/2  (i четно);
d_{i,5}=c_n-4c_{n-1}+3c_{n-2}, \;\; n=(i\!+\!5)/2  (i нечетно).

Из шести выражений первые два равенства тривиальные, третье и четвертое легко проверить, над последними двумя надо поработать с бумагой и карандашом. Но для последующих значений  j  придется искать правило построения таких полиномов.

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

    \[d_{i,j}=p_j(n), \; n= \frac{i\!+\!j}{2}\]

Обратим внимание, в разностном уравнении (2) узлы d_{i, j} и d_{i+1, j-1} расположены на одной и той же изолинии n, а узел d_{i, j-2} размещен на соседней (n-1)-ой изолинии. Поэтому равенство (2) эквивалентно следующему выражению:

(3)   \begin{equation*} p_ j(n)=p_{j-1}(n) - p_{j-2}(n\!-\!1), \;\; j\! > \!1. \end{equation*}

Полученное выражение легко проверяется на рассмотренных равенствах. Вычислим следующий 6-ой полином с помощью уравнения (3):

d_{i,6} = p_6(n) =p_5(n) - p_4(n\!-\!1) =
=(c_n - 4c_{n-1} + 3c_{n-2})-(c_{n-1} -3c_{n-2}+c_{n-3})=
=c_n - 5c_{n-1} + 6c_{n-2} - c_{n-3}, \;\; n=(i\!+\!6)/2.

Полиномы  pj (n)  логично назвать полиномами Дика, а выражение (3)  – полино­миальное уравнение или динамика полиномов Дика. Необходимо подчеркнуть, ранее мы под n понимали фиксированную величину – число пар скобок в слове Дика. В уравнении (3)  n – па­раметр полиномов, вторичная переменная, которой нет ни в уравнении дина­мики (1), ни в треугольнике Дика. Переменная n опосредованно представляет в полиномах первичную переменную i, поскольку n\!=\! (i\!+\!j)/2.

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

матрица ДикаМатрица с коэффициентами полиномов или полиномиальная матрица Дика строится следующим образом. Нижняя строка набирается из единиц, остальные строки первоначально обнулены. Далее коэффициенты пересчитываются построчно по формуле:

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

Очевидно, уравнение (4) непосредственно следует из динамики полиномов (3). Построение полиномиальной матрицы начинается с элемента a_{2, n-1}\!=\!a_{1, n-1} \!-\! a_{0, n} \!=\! 0\!-\!1 \!=\! -1.

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

a2k,n-k = (-1)kk > 0.

В качестве пояснений на рисунке дополнительно выделены три коэффициента, связанные равенством (4):  a_{12,n-3} \!=\! a_{11,n-3} \!-\! a_{10,n-2} \!=\! -56\! -\! 28 \!=\! -84.

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

а) Метка узла на пересечении 15-ого столбца и 7-ой строки равна 910 (см. рис. 7). Напомним, равенство d_{15,7}\!=\! 910 указывает на количество начальных фрагментов правильных скобочных последовательностей, которые в позиции 15 допускают раз­баланс скобок 7. Проверим это значение. Узел (15,7) размещен на изолинии  n\! =\! (15\!+\!7)/2\! =\! 11. Из коэффициентов 7-го столбца матрицы составляем полином:

d_{15,7}=p_7(11)=c_{11}-6c_{10}+10c_{9}-4c_8=
= 58786 -6\! \times\! 16796 +10\! \times\! 4862 -4\!\times\! 1430= 910.

б) Вычислим динамику узла (32,10). Полусумма координат узла дает нам 21-ую изолинию, для расчета выбираем коэффициенты из 10-го столбца матрицы:

d32,10 = p10(21) = c21 – 9c20 + 28c19 – 35c18 + 15 c17c16 = 64 512 240.

в) Составим полином для узла (132,10). Узел находится на 71-ой изолинии треугольника Дика, но для составления полинома мы, по-прежнему, выбираем 10-ый столбец полино­миальной матрицы. Итак,

d132,10 = p10(71) = c71 – 9c70 + 28c69 – 35c68 + 15c67c66.

Для читателей, желающих проверить результат:

с66 = 5 632 681 584 560 312 734 993 915 705 849 145 100,
с67 = 22 033 725 021 956 517 463 358 552 614 056 949 950,
с68 = 86 218 923 998 960 285 726 185 640 663 701 108 500,
с69 = 337 485 502 510 215 975 556 783 793 455 058 624 700,
с70 = 1 321 422 108 420 282 270 489 942 177 190 229 544 600,
с71 = 5 175 569 924 646 105 559 418 940 193 995 065 716 350.

Ответ: d132,10 = 39 575 872 930 789 889 398 293 766 300 107 613 200.

Клин Дика

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

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

Зафиксируем в треугольнике Дика узел  x = (ix, jx). Будем полагать, что узел нахо­дится внутри треугольника, иначе говоря,  i_x \!>\! j_x \!>\! 0  (в противном случае о расчете динамики dx говорить не прихо­дится). Узел расположен на изолинии  n_x \!=\! (i_x \!+\!j_x)/2. Изолиния фиксирует в треугольнике Дика опорный треугольник с основанием на оси абсцисс длиной 2nx. Рассмотрим три группы узлов, три сегмента, три составные части опорного треугольника, которые однозначно определяются узлом x.

Величину dx можно вычислить по классической схеме, продвигаясь от начала координат в соответствии с уравнением (1). При этом узлы, которые задействованы в вычисли­тельном процессе, отнесем к первому основному сегменту. Логично к этому сегменту отнести и сам узел x. Очевидно, в основном сегменте нет узлов опорного треугольника с абсциссой, превышающей  ix.

Расчет dx можно проводить от нижнего узла (2nx, 0), поднимаясь по изолинии вверх к узлу x в соответствии с разностным уравнением динамики (2). В этом случае узлы, охваченные вычислительным процессом, отнесем ко второму разностному сегменту. В разностный сегмент также включим заданный узел x, и тогда сегмент состоит из тех и только тех узлов опорного треугольника, абсцисса которых равна или больше ix. Таким образом, первый и второй сегменты, сопри­касаясь, имеют общий узел-шарнир x.

В большинстве случаев не все узлы опорного треугольника используются в вычислительных процессах при расчете dx, и эти узлы образуют третий последний сегмент. Третий сегмент часто соизмерим с остальными сегментами, и может превосходить по количеству точек некоторые из них. Дальнейший анализ проведем на конкретном примере.

Пример 2. На рис. 9 выделен узел (15,9) с динамикой 350. Опорный треугольник (расцвеченные узлы) ограничен изолинией 12 с крайними узлами (12,12) и (24,0).

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

Третий сегмент (узлы на «ржавом» фоне) встроен между основным и разностным сегментами. Здесь собраны узлы, которые не используются для расчета динамики d15,9, это своего рода мертвая зона. Сегмент напоминает клин, разъедающий или рассекающий опорный треугольник, поэтому так его и назовем – клин Дика.

В общем случае для расчетного узла  x = (ix, jx)  клин Дика размещается между ix-ым столбцом и диагональю, которая соединяет узлы  x  и (i_x \!-\! j_x, 0). Вершина клина  разместилась в точке (i_x \!-\!1, j_x \!-\!3), поэтому клин Дика существует только в случае  j_x \!>\! 2.

Если перебирать узлы изолинии с нижней точки (2nx, 0), разностный сегмент постепенно расширяется за счет  основного сегмента. Начиная с узла (2n_x \!-\! 3, 3), появляется клин Дика. В верхней точке (n_x,n_x) основной сегмент вырождается и совпадает с внешней диагональю опорного треугольника. При этом клин Дика и разностный сегмент достигают максимальных размеров.


<<<<<  Идентификация  ||  Модифицированный треугольник  >>>>>

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