1. Последовательности

Еремин Геннадий
опубликовано 6 May 2015 19:05

 

Брокгауз и Ефрон дают такое определения ряда:

Определение 1.1. Ряд есть после­довательность элементов, составленных по какому-нибудь закону. Если дан ряд, то это значит, что указан закон, при помощи которого можно составить сколько угодно элементов ряда.

По Брокгаузу и Ефрону элементами ряда могут быть числа, функции и действия.

Таким образом, ряд – это последовательность, совокупность или набор (конечный или бесконечный) однотипных элементов (объектов), которые выстраиваются в линию в соответствии с некоторым законом или правилами. И эти правила разработаны и действуют одновременно и одинаково для всех элементов данного ряда. Очевидно, ничто не мешает нам расширить список типов элементов в определении Брокгауза и Ефрона. Включим в этот список и скобочные последовательности.

В дальнейшем будем придерживаться именно такого определения ряда, и вот по какой причине. Многие авторы различают понятия числовая последовательность и числовой ряд. Под числовым рядом обычно понимают сумму элементов соответствующей числовой последова­тельности. Сошлемся здесь на «увесистый» учебно-методический сайт  Единое окно доступа к образовательным ресурсам.

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

Натуральный ряд

Обратимся к натуральному ряду, наиболее известной, наиболее цитируемой и самой простой числовой последовательности:

    \[[0,]\: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, \ldots  \]

Ряд может начинаться с 0 или 1, иначе говоря, нуль может включаться в натуральный ряд, а может – и нет. Логично назвать нулевой элемент беглым нулем. Закон (или функция следования), по которому строится ряд, очень простой: значение последующего элемента на единицу больше предыдущего.

Среди математиков до сих пор нет согласия относительно нуля, хотя на дворе XXI-ый век. Многие зарубежные математические школы считают нуль натуральным числом (например, если используется теоретико-множественный подход), российские математики – нет.

Процитируем Википедию: «При определении через классы равномощных множеств ноль является натуральным числом по определению». Попробуем прояснить ситуацию с нулем или, скажем так, приведем свои, возможно, спорные соображения по данному поводу.

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

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

Конечно, натуральный ряд индексирует и самого себя, т.е. является самоиндекси­рующимся. В этом случае значение каждого элемента совпадает с его индексом. И если мы включаем 0 в натуральный ряд, то этому элементу автоматически должен присваиваться нулевой индекс, поскольку все положительные значения индексов использованы для других элементов ряда.

Выпишем произвольную последовательность с прямой индексацией элементов, т.е. каждому элементу присвоен и непосредственно указан конкретный уникальный (неповторяющийся) индекс:

    \[[a_0,] \:a_1, \;a_2, \;a_3, \;a_4, \;a_5, \;a_6,  \;a_7, \;a_8, \;a_9, \;a_{10}, \;a_{11}, \ldots\]

Элемент с индексом 0 может находиться в последовательности, а может и отсутствовать (снова налицо беглый элемент).

Напрашивается следующее

Утверждение 1.1. Если мы отождествляем натуральный ряд с семейством индексов элементов некоторой последовательности (что не только заманчиво, но и достаточно очевидно) и если в этой последовательности начальный элемент имеет нулевой индекс, то тогда мы просто обязаны считать ноль натуральным числом.

Для многих последовательностей элементы индексируются, начиная с нуля. В чис­ловых рядах элемент с индексом 0 может быть равен нулю или отличен от нуля. Например, в последовательности Фибоначчи (OEIS A000045) начальный элемент равен нулю. Для чисел Каталана (OEIS A000108) и чисел Моцкина (OEIS A001006) элемент с индексом 0 равен 1.

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

Лексикографический ряд

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

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

Каковы формальные признаки натурального ряда? Начнем с того, что в натуральном ряде нет повторяющихся объектов, отсюда первое условие LG-ряда.

Условие 1.1. В лексикографическом ряде все объекты уникальные.

Многие последовательности не удовлетворяют первому условию. Например, упоминавшиеся выше числа Фибоначчи, числа Каталана и числа Моцкина содержат в начале ряда повторяющиеся элементы.

В натуральном ряде все числа размещены (отсортированы) в порядке увеличения длины кода. Ряд начинается одноразрядными числами, затем следуют двухразрядные и т.д. Исходя из этого, сформулируем второе условие LG-ряда.

Условие 1.2. Объекты в лексикографическом ряде отсортированы в порядке возрастания длины кода.

В соответствии с условием 1.2 объекты лексикографического ряда распределяются по знаковым диапазонам. Ряд «нарезается» на отрезки-диапазоны, и  в каждом таком отрезке элементы имеют одинаковую длину кода. В дальнейшем множество элементов длины k будем называть k-диа­пазоном лексикографического ряда или просто k-диа­пазоном. 

В натуральном ряде элементы каждого знакового диапазона, т.е. числа одинаковой разрядности, также отсортированы. Элементы ряда составляются из знаков алфавита – цифр. Десять цифр выстраиваются по ранжиру в порядке возрастания весов, т.е. на множестве знаков алфавита имеем полный строгий порядок, исходя из неравенств  0<1<2<3<4<5<6<7<8<9. И в соответствии с этим порядком сортируются числа внутри каждого знакового диапазона. Оформим сказанное в форме следующего условия для LG-ряда.

Условие 1.3. В каждом знаковом диапазоне лексикографического ряда объекты отсортированы в лексикографическом порядке, т.е. в соответствии с полным строгим порядком, установленном на множестве знаков, из которых составляются объекты ряда.

Алгоритм сортировки объектов внутри знаковых диапазонов довольно прост. При сравнении двух элементов с кодами равной длины последовательно попарно сравниваются знаки, начиная с начала кода. И первое же несовпадение в какой-либо паре (а такой случай неизбежен, поскольку все объекты ряда уникальные) позволяет соотнести веса сравниваемых элементов.

Итак, в LG-ряде мы имеем двойную сортировку объектов. Внешняя сортировка расставляет элементы по длине кода, распределяет их по знаковым диапазонам. Внутренняя сортировка упорядочивает элементы внутри знаковых диапазонов. В каждом диапазоне есть минимальный и максимальный элементы. К примеру, в натуральном ряде минимальный элемент k-диапазона состоит из 1 и k-1 нулей, в максимальном элементе k девяток.

Таким образом, лексикографический  ряд – цепь. Иначе говоря, все объекты LG-ряда расставлены в соответствии со своими весами на линейке ряда, и логично считать мерой веса каждого объекта его индекс.

Присмотримся в натуральном ряде к знаку алфавита с минимальным весом – цифре 0. Ноль не пишется в начале целых чисел, код не начинается с нуля, за исключением единственного случая, когда 0 включен в натуральный ряд. И уж тем более элемент с минимальным весом не может тиражироваться в начале кода.

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

Мы готовы сформулировать последнее 4-ое условие для LG-ряда о запрете размещения и тиражирования знака с минимальным весом в начале кода объекта, но мешает одно обстоятельство.

В числовых рядах знаки алфавита формально не зависят друг от друга, цифры свободны и практически ничем не ограничены в использовании. Однако, в нечисловых последовательностях отдельные знаки алфавита, из которых составляются элементы ряда, могут быть несвободны, связаны друг с другом, образовывая связанные группы. Между знаками группы возможны специфические ограничения или жесткая связь. Знак алфавита из какой-либо связанной группы может иметь минимальный вес, и при этом может размещаться и тиражироваться в начале кода.

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

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

Итак, в алфавите слов Дика лишь два знака, и оба знака образуют единственную связанную группу. Свободных знаков в алфавите нет. Последовательность слов Дика удовлетворяет перечисленным выше условиям LG-ряда. И чтобы причислить такую последовательность к числу лексико­графических рядов,  придется в последнем условии особо оговорить символ с минимальным весом.

Условие 1.4. В лексикографическом ряде элемент с двумя и более знаками в коде не может начинаться свободным (несвязанным) символом, имеющим минимальный вес.

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

Ряд Дика

Для слов Дика одинаковой длины устанавливается лексикографический порядок, исходя из порядка на алфавите, а именно: левая скобка считается «меньше» правой или  “(” <  “)”. Количество слов Дика, в которых k пар скобок, равно числу Каталана c_k. Например, слова Дика с тремя парами скобок выстраиваются в цепочку из пяти элементов (c_3=5):

    \[((())), \;(()()), \;(())(), \;()(()), \;()()() .\]

Очевидно, (2n)-диапазон ряда (в словах n пар скобок) начинается одноблочным словом Дика ((\ldots())\ldots) и заканчивается словом Дика ()()\ldots(), состоящим из n блоков скобок.

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

    \[(), \;(()), \;()(), \;((())), \ldots\;()()(), \;(((()))), \ldots\]

Первым указано единственное слово Дика с одной парой скобок (первый диапазон или 1-диапазон), далее следуют два элемента с двумя парами скобок (2-диапазон) и т.д. В последовательности OEIS A000108 начальное число Каталана равно 1 и имеет индекс 0. И возникает вопрос: что делать с пустым словом длины 0? Очевидно, надо включать в начало ряда Дика дополнительный 0-диапазон, состоящий из единст­венного элемента – пустого слова.

В ряде Дика нет пустого слова, и так поступают практически всегда, когда перечисляют правильные скобочные последовательности, например, здесь (стр. 177). Более того, можно встретить укороченную последовательность чисел Каталана без начального элемента, например, как здесь. И это вполне объяснимо, все-таки интересны реальные скобочные наборы, слова, содержащие хотя бы одну пару скобок. В дальнейшем по возможности будем обходиться без пустого слова и, соответ­ственно, без числа Каталана с индексом 0.

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

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


<<<<<   Введение  ||  Начала динамики  >>>>>

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