Вычисление чисел Каталана

[codedot]

Задача о нахождении количества вариантов скобочных структур возникает во многих областях комбинаторики, а ее решением являются так называемые числа Каталана: (2n)!/((n + 1)!n!). Один из многочисленных способов вычисления этих чисел следующий.

Если рассматривать скобочные структуры, то можно построить дерево-сетку, путь прохождения по которому однозначно будет определять одну из скобочных структур (движение вправо означает приписывание "(" в конец к уже написанному выражению, движение вниз - приписывание ")", перемещения в других направлениях запрещены, путь начинается с корня - самого верхнего самого левого узла):

* - * - * - * - * -
    |   |   |   |
    *   * - * - * -
        |   |   |
        *   * - * -
            |   |
            *   * -
                |
                *

Если отбросить нижнюю диагональ и ко всем оставшимся узлам дерева-сетки начать приписывать количество путей, которыми можно до этих узлов добраться, становится очевидным, что значение, приписанное к каждому узлу, кроме корневого, равно сумме значений в родительских для него узлах:

1 -  1 -  1 -  1 -  1 -  1 -
     |    |    |    |    |
     1 -  2 -  3 -  4 -  5 -
          |    |    |    |
          2 -  5 -  9 - 14 -
               |    |    |
               5 - 14 - 28 -
                    |    |
                   14 - 42 -
                         |
                        42 -

На нижней диагонали дерева-сетки и оказываются числа Каталана после простых сложений чисел.