No Image

Число правильных скобочных последовательностей

СОДЕРЖАНИЕ
6 просмотров
10 марта 2020

[ последовательностей ]

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

Рассмотрим одну классическую задачу, в которой возникает последовательность чисел Каталана, выведем производящую функцию и формулу

Правильные скобочные последовательности

Сколько существует правильных скобочных последовательностей, состоящих из 2n скобок ( n открывающих и n закрывающих)? Например, если n=3 , то таких последовательностей всего 5:

Пусть Cn — ответ к нашей задаче. Положим по определению C=1 . Очевидно, что любая правильная скобочная последовательность начинается с открывающей скобки. Между ней и соответствующей ей закрывающей скобкой можно расположить правильную последовательность из 2k скобок (где 0≤k ):

Таким образом, чтобы узнать количество правильных скобочных последовательностей из 2n скобок, нужно перебрать все возможные способы расположить 2k скобок в зоне между красными скобками (рис) и 2(n-k-1) скобок после неё. Получаем рекуррентное соотношение:

Это соотношение нужно резрешить и вывести общую формулу. О решении рекуррентных соотношений подробнее говорилось здесь. Будем искать производящую функцию в виде

В рекуррентном соотношении домножаем Cn на z n :

Выполняя суммирования по всем n , получаем

Обратите внимание, что сумма в этом выражении ни что иное как свёртка производящих функций:

Значит, окончательное уравнение для производящей функции будет иметь вид

или, что то же самое,

Из этого квадратного уравнения легко найти G(z) :

Теперь нужно определиться, какой из двух корней нас интересует. Заметим, что G(z) должно быть равно 1 при z=0 , следовательно, нам подходит корень со знаком минус:

Чтобы проверить это, нужно перейти в этом выражении к пределу при z→0 .

Осталось разложить в ряд полученное выражение (здесь мы пользуемся расширенными биномиальными коэффициентами):

Откуда получается, что

Выведенная формула даёт ещё одно, более простое рекуррентное соотношение:

В одном из упражнений будет предложено показать, что

Язык Дика

Правильные скобочные последовательности имеют и другое название: слова Дика (Dyck). В случае, когда рассматриваются скобки только одного вида, слова Дика порождаются следующей контекстно-свободной грамматикой

Здесь ε — пустое слово. Эта грамматика указывает на то, что все правильные скобочные последовательности (ПСП) строятся по одному и тому же правилу: либо ПСП — это пустое слово, либо ПСП, взятая в скобки, за которыми снова идет ПСП.

Асимптотика

Рассмотрим поведение последовательности чисел Каталана на бесконечности. Для определения главного члена асимптотики воспользуемся формулой Стирлинга

Теперь преобразуем выражение следующим образом:

Вспомнив один из замечательных пределов, можно заменить выражение со скобками на 1/e , окончательно записав

Блуждания на полупрямой

Ещё одна классическая задача, в которой встречаются числа Каталана. Рассмотрим прямую. Некоторый объект находится на прямой в позиции 0. Он может за один шаг переместиться либо влево, либо вправо на одну позицию. Сколькими способами можно переместиться из начальной позиции в неё же за 2n шагов так, чтобы ни разу не оказаться левее нуля?

Сначала рассмотрим случай, когда нулевую отметку можно пересекать (задача о блуждании на прямой). В этом случае нужно совершить 2n шагов, n из которых делаются влево и n — вправо (в любой последовательности). Обозначим символом 0 движение влево, а символом 1 движение вправо. Сколько существует последовательностей из нулей и единиц, в которых нулей и единиц ровно по n ? Это число сочетаний:

Читайте также:  Dell inspiron 15 7567 отзывы

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

Выводится производящая функция и формула для чисел Каталана. Выводится асимптотика. Рассматриваются примеры задач, в которых встречаются эти числа.

Чего больше: правильных скобочных последовательностей из n пар скобок или последовательностей (x1, . . . , x2n) с элементами ±1 таких, что ∑︀xi = 0 (от i=1 до 2n)

задан 3 Ноя ’19 22:44

Заменим ( на +1 и ) на -1. Сумма будет равна 0 для правильной расстановки. При n>=1 возможна последовательность -1, 1 с нулевой суммой, которая не соответствует правильной расстановки. Из этого делаем выводы.

Здравствуйте

Математика – это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Содержание

Определения [ править ]

Определение:
Скобочная последовательность (анлг. Bracket Sequences) — класс комбинаторных объектов, представляющих собой последовательность скобочных символов.

Примеры скобочных последовательностей

  • [math](())))([/math]
  • [math])()()))()(()())[/math]
Определение:
Правильная скобочная последовательность (анлг. Correct Bracket Sequences) — частный случай скобочной последовательности, определяющийся следующими образами:

  • [math]varepsilon[/math] (пустая строка) есть правильная скобочная последовательность;
  • пусть [math]S[/math] — правильная скобочная последовательность, тогда [math](S)[/math] есть правильная скобочная последовательность;
  • пусть [math]S1[/math] , [math]S2[/math] — правильные скобочные последовательности, тогда [math]S1S2[/math] есть правильная скобочная последовательность;

Примеры правильных скобочный последовательностей

Алгоритм проверки правильности скобочной последовательности [ править ]

Пусть нам дана скобочная последовательность, записанная в строку [math]s[/math] . Возьмем переменную [math]mathtt[/math] , [math]mathtt = 0[/math] , в которой мы будем поддерживать баланс. Будем последовательно перебирать все символы этой строки. Если мы встречаем открывающуюся скобку, то увеличиваем [math]mathtt[/math] на [math]1[/math] , закрывающую — уменьшаем на [math]1[/math] . Если на протяжении всего перебора [math]mathtt[/math] было неотрицательным (не встречалось закрывающих скобок, для которых не было соответствующих открывающих) и после завершения осталось нулем (все открывающие скобки закрыты, при этом нет лишних закрытых скобок), то скобочная последовательность правильна.

Псевдокод [ править ]

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

Примеры скобочных последовательностей с несколькими типами скобок [ править ]

  • [math]()[()]<()()[]>[/math] — верно
  • [math][(]<>)[/math] — неверно

В этом случае для проверки надо будет использовать стек.

Лексикографический порядок правильных скобочных последовательностей [ править ]

Для того, чтобы определить лексикографический порядок для правильных скобочных последовательностей, надо установить порядок на алфавите, например так [math]( lt )[/math] . Для последовательностей с разным типом скобок надо определять свой порядок в зависимости от числа скобок, причем любая открывающаяся скобка должна быть меньше закрывающейся, например [math]( lt [ lt ) lt ][/math] .

Читайте также:  Системная ошибка msvcp120 dll что делать

Примеры лексикографического порядка для [math]n[/math] и [math]k[/math] , где [math]n[/math] — число открывающихся скобок, а [math]k[/math] — число видов скобок [ править ]

[math]n = 3[/math] [math]k = 1[/math]
[math]((()))[/math] [math](()())[/math] [math](())()[/math] [math]()(())[/math] [math]()()()[/math]
[math]n = 2[/math] [math]k = 2[/math]
[math]()[][/math] [math]([])[/math] [math][()][/math] [math][]()[/math]

Алгоритмы генерации [ править ]

Рекурсивный алгоритм получения лексикографического порядка [ править ]

Пусть нам известно число [math]n[/math] . Надо вывести все правильные скобочные последовательности в лексикографическом порядке с [math]n[/math] открывающимися скобками:

Для запуска алгоритма необходимо сделать вызов [math]mathrm(n[/math] , [math]0[/math] , [math]0[/math] , [math]"")[/math] .

  • [math] mathtt[/math] — строка, в которой мы считаем ответ
  • [math] mathtt[/math] – количество открывающих скобок в данный момент
  • [math] mathtt[/math] – количество закрывающих скобок в данный момент

Если есть возможность поставить открывающую скобку, то мы ставим её. Аналогично после этого если есть возможность поставить закрывающую скобку, то после этого мы ставим и её.
Таким образом строки будут выведены в лексографическом порядке, так как сначала мы мы пытаемся поставить открывающую скобку. При этом мы перебираем все возможные варианты последующих скобок для каждого возможного префикса [math]mathtt[/math] , а следовательно в результате получаем все возможножные правильные скобочные последовательности

Генерация следующей скобочной последовательности [ править ]

Пусть нам известна строка [math]s[/math] , представляющая собой правильную скобочную последовательность. Нам необходимо вывести следующую скобочную последовательность, а если ее нет, то вывести "No solution". Чтобы получить следующую скобочную последовательность надо найти последнюю открывающуюся скобку, которую можно заменить (на этом месте мы можем поставить закрывающую скобку, не нарушив условия правильности скобочной последовательности, то есть на протяжении проверки на правильность counter должен быть неотрицательным), заменить ее на закрывающуюся, а оставшиеся в конце скобки (если они есть) заменить на минимально возможную последовательность скобок:

Получение лексикографического порядка [ править ]

Пусть нам известно число [math]n[/math] . Надо вывести все правильные скобочные последовательности в лексикографическом порядке с [math]n[/math] открывающимися скобками:

Также с помощью этого алгоритма можно получить скобочную последовательность по номеру и номер по скобочной последовательности, добавив сравнение с нужной последовательностью и счетчик. Но это далеко не самый оптимальный алгоритм для подобного типа задач и он не будет нормально работать для больших [math]n[/math] .

Получение номера последовательности [ править ]

Пусть [math]n[/math] — количество пар скобок в последовательности. Требуется по заданной правильной скобочной последовательности найти её номер в списке лексикографически упорядоченных правильных скобочных последовательностей.

Научимся считать вспомогательную динамику [math]d[i][j][/math] , где [math]i[/math] — длина скобочной последовательности (она "полуправильная": всякой закрывающей скобке соответствует парная открывающая, но не все открытые скобки закрыты), [math]j[/math] — баланс (т.е. разность между количеством открывающих и закрывающих скобок), [math]d[i][j][/math] — количество таких последовательностей. При подсчёте этой динамики мы считаем, что скобки бывают только одного типа.

Считать эту динамику можно следующим образом. Пусть [math]d[i][j][/math] — величина, которую мы хотим посчитать. Если [math]i = 0[/math] , то ответ понятен сразу: [math]d[0][0] = 1[/math] , все остальные [math]d[0][j] = 0[/math] . Пусть теперь [math]i gt 0[/math] , тогда переберём, чему мог быть равен последний символ этой последовательности. Если он был равен [math]'(‘[/math] , то до этого символа мы находились в состоянии [math](i-1,j-1)[/math] . Если он был равен [math]’)'[/math] , то предыдущим было состояние [math](i-1,j+1)[/math] . Таким образом, получаем формулу:

Читайте также:  Программа для ретуширования лица на фото

(считается, что все значения [math]d[i][j][/math] при отрицательном [math]j[/math] равны нулю). Таким образом, эту динамику мы можем посчитать за [math]O(n^2)[/math] .

Перейдём теперь к решению самой задачи. Сначала пусть допустимы только скобки одного типа:

Пусть теперь разрешены скобки [math]k[/math] типов. Тогда при рассмотрении текущего символа [math]s[i][/math] до пересчёта [math]
m depth[/math] мы должны перебирать все скобки, которые меньше текущего символа в установленном ранее порядке, пробовать ставить эту скобку в текущую позицию (получая тем самым новый баланс [math]
m ndepth =
m depth pm 1[/math] ), и прибавлять к ответу количество соответствующих "хвостов" — завершений (которые имеют длину [math]2n – i – 1[/math] , баланс [math]
m ndepth[/math] и [math]k[/math] типов скобок). Утверждается, что формула для этого количества имеет вид:

Эта формула выводится из следующих соображений. Сначала мы "забываем" про то, что скобки бывают нескольких типов, и просто берём ответ из [math]d[2n – i – 1][<
m ndepth>] [/math] (аналогично случаю с одним типом скобок, где мы увеличивали [math]depth[/math] на [math]1[/math] , если скобка открывающая, и уменьшали на [math]1[/math] , если закрывающая, [math]ndepth = depth + 1[/math] , если мы пробуем поставить открывающую скобку, и [math]ndepth = depth – 1[/math] , если закрывающую). Теперь посчитаем, как изменится ответ из-за наличия [math]k[/math] типов скобок. У нас имеется [math]2n – i – 1[/math] неопределённых позиций, из которых [math]
m ndepth[/math] являются скобками, закрывающими какие-то из открытых ранее, — значит, тип таких скобок мы варьировать не можем. А вот все остальные скобки (а их будет [math](2n – i – 1 – <
m ndepth>) / 2[/math] пар) могут быть любого из [math]k[/math] типов, поэтому ответ умножается на эту степень числа [math]k[/math] .

Сложность данного алгоритма [math]O(n^2 + n cdot k)[/math] .

Получение k-й последовательности [ править ]

Пусть [math]n[/math] — количество пар скобок в последовательности. В данной задаче по заданному [math]k[/math] требуется найти [math]k[/math] -ую правильную скобочную последовательность в списке лексикографически упорядоченных последовательностей.

Как и в предыдущем разделе, посчитаем динамику [math]d[i][j][/math] — количество правильных скобочных последовательностей длины [math]i[/math] с балансом [math]j[/math] .

Пусть сначала допустимы только скобки одного типа:

Пусть теперь разрешён не один, а [math]k[/math] типов скобок. Тогда алгоритм решения будет отличаться от предыдущего случая только тем, что мы должны домножать значение [math]d[i + 1][
m ndepth][/math] на величину [math]k^<(2n – i – 1 –
m ndepth) / 2>[/math] , чтобы учесть, что в этом остатке могли быть скобки различных типов, а парных скобок в этом остатке будет только [math]2n – i – 1 –
m ndepth[/math] , поскольку [math]
m ndepth[/math] скобок являются закрывающими для открывающих скобок, находящихся вне этого остатка (а потому их типы мы варьировать не можем).

Сложность данного алгоритма [math]O(n^2 + n cdot k)[/math] .

Количество правильных скобочных последовательностей [ править ]

Количество правильных скобочных последовательностей со скобками одного типа совпадает с числами Каталана.

Комментировать
6 просмотров
Комментариев нет, будьте первым кто его оставит

Это интересно
No Image Компьютеры
0 комментариев
No Image Компьютеры
0 комментариев
No Image Компьютеры
0 комментариев
No Image Компьютеры
0 комментариев
Adblock detector