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

            1. Введение

В дискретной математике особый интерес представляют скобочные после­дова­тель­ности. Если, к при­ме­ру, в ариф­мети­ческом выра­жении  y×[(12−z)/(a+b)−8]+345  операнды и знаки операций заме­нить нуля­ми, а все скобки заме­нить на круглые, то полу­чим набор из нулей и скобок

00((000)0(000)00)00
(1.1)

Нас будут интересовать слова Моцкина, т.е. правильные скобочные последовательности, разрежен­ные нулями (далее ПСПРН или скобоч­ные наборы), в которых соб­люда­ются следу­ющие два условия:

Скобки каждого скобочного набора однозначно разбиваются на пары разно­направ­лен­ных скобок, или пар­ные скобки таким образом, что внутри каждой пары образу­ется также ПСПРН. Парные скобки смеж­ные, если не содер­жат внутри никаких знаков. Очевидно, группа подряд идущих ПСПРН также явля­ется словом Моцкина. Можно сказать, каждое слово Моцкина собира­ется из "строи­тельных кирпи­чиков" трех видов: ноль, левая скобка и правая скобка. Самая прос­тая ПСПРН это набор без скобок, в кото­ром только нули.

Как и во всех перечислительных задачах комбинаторики для ПСПРН подсчи­тыва­ется число слов Моцкина фикси­рован­ной длины. Например, возможны лишь два набора по два знака, это − "00" и "( )". Трех­значных ско­боч­ных набо­ров уже четыре: "000", "0( )", "(0)", "( )0". Первые два насле­дуются от двухзначных после добав­ления нуля в начале кода, другие два набора уникальные. Анало­гично, все трех­знач­ные ско­бочные наборы на осно­вании того же правила насле­дования пере­ходят (с до­полни­тельным нулем в начале кода) в список четырех­значных. И этот список допол­няется пятью уникаль­ными четырех­значными набо­рами "(00)", "(0)0", "(( ))", "( )00", "( )( )". Естест­венно, эту проце­дуру можно продол­жать.

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

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

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

Пример 1.1. В семействе 2-наборов нулевой элемент "00" унаследован, вто­рой элемент "( )" уникальный. Попро­буем разоб­раться с единст­венным элементом множе­ства 1-на­боров: элемент "0" унасле­дован или уникаль­ный? К пустому набору можно приписать ноль, и мы получим унасле­дован­ный 1-набор. В этом случае уникаль­ных 1-на­боров нет, и можно считать, что мы опреде­лились с типом элемен­та "0". Однако, с другой стороны, при увели­чении длины скобоч­ных наборов их число всегда растет за счет новых уникаль­ных эле­мен­тов. И тог­да, если считать эле­мент "0" уникаль­ным, то во множе­стве 1-на­боров не ока­жется унасле­дован­ных элемен­тов. Это озна­чает, что началь­ный элемент после­дова­тель­ности A001006 сле­дует обну­лить.

Рассмотрим пустой скобочный набор с другой точки зрения. Мы отмечали, что в ПСПРН пар­ные смеж­ные скобки не содер­жат никаких зна­ков, но можно сказать и так: внутри смежных парных скобок нахо­дится 0-на­бор. Собст­венно, таким же образом можно "обнару­жить" 0-на­бор в любом месте произ­вольной скобочной после­дова­тель­ности. Более того, можно утвер­ждать, что в ПСПРН за каждым 0-на­бором сле­дует любое количе­ство пустых набо­ров. Вот самый прос­той пример: если обоз­начить пустой набор ∅, то все скобоч­ные после­дова­тель­ности вида  ∅, ∅∅, ∅∅∅  и т.д. пред­став­ляют собой ПСПРН и все имеют длину 0, т.е. явля­ются 0-на­борами. И сколь­ко же тогда набира­ется 0-на­боров?

Таким образом, пустой набор легко тиражируется в произвольной позиции каждого скобоч­ного набора, не изме­няя при этом длину послед­него. Из этого сле­дует, что числа Моцки­на в последо­ватель­ности A001006 неверны. Но если обну­лить началь­ное число Моцкина (т.е. уда­лить 0-на­бор из числа ПСПРН), то осталь­ные числа Моцкина сохра­няют свои значе­ния. Скор­ректи­руем в связи с этим последо­ватель­ность (1.2):

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

Обычно в прикладных задачах рассматривается множество ПСПРН фикси­рован­ной длины. пример И это, на первый взгляд, логично, посколь­ку фикси­рованы размеры объек­тов, к кото­рым приме­няется матема­тичес­кая модель. Напри­мер, скобоч­ная модель исполь­зу­ет­ся при под­счете числа Гамиль­тоно­вых цик­лов на прямо­уголь­ной решетке. Здесь длина скобоч­ных наборов равна ширине решетки. Другая реали­зация ПСПРН связана с путями на плос­кости. На ри­сунке показан путь, постро­енный для ско­боч­ного набо­ра (1.1). В та­ком пути учас­ток подъе­ма соот­ветс­т­вует левой скобке, спад − пра­вой скобке, гори­зонталь­ные участки связаны с нулями.

Зададимся вопросом, что мешает отказаться от фиксирован­ной длины ПСПРН? Фиксируя длину наборов, мы каждый раз имеем дело с конкрет­ным конечным множе­ством скобочных после­дова­тель­нос­тей. Мощ­ность такого множе­ства опреде­ляется соответ­ствующим чис­лом Моцкина. Что полу­чится, если уда­лить во всех наборах беспо­лезные лиди­ру­ющие (начальные) нули? Беспо­лезные хотя бы в том смысле, что при необ­ходи­мости их легко можно восста­новить. Назовем процедуру удаления лидирующих нулей нормализацией слов Моцкина. К примеру, скобочный набор (1.1) в усечен­ном или нормали­зованном виде выгля­дит следу­ющим образом:

((000)0(000)00)00

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

                            ||   Числа и скобки   >>