212
правок
Изменения
→Задача расстановки скобок
закрывающих. Во-вторых, ни в каком начальном отрезке количество закрывающих
скобок не может оказаться больше количества открывающих скобок. (Например,
расстановки <tex dpi = 110> )( </tex> и <tex dpi = 110> ((())))( </tex> — неправильные.) Эти два условия не только необходимы, но и достаточны.
Рассмотрим несколько примеров. Одна пара скобок может выглядеть единственным способом: <tex dpi = 110> ()</tex>. Две пары — двумя способами: <tex dpi = 110> ()() </tex> или <tex dpi = 110> (())</tex>. Три пары —пятью способами: <tex dpi = 110> ()()(), ()(()), (())(), (()()) </tex> или <tex dpi = 110> ((()))</tex>. Четыре пары, как нетрудно проверить,— четырнадцатью способам и. Чтобы понять, сколькими способами могут выглядеть правильно расставленные пять пар скобок, рассмотрим закрывающую скобку, парную к первой открывающей скобке. Остальные четыре пары
тогда разделятся на две группы: расположенные внутри рассмотренной пары и
расположенные справа от неё. (Разумеется, любая из этих групп может состоять из
же — когда одна внутри, а три справа. Наконец, когда две пары внутри, а две
справа, имеем 2 · 2 = 4 способа. Итого
способа. Следуя такому походу, можно вычислять количество правильных скобочных последовательностей дальше.
</wikitex>
