1. Введение
2. Числа и скобки
3. Скобочный ряд
4. Операции на скобках
5. Сервис on-line
СОДЕРЖАНИЕ (показать)

            4. Операции на скобках

Итак, в лексикографическом ряде нет дубликатов, ряд упорядочен двойной сор­тиров­кой. Внешняя сорти­ровка груп­пирует элемен­ты ряда по длине кода, при этом группы элементов с более корот­кими кодами разме­щаются ближе к началу ряда. Внут­ренняя (группо­вая) сорти­ровка лекси­когра­фически упоря­дочи­вает элементы внутри каж­дой группы.  k-ое число Моцкина индек­сирует  k-мак­симум скобоч­ного ряда. Обобщим это свой­ство в следу­ющем опре­деле­нии: индекс­ным рядом лекси­когра­фичес­кого ряда  A  назо­вем после­дова­тель­ность  I(A)  индексов макси­мальных элемен­тов этого ряда. В на­шем случае, если обозна­чить  B – скобоч­ный ряд, то  I(B)  – после­дова­тель­ность чисел Моц­кина.

Очевидно, для лекси­когра­фичес­кого ряда  A  индек­сный ряд  I(A)  также явля­ется лекси­когра­фичес­ким, и для него сущес­твует свой индек­сный ряд  I(I(A)) = I2(A) , который назовем индексным рядом второго порядка для  A. Для число­вой лексико­графи­ческой после­дова­тель­нос­ти логи­чно счи­тать  I 0(A) = A, т.е. индек­сный ряд нуле­вого порядка совпа­дает с исход­ным рядом. Инте­ресны после­дова­тель­ности, у которых совпа­дают индек­сные ряды различ­ных поряд­ков. В этом случае можно гово­рить об индек­сной перио­дич­ности рядов.

Пример 4.1. Для нату­раль­ного ряда  N  индексный ряд первого порядка  I(N)  имеет вид

9, 99, 999, 9999, 99999, ...
(4.1)

В свою очередь, индексный ряд для последовательности (4.1), т.е. индексный ряд второго порядка для  N, совпа­дает с исходным рядом, или  I(I(N)) = I2(N) = N . Таким образом, для нату­раль­ного ряда совпа­дают все индек­сные ряды четных порядков (0 также считаем четным числом) и все индек­сные ряды нечет­ных поряд­ков. В свою очередь, выше­сказан­ное спра­вед­ливо и для лекси­когра­фичес­кой после­дователь­ности (4.1). Таким образом, у нату­раль­ного ряда и ряда (4.1) индек­сная перио­дич­ность рав­на 2.

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

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

Процедура расширения применима и к произвольной группе внешних блоков. Расширен­ный блок назо­вем групповым, если он сфор­миро­ван на базе группы блоков роди­теля, т.е. за преде­лами отоб­ран­ных блоков обну­лены все скобки, а затем уда­лены лидиру­ющие нули. Груп­повой расши­ренный блок совпа­дает с исход­ным скобоч­ным набором, если в него вклю­чены все блоки роди­теля. Каждый расши­ренный блок нас­ле­дует конеч­ные нули набора-роди­теля, а на линей­ке скобоч­ного ряда роди­тель распо­ложен правее всех порож­денных расши­ренных бло­ков (если, конечно, расши­ренный блок не совпа­дает с роди­телем). С уче­том груп­пового расши­рения,  k-блоч­ный скобоч­ный набор может поро­дить   2k−1 прос­тых и/или груп­повых расши­рен­ных блоков.

В общем случае,  k-блочный набор можно разло­жить на sk расши­ренных блоков. Очевид­но, коли­чес­тво всех разло­жений  k-блоч­ного скобоч­ного набора совпа­дает с чис­лом разби­ений  k-эле­мент­ного множе­ства или чис­лом Белла (OEIS A000110). Напри­мер, в скобоч­ном наборе три блока A, B и C можно сгруп­пиро­вать пятью вариан­тами: A+B+C, A+BC, AB+C, AC+B, ABC. Отме­тим два триви­альных разло­жения скобоч­ного набора: поэле­мент­ное разло­жение, в котором все расши­ренные блоки прос­тые, и единич­ное разло­жение, в котором един­ствен­ный расши­рен­ный блок совпа­дает с исход­ным набором. Спра­вед­лива следу­ющая теоре­ма.

Теорема 4.1. Пусть  k-блочный элемент скобочного ряда разложен на  sk  расши­рен­ных блоков с индек­сами  i1, i2, ... , is. Тогда индекс исход­ного элемента  i0  равен сумме индек­сов расши­ренных блоков за вычетом величи­ны  s−1, т.е.

i0 = i1 + i2 + . . . + is − (s−1)
(4.2)

Д о к а з а т е л ь с т в о.  Обозначим вычитаемое значение  Δ= s−1. Сначала рассмотрим три­виаль­ное поэле­мен­тное разло­жение, т.е. все расши­ренные блоки в разложении прос­тые и, следо­ватель­но, s= k. В случае  k=1 спра­ведли­вость теоремы оче­вид­на, и  Δ= 0. Рассмот­рим двух­блоч­ный элемент скобоч­ного ряда. Чтобы "пробе­жать" по линей­ке ряда от левого (более длин­ного) расши­рен­ного блока до набора-роди­теля, надо пере­брать число элемен­тов, равное индек­су второго (корот­кого) расши­рен­ного блока за выче­том 1. Поэтому индекс двухблоч­ного набора меньше суммы индек­сов обоих рас­ши­ренных блоков на вели­чину   Δ= 1. Далее дока­зываем по индук­ции, рассмат­ривая в разло­жении каждого  i-блоч­ного набора (2 < ik) также два расши­ренных блока. Первый блок группо­вой, в нем собра­ны все роди­тель­ские блоки кроме одно­го. Индекс группо­вого блока равен сумме индек­сов простых  i−1 расши­ренных блоков за выче­том  Δ= (i−1) − 1. Подк­лю­чая к груп­повому блоку прос­той расши­ренный блок, мы добав­ляем к индексной сумме индекс этого блока и однов­ремен­но увели­чиваем на еди­ницу вычи­таемое   Δ= (i−1) − 1 + 1 = i−1. Таким обра­зом, для три­виаль­ного поэле­мент­ного разло­жения много­блоч­ного набора теорема верна.

Пусть в разложении  k-блочного набора содержится по мень­шей мере один груп­повой блок, т.е.  s < k. Вер­немся к триви­аль­ному поэле­мент­ному разло­жению и распи­шем индекс набо­ра-ро­дите­ля через сумму инде­ксов прос­тых расши­ренных блоков с разбив­кой  Δ  на еди­ницы:

i0 = i1 + (−1) + i2 + (−1) + . . . + (−1) + ik
(4.3)

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

Равенство (4.2) назовем индексным уравнением разложения много­блоч­ного набора. Урав­нение, экви­вален­тное индекс­ному, можно запи­сать и на уровне элемен­тов скобоч­ного ряда. Обоз­начим скобоч­ный ряд  B = {b}.  Нижний индекс будем исполь­зовать для указа­ния фикси­рованных элемен­тов ряда или скобочных конс­тант (аналог число­вых конс­тант нату­раль­ного ряда), напри­мер,  b1= "0",  b10= "(000)",  b110= "()00()0" и т.д. Обра­тим внима­ние, подобные равен­ства следует рассмат­ривать как тожде­ства, пос­кольку здесь и элементы ряда и литералы (скобоч­ные набо­ры) явля­ются конс­тан­тами. При указа­нии лите­ралов кавычки для крат­кости иногда будем опус­кать.

Верхний индекс будем использовать для обозначения скобоч­ных переменных (аналог цело­числен­ных пере­мен­ных). Пере­пишем урав­нение (4.2) в следу­ющем виде:

b(0) = b(1)b(2)⊕ . . . ⊕ b(s),
(4.4)

где переменной  b(j) соот­ветст­вует индекс  ij. Очевидно, опера­ция сложения набо­ров  ⊕  как и обычное ариф­мети­ческое сложе­ние ком­мута­тивна и ассо­циа­тивна. Индек­сное урав­нение (4.2), а сле­дова­тель­но, и скобоч­ное урав­не­ние (4.4) можно разре­шить относи­тельно произ­воль­ного слага­емого суммы. При этом в скобоч­ном варианте будем исполь­зовать опера­цию вычи­тания набо­ров  ⊖  (ана­лог арифме­тичес­кого вычи­тания).

Пример 4.2. Обратимся к таблице из раздела 3. Максимальный элемент 7-го диапа­зона скобоч­ного ряда равен  b127= ()()()0 (здесь ин­декс 127 – 7-ое число Моц­кина). Этот макси­мум разла­гается на три прос­тых расши­рен­ных блока:  b107= ()00000,  b18= ()000,  b4= ()0. В резуль­тате для дан­ного част­ного случая индек­сное урав­нение разложения становится тож­дест­вом, подт­верж­дающим теорему:  127 = 107 + 18 + 4 − (3 − 1), или, используя числа Моцкина,  M7 = 107 + 18 + M3 − 2, или, исполь­зуя скобоч­ные конс­танты,  b127= b107b18b4. Заметим, решая скобочное уравне­ние  ()00000 = ()()()0 ⊖ ()()0, можно сразу полу­чить индекс результата:  M7M5+ (2−1) = 127−21+1 = 107.

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

Обратимся к скобочным уравнениям. Рассмотрим элемент скобочного ряда "()00...0" дли­ны  k, который опре­деля­ется как раз­ность  k-мак­си­мума и  (k−2)-мак­симума. Этот первый (левый) прос­той расши­ренный блок  k-мак­симума имеет такую же длину кода, поэтому рас­поло­жен на линейке ряда правее  (k−1)-мак­симума, и по срав­нению с дру­гими расши­рен­ными бло­ками дли­ны  k  наибо­лее удален от  k-мак­си­мума (соот­ветст­венно, наибо­лее приб­лижен к макси­муму диапа­зона  k−1). Индекс такого расши­рен­ного блока равен  MkMk-2+ 1. В ре­зуль­тате полу­чаем произ­водное число Моцкина. Нетрудно прове­рить, рассмот­ренный элемент делит интер­вал на линейке ряда между  (k−1)-мак­симумом и  k-мак­симумом в соот­ноше­нии при­мерно 3:1.

C каждым числом  Mk связано семейство (множество) производных чисел Моцкина, которые индек­сируют производные скобоч­ные наборы (производные слова Моцкина) длины  k. В про­извод­ных набо­рах все пар­ные скобки смеж­ные. Оче­видно, все расши­ренные блоки  k-мак­симума, имеющие длину  k, явля­ются произ­вод­ными набо­рами. Коли­чество таких бло­ков рав­но  2k/2⌋−1. Однако, не все произ­водные набо­ры явля­ются расши­рен­ными блоками  k-мак­си­мума.

Пример 4.3. Составим множество производных чисел Моцкина для  M8 = 323, и выбе­рем все элементы скобоч­ного ряда, которые индек­сиру­ются этими чис­лами. Нас инте­ресуют наборы длины 8 со смеж­ными пар­ными скоб­ками. Таких произ­водных наборов оказа­лось 13, вклю­чая макси­мум 8-го диапа­зона. Ниже в таб­лице соб­раны произ­водные числа для  M8, индек­сируемые наборы, соот­ветст­вующие скобоч­ные и индек­сные выра­жения.

273 ()000000 ()()()() ⊖ ()()() M8 − (M6 − 1) = 323− 51 + 1 = 273
274 ()0000() ()000000 ⊕ () 273 + (M2 − 1) = 273 + 2 − 1 = 274
276 ()000()0 ()000000 ⊕ ()0 273 + (M3 − 1) = 273 + 4 − 1 = 276
280 ()00()00 ()000000 ⊕ ()() ⊖ () 273 + (M4 − 1) − (M2 − 1) = 273 + 9 − 1 − 2 + 1 = 280
281 ()00()() ()000000 ⊕ ()() 273 + (M4 − 1) = 273 + 9 − 1 = 281
290 ()0()000 ()000000 ⊕ ()()0 ⊖ ()0 273 + (M5 − 1) − (M3 − 1) = 273 + 21 − 1 − 4 + 1 = 290
291 ()0()0() ()0()000 ⊕ () 290 + (M2 − 1) = 290 + 2 − 1 = 291
293 ()0()()0 ()0()000 ⊕ ()0 290 + (M3 − 1) = 290 + 4 − 1 = 293
315 ()()0000 ()()()() ⊖ ()() M8 − (M4 − 1) = 323 − 9 + 1 = 315
316 ()()00() ()()0000 ⊕ () 315 + (M2 − 1) = 315 + 2 − 1 = 316
318 ()()0()0 ()()0000 ⊕ ()0 315 + (M3 − 1) = 315 + 4 − 1 = 318
322 ()()()00 ()()()() ⊖ () M8 − (M2 − 1) = 323 − 2 + 1 = 322
323 ()()()() ()()()() 323

Обратим внимание, из 13-ти производных слов Моцкина пять не являются расширенными блоками максимума 8-го диапазона, это наборы с индексами 276, 290, 291, 293, 318.  

 

<<   Скобочный ряд  ||   Сервис on-line   >>