Числа Каталана

Рассмотрим отображение, сопоставляющее разбиению на пары правильную скобочную последовательность по следующему правилу: меньшее число в паре становится открывающей скобкой, а большее – закрывающей. Кроме того, что отображение возвращает правильную скобочную последовательность, мы также покажем, что оно является биекцией на множество всех правильных скобочных последовательностей длины Тогда ясно, что число разбиений на пары равно

Почему всегда получается правильная скобочная последовательность? По определению отображения, каждой закрывающей скобке соответствует своя открывающая, идущая перед ней, поэтому в любом префиксе открывающих скобок не меньше, чем закрывающих. Любую правильную скобочную последовательность можно лишь единственным способом разбить на пары так, чтобы часть последовательности, находящаяся внутри любой пары скобок, тоже была правильной, и именно такое разбиение дает определение отображения. Действительно, предположим противное: пусть существует пара чисел нарушающая это условие. Если бы все числа между и были бы разбиты на пары, то в любом префиксе последовательности открывающих скобок было бы хотя бы столько же, сколько закрывающих. Поэтому либо существует открывающая скобка с номером которая сопоставлена закрывающей либо закрывающая с номером сопоставленная открывающей Любая из этих ситуаций противоречит условию задачи.

Таким образом, разбиение чисел на пары из условия задачи однозначно определяет правильную скобочную последовательность, поэтому построенное отображение инъективно. При этом, нетрудно видеть, что оно и сюръективно: данную правильную скобочную последовательность разобьем на пары открывающих/закрывающих скобок, и соответственно разобьем числа от до на пары. Если при таком построении нарушилось условие задачи, то существует набор чисел такой, что в разбиение одновременно входят пары и но тогда подпоследовательность скобок с номерами не является правильной, что противоречит построению. Биективность доказана.