94
правки
Изменения
Нет описания правки
*"" (пустая строка) есть правильная скобочная последовательность;
*правильная скобочная последовательность, взятая в скобки есть правильная скобочная последовательность;(*)
*правильная скобочная последовательность, к которой приписана слева или справа другая правильная скобочная последовательность, есть правильная скобочная последовательность;
}}
''Примеры правильных скобочный последовательностей:''
|id = def1
|definition =Числа Каталана {{---}} последовательность чисел, выражающих:
*количество неизоморфных упорядоченных бинарных деревьев с корнем и $n+1 $ листьями;*количество способов соединения $2n $ точек на окружности n непересекающимися хордами;*количество разбиений выпуклого $(n+2)$ -угольника на треугольники непересекающимися диагоналями;
*количество правильных скобочных последовательностей имеющих n открывающихся скобок.}}
Числа Каталана удовлетворяют следующему рекурентному соотношению:
$C_0 = 1$; {{---}} так как существует только одна скобочная последовательность с $0 $ открывающихся скобок - пустая
$C_n = \sum_{i = 1}^{n - 1} C_i C_{n - 1 - i}$.
