Числа Каталана
Комбинаторное доказательство тождества 
.
Число Каталана)
считает количество слов длины 2n над алфавитом \})
с равным количеством открывающихся и закрывающихся скобок, любой префикс которых содержит не меньше открывающихся скобок, чем закрывающихся. Другая интерпретация: количество маршрутов из точки (0,0) в точку (n,n), когда передвижения ограничены ходами вправо (0,1) и вверх (1,0), пересечение (или соприкосновение с) диагональю (0,0)-(n,n) разрешено только по краям маршрута и первый ход - вправо.
Число маршрутов длины 2n-1 из (0,0) в (n,n-1), когда посредине маршрута запрещается пересекать диагональ (0,-1)-(n,n-1) и когда первые два хода - вправо, равно, стало быть,
.
Обозначим через)
число маршрутов длины
, начинающихся в (0,0), когда запрещается пересекать диагональ{-}(\ell,\ell{-}1))
, первый ход - вправо и когда количество ходов вправо превышает количество ходов вверх на k. Обратим внимание, что = C_{n-1})
. Мы заинтересованы в нахождении следующей величины = \sum_{k = 0}^{2n}{2f(2n, k)})
. Число F(n) выражает количество маршрутов из (0,0) в (n,n), не пересекающих диагональ (0,0)-(n,n) (без ограничения на начальный ход). Дважды расписывая каждый из суммандов с помощью рекуррентного правила
 = f(\ell{-}1, k{-}1) + f(\ell{-}1, k{+}1))
для
и = 0)
для
получаем равенство = 4F(n{-}1) - 2f(2n{-}1, 1) = 4F(n{-}1) - 2C_{n-1})
.
Проверкой устанавливаем, что решением последней рекуррентной формулы является = \binom{2n}{n})
.
Возвращаемся к доказательству тождества. Всё количество маршрутов длины 2n из точки (0,0), когда разрешено двигаться вверх и вправо, равно
. С другой стороны, это количество равно следующей сумме маршрутов. Нулевая группа маршрутов просто никогда не пересекает диагональ (0,0)-(n,n) - таковых, пользуясь нашим вспомогательным доказательством,
. Первая группа маршрутов доходит до точки (1,1), а затем уже никогда не пересекает диагональ (1,1)-(n,n) - таковых
(из двух первых ходов выбираем место для хода вправо, а оставшийся ход вверх определяется автоматически), помноженное на
по вспомогательному доказательству. Вторая группа маршрутов доходит до точки (2,2), а затем уже никогда не пересекает диагональ (2,2)-(n,n) - таковых
. Продолжаем таким образом до n-ой группы маршрутов, которая просто доходит до точки (n,n) - таковых
. Так как все перечисленные маршруты различны и так как все маршруты длины 2n попадают в одну из (n+1)-ной категорий,
.
Некомбинаторное доказательство того же тождества через ряд Тейлора
проще, но совершенно не интуитивно начинать именно с него.
.
Число Каталана
считает количество слов длины 2n над алфавитом
с равным количеством открывающихся и закрывающихся скобок, любой префикс которых содержит не меньше открывающихся скобок, чем закрывающихся. Другая интерпретация: количество маршрутов из точки (0,0) в точку (n,n), когда передвижения ограничены ходами вправо (0,1) и вверх (1,0), пересечение (или соприкосновение с) диагональю (0,0)-(n,n) разрешено только по краям маршрута и первый ход - вправо.
Число маршрутов длины 2n-1 из (0,0) в (n,n-1), когда посредине маршрута запрещается пересекать диагональ (0,-1)-(n,n-1) и когда первые два хода - вправо, равно, стало быть,
.
Обозначим через
число маршрутов длины
, начинающихся в (0,0), когда запрещается пересекать диагональ
, первый ход - вправо и когда количество ходов вправо превышает количество ходов вверх на k. Обратим внимание, что
. Мы заинтересованы в нахождении следующей величины
. Число F(n) выражает количество маршрутов из (0,0) в (n,n), не пересекающих диагональ (0,0)-(n,n) (без ограничения на начальный ход). Дважды расписывая каждый из суммандов с помощью рекуррентного правила
для
и
для
получаем равенство
.
Проверкой устанавливаем, что решением последней рекуррентной формулы является
.
Возвращаемся к доказательству тождества. Всё количество маршрутов длины 2n из точки (0,0), когда разрешено двигаться вверх и вправо, равно
. С другой стороны, это количество равно следующей сумме маршрутов. Нулевая группа маршрутов просто никогда не пересекает диагональ (0,0)-(n,n) - таковых, пользуясь нашим вспомогательным доказательством,
. Первая группа маршрутов доходит до точки (1,1), а затем уже никогда не пересекает диагональ (1,1)-(n,n) - таковых
(из двух первых ходов выбираем место для хода вправо, а оставшийся ход вверх определяется автоматически), помноженное на
по вспомогательному доказательству. Вторая группа маршрутов доходит до точки (2,2), а затем уже никогда не пересекает диагональ (2,2)-(n,n) - таковых
. Продолжаем таким образом до n-ой группы маршрутов, которая просто доходит до точки (n,n) - таковых
. Так как все перечисленные маршруты различны и так как все маршруты длины 2n попадают в одну из (n+1)-ной категорий,
.
Некомбинаторное доказательство того же тождества через ряд Тейлора
проще, но совершенно не интуитивно начинать именно с него.