Числа Каталана
Число Каталана \(C_n\) определяет, сколько существует способов правильно расставить скобки в выражении, содержащем \(n\) левых и \(n\) правых скобок. Например, \(C_3=5\), т.е. существует пять способо расставить три левые и три правые скобки:
● ()()()
● (())()
● ()(())
● ((()))
● (()())
Числа Каталана можно вычислить по формуле:
\(C_n = \displaystyle\sum_{i=0}^{n-1}C_iC_{n-i-1},\)
которая получается, если рассмотреть способы разбиения расстановки скобок на две части, обе из которых являются правильными расстановками и первая содержит минимально возможное число скобок, но при этом не пуста. Для каждого \(i\) первая часть содержит \(i+1\) пар скобок, и число правильных расстановок равно произведению следующих величин:
● \(C_i\) – количество способов построить расстановку из скобок, входящих в первую часть без учета самых внешних скобок;
● \(C_{n-i-1}\) – количество способов построить расстановку из скобок, входящих во вторую часть.
Базой рекурсии является случай \(C_0=1\), поскольку вообще без скобок можно построить только пустую расстановку.
Числа Каталана можно также вычислить по формуле
\(C_n=\frac{1}{n+1}\binom{2n}{n},\)
которую можно объяснить так. Всего существует \(\binom{2n}{n}\) способов расставить \(n\) левых и \(n\) правых скобок (необязательно правильно). Посчитаем, сколько из этих расстановок неправильны.
Если расстановка скобок неправильна, то она должна содержать префикс, в котором правых скобок больше, чем левых. Идея в том, чтобы выбрать самый короткий из таких префиксов и поменять в нем каждую скобку на противоположную. Например, расстановка ()()( имеет префикс ()) и после обращения скобок принимает вид )((()(. В получающейся расстановке будет \(n + 1\) левых и \(n - 1\) правых скобок. На самом деле существует единственный способ получить произвольную расстановку \(n + 1\) левых и \(n - 1\) правых скобок описанным выше способом. Число таких расстановок равно \(\binom{2n}{n+1}\), именно столько существует неправильных расстановок скобок. Следовательно, число правильных расстановок равно
\(\binom{2n}{n}-\binom{2n}{n+1}=\binom{2n}{n}-\frac{n}{n+1}\binom{2n}{n}=\frac{1}{n+1}\binom{2n}{n}.\)
Подсчёт деревьев
С помощью чисел Каталана можно также подсчитать количество некоторых древовидных структур. Прежде всего \(C_n\) равно числу двоичных деревьев с \(n\) вершинами в предположении, что левая и правая дочерняя вершины различаются. Например, существует \(5\) двоичных деревьев с \(3\) вершинами, поскольку \(C_3=5:\)
Далее, \(C_n\) равно числу корневых деревьев общего вида с \(n+1\) вершинами. На рисунке ниже показано \(5\) корневых деревьев с \(4\) вершинами:
