Изменения

Числа Каталана просто посчитать с помощью рекуррентной формулы. Для этого понадобится <tex dpi = 120>O(n)</tex> памяти и <tex dpi = 120>O(n^2)</tex> времени. За <tex dpi = 120>O(n)</tex> времени их можно посчитать если использовать аналитическую формулу. Также из аналитической формулы можно выразить ещё более простую, если разложить два раза биноминальный коэффициент по формуле <tex dpi = 135> \binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1} </tex> и свести всё к <tex dpi = 135> C_{n-1} </tex>. В итоге должно получитьсяреккурентную формулу: