<tex dpi = 120>t_{n+1} = t_0 t_n + t_1 t_{n-1} + \cdot \cdot \cdot + t_n t_0 </tex>
и поскольку <tex dpi = 120>t_0 = 1</tex>, последовательность чисел <tex dpi = 120>t_n</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> или <tex dpi = 110> ((())) </tex>. Четыре пары, как нетрудно проверить,— четырнадцатью способам и. Чтобы понять, сколькими способами могут выглядеть правильно расставленные пять пар скобок, рассмотрим закрывающую скобку, парную к первой открывающей скобке. Остальные четыре пары
тогда разделятся на две группы: расположенные внутри рассмотренной пары и
расположенные справа от неё. (Разумеется, любая из этих групп может состоять из
0 скобок.) Способов, когда все четыре пары внутри или все четыре справа, имеется
по 14 штук. Когда три пары внутри, а одна справа, имеем 5 способов. Столько
же — когда одна внутри, а три справа. Наконец, когда две пары внутри, а две
справа, имеем 2 · 2 = 4 способа. Итого
<tex dpi = 120> 14 + 5 + 2 \cdot 2 + 5 + 14 = 42 </tex>
способа. Следуя такому походу, можно вычислять количество правильных скобочных последовательностей дальше.
==Подсчет чисел Каталана==
