Рекуррентная формула для чисел Каталана.

В действительности числа Каталана C(n) определяются так: нулевое число Каталана равно единице. Число с номером n равно сумме следующих произведений: нулевого числа на (n-1)–е, первого числа на (n-2)–e, второго на (n-3)–е, …, (n-1)–го на нулевое, так чтобы сумма номеров двух перемножаемых чисел была равна n-1. Более строго это можно записать так:

(1)

Так, для малых значений n получаем:

Покажем, что именно такая рекуррентная формула соответствует решениям всех трех предложенных задач.

Рассмотрим сначала случай правильных скобочных структур (расстановок скобок). Пусть дана некоторая правильная расстановка n пар скобок. Понятно, что начальная скобка a будет открывающей. Следовательно, ей соответствует какая–то закрывающая скобка b. Между этими двумя скобками находится другой набор скобок, возможно пустой, который, очевидно, является правильной скобочной структурой. Кроме того, последовательность скобок, стоящая после скобки b, также правильная. Таким образом, внутри нашей структуры есть еще две правильные структуры, суммарное количество пар скобок в которых равно n-1. Эти две структуры полностью определяют изначальную расстановку скобок: для ее получения достаточно заключить в скобки первую структуру, а затем справа приписать к ней вторую.

Пример.В структуре ( ( ) ( ) ) ( ( ) ) из пяти пар скобок скобки, отмеченные красным, отделяют правильную структуру из двух пар скобок от правильной структуры из двух пар скобок.

Таким образом, становится понятен смысл формулы (1): для того, чтобы посчитать количество правильных структур из пяти пар скобок нужно рассмотреть зафиксировать первую пару скобок, а затем поставить две правильные структуры, суммарное количество скобок в которых равно четырем.

Аналогичная ситуация имеет место и в случае с многоугольниками: мы фиксируем некоторое ребро и рассматриваем треугольник, примыкающий к этому ребру, см. рис. 2. Он разбивает (n+2)–угольник на (p+2)–угольник и (q+2)–угольник, где p+q=n-1. Эти два многоугольника должны быть разбиты на треугольники своими непересекающимися диагоналями, которые являются диагоналями исходного многоугольника. Любое такое разбиение двух “маленьких” многоугольников порождает разбиение изначального многоугольника.

На рисунке 2 изображен восьмиугольник (8=6+2), разбиение которого на треугольники непересекающимися диагоналями порождается такими разбиениями для четырехугольника (4=2+2) и пятиугольника (5=3+2). При этом 6-1=2+3.

Таким образом, для количества разбиений (n+2)–угольника непересекающимися диагоналями на треугольники имеет место та же рекуррентная формула, что и для скобочных структур.

Перейдем, наконец, к описанию задачи про билеты в театр. Для каждого возможного случая распределения пятирублевых и десятирублевых банкнот у стоящих в очереди можно построить правильную скобочную структуру. Действительно, каждому следующему стоящему в очереди будем приписывать скобку, которая будет открывающей, если у него на руках пятирублевая купюра, и закрывающей, если десятирублевая. Условие того, что у кассира всегда будет достаточно пятирублевых купюр означает, что по ходу написания слова из скобок количество открывающих будет всегда не меньше количества закрывающих, а то, что эти купюры иссякнут после обслуживания последнего покупателя, значит, что во всем слове количество открывающих скобок будет равно количеству закрывающих. Это и означает, что каждой открывающей скобке будет однозначно соответствовать закрывающая. Для этого человеку, давшему пять рублей, после чего у кассира стало m пятирублевых банкнот, нужно сопоставить человека, давшего десять рублей и стоящего после первого, после чего у кассира осталась (m-1) пятирублевая банкнота, причем между первым и вторым человеком у кассира должно всегда быть не меньше n пятирублевых банкнот.

Пример. Для скобочной структуры ( ) ( ( ) ( ( ) ) ) из пяти пар скобок поставим в соответствие такое распределение банкнот: 5, 10, 5, 5, 10, 5, 5, 10, 10, 10. При этом количество пятирублевых банкнот у кассира после продажи очередного билета будет изменяться следующим образом:

1, 0, 1, 2, 1, 2, 3, 2, 1, 0

( ) ( ( ) ( ( ) ) )

Из сказанного выше следует, что правильные скобочные структуры из n скобок однозначно соответствуют “хорошим” распределениям пяти– и десятирублевых банкнот у стоящих в очереди.

Таким образом, количество правильных очередей из 2n человек равно C(n) и ответ на третью задачу, как и на первые две, связан с числами Каталана.

При этом у нас остается открытым еще один вопрос: как считать числа Каталана, т.е. найти формулу для C(n) не рекуррентную, а в явном виде.