Комбинаторный смысл чисел Каталана

[caxap]

Число каталано $C_n$ равно числу правильный скобочных последовательностей длины $2n$. Известна формула для него $\binom {2n} n-\binom {2n} {n-1}$ (из Википедии).

Как можно комбинатоно интерпретировать эту формулу? Первый коэф. --- число способов выбрать $n$ скобок из $2n$, второй --- аналогично, только выбор $n+1$ скобок. Почему-то их разность равна числу правильных скобочных последовательностей длины $2n$. Это не понимаю.

[Trotil]

Здесь в конце есть вывод формулы: http://e-maxx.ru/algo/catalan_numbers

[Zealint]

caxap в сообщении #336707 писал(а):

Как можно комбинатоно интерпретировать эту формулу?

Можно сказать, что из числа всех скобочных последовательностей, коих $\binom{2n}{n}$ нужно вычесть число неправильных. Неправильных будет $\frac{n}{n+1}\binom{2n}{n}=\binom{2n}{n-1}=\binom{2n}{n+1}$.

Trotil в сообщении #336752 писал(а):

Здесь в конце есть вывод формулы: http://e-maxx.ru/algo/catalan_numbers

Можно и так, а вывод формулы $\frac{1}{n+1}\binom{2n}{n}$ через производящие функции есть здесь.