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

      3. Скобочный ряд

Упорядоченный список нормализованных слов Моцкина назовем скобочным рядом. Каждый набор скобок (далее элемент ряда) разме­щается на опреде­ленном месте. Напри­мер, набор  ((000)0(000)00)00  из первого раздела зани­мает пози­цию под номером (индек­сом) 1418009. И это легко проверя­ется с помощью прила­гае­мого инте­рак­тив­ного сер­виса. Читатель в режиме on-line может полу­чить элементы скобоч­ного ряда в произ­воль­ном диа­па­зоне, указав началь­ный индекс и коли­чество эле­ментов.

Ниже в таблице приведены первые 130 элементов скобочного ряда (пустой набор опускаем, индек­сация начина­ется с единицы). Некоторые элементы для лучшей ориен­тации пронуме­рованы, закра­шенные ячейки таблицы связаны с числами Моцкина.

Вернемся к десятичным натуральным числам. В каждом  k-разрядном диапазоне натураль­ного ряда есть мини­маль­ный элемент (единица с  k−1 ну­лями) и макси­мальный элемент, состо­ящий из  k  девяток. Длина (мощ­ность) каждого диапа­зона опреде­ляется разно­стью между макси­мальными элемен­тами теку­щего и преды­ду­щего диапа­зонов. С умень­шением разряд­ности макси­мальный эле­мент теряет девятки, мини­маль­ный – нули. C умень­шением разряд­ности на одну единицу длина диапа­зона снижа­ется десяти­кратно (осно­вание системы счисле­ния). В низшем однораз­рядном диа­па­зо­не минималь­ный элемент оста­ется без нулей.

Соответственно и для скобочного ряда в каждом знаковом диапазоне есть минималь­ный элемент (минимум) и макси­мальный эле­мент (максимум). В чет­ном  k-зна­ковом диапазоне (далее  k-диа­па­зоне) максимум пред­ставляет собой набор смежных парных скобок без нулей, число пар рав­но k/2. Напри­мер, в нашей таблице макси­мальные элементы с индек­сами 2, 9, 51 пред­став­ляют диапа­зоны соот­ветст­венно 2, 4, 6. Если к коду макси­мального элемента четного диапа­зона припи­сать 0, то получим макси­мум следу­ющего нечет­ного диапа­зона. Обратно, если в мак­си­мальном элементе четного диапа­зона правые смежные скобки заменить нулем, то получим максимум пред­шест­вующего нечет­ного диапа­зона. Таким образом, максимумы могут быть двух видов и одно­значно опреде­ляются длиной набора скобок. В при­ве­денную таблицу попали семь макси­мальных элементов скобочного ряда (закра­шенные ячейки).

Минимумы одинаковы практически во всех  k-диапазонах и имеют следую­щий вид: внешние парные скоб­ки охва­тывают группу смежных нулей в коли­честве  k−2. В нашей таблице это элементы с индексами 2, 3, 5, 10, 22, 52, 128. С умень­шением  k число нулей в мини­мальных элементах сокра­щается, и уже в двух­зна­ковом диапа­зоне внут­рен­них нулей нет, мини­мум совпадает с макси­мумом, в итоге в этом диапа­зоне только один эле­мент. В одно­знако­вом диапа­зоне для скобок места нет, здесь единст­венный эле­мент "0" с индексом 1, который одновременно и мини­мум и макси­мум. Далее под  k-мак­симумом (k-ми­нимумом) будем пони­мать максимум (минимум)  k-диа­пазона скобоч­ного ряда.

Поясним, для чего так подробно описывается, казалось бы, очевидное, зачем "препа­рируется" ско­бочный ряд. Каждому элементу скобочного ряда прис­воен уникаль­ный индекс. Можно сказать иначе: сущест­вует взаимно-од­нознач­ное соот­ветс­твие (биек­ция) между скобоч­ным рядом и нату­ральным рядом. Выде­ленные цветом элемен­ты в таблице имеют прямое отно­шение к числам Моцкина. Нетрудно видеть, индекс  k-мак­симума равен коли­честву всех слов Моцкина дли­ной  k, или суммар­ному числу нормализованных слов Моцкина длиной 1, 2, …, k  (т.е. сумме длин соот­ветст­вующих диапа­зонов скобоч­ного ряда). И этот индекс равен  k-му числу Моцкина (да­лее Mk ). Собст­венно, это следует непос­редст­венно из опреде­ления чисел Моцкина. Очевидно, индекс  k-ми­ни­мума равен  Mk−1+1.

Максимальному элементу  k-диапазона скобочного ряда взаимно-одноз­начно соответ­ству­ет  k-ое число последо­ватель­ности Моцкина. В таблице семь макси­мумов с индексами 1, 2, 4, 9, 21, 51, 127, и это семь чисел Моцкина  M1÷ M7. Опреде­лимся с нулевым элементом  M0, который, напомним, сог­ласно OEIS A001006 равен 1.

Нулевому элементу последовательности Моцкина должен соответ­ствовать пустой 0-набор или нуле­вой элемент скобоч­ного ряда. (Обратим внимание, следует различать в скобочном ряде элемент "0" с индексом 1, и нулевой элемент, пустой набор с индексом 0.) Это означает, что в начало скобоч­ного ряда встра­ивается допол­нительный вирту­альный 0-диа­па­зон, состо­ящий, естес­твенно, из единст­венного элемента без скобок и нулей. Этот элемент является одно­вре­менно минимумом и максимумом, и соответственно, длина (мощ­ность) такого вир­ту­аль­ного диапазона равна 1. Поясним, почему это пробле­матично, а по всей види­мости, и невоз­можно.

Так же как и в натуральном ряде, длина  Lk каждого  k-ди­апа­зона скобоч­ного ряда равна раз­ности индек­сов  k-мак­симума и  (k−1)-мак­симума, или  Lk= MkMk-1. Эта вели­чина сни­жа­ется при умень­ше­нии k, и только диапа­зоны 1 и 2 имеют одина­ковую мощность:  L1= L2= 1. Отсюда полу­чаем значение индекса для макси­мума вирту­ального диапа­зона:  M0= M1L1= 1 − 1 = 0. Следова­тельно, 0-диа­пазон пуст (пусты и все пред­шеству­ющие диапа­зоны, если бы таковые были в скобоч­ном ряде), и мы снова приходим к последо­ватель­ности (1.3). Таким образом, мы исклю­чаем из скобоч­ного ряда пус­той эле­мент −  0-на­бор, но можем гово­рить о пустом 0-диа­па­зоне скобоч­ного ряда (пустое множе­ство элемен­тов нулевой длины).

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

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

1, 2, 4, 9, 21, 51, 127, 323, 835, 2188, 5798, ...
(3.1)

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

Ряд, в котором соблюдаются приведенные условия, назовем рядом (после­дова­тель­ностью) лексико­графичес­кого типа, или лексико­графи­чес­ким рядом. Естественно, скобоч­ный ряд и нату­раль­ный ряд не единственные подобного типа. Напри­мер, если мы выст­роим все нормали­зованные ПСПРН по тем же правилам, что и элементы скобоч­ного ряда, то также получим лекси­когра­фичес­кий ряд. В та­ком расши­ренном ско­боч­ном ряде длина (мощ­ность)  k-диа­па­зона равна  k-му числу Моцкина, а индекс  k-мак­симума равен  M1+ M2+ ... + Mk. Напом­ним, в нашем скобоч­ном ряде длина k-диа­па­зона равна  MkMk-1  (M0= 0), индекс  k-мак­симума ра­вен  Mk.

 

<<   Числа и скобки   ||   Операции на скобках  >>