Рассмотрим $n$ точек на окружности и непересекающие хорды, которые попарно соединяют все точки (т. е. совершенное паросочетание). Обозначим количество таких разбиений через $f(n)$.
1) Очевидно, если $n$ нечётно, то $f(n)=0$. Пусть $n=2k$. Зафиксируем некоторую точку $P$ и допустим, что она соединена с точкой, стоящей через $2i+1$ шагов по окружности (то есть между этими двумя точками лежит $2i$ точек слева и $2(k-i-1)$ точек справа). Тогда конфигурация распадается на две независимые части размеров $2i$ и $2(k-i-1)$. Получаем рекуррентное соотношение
$$f(0)=1,f(2k)=\sum _{i=0}^{k-1}f(2i)f(2(k-1-i))(k\ge 1),$$ и $f(2k+1)=0$.
2) Введение чисел $a_k:=f(2k)$ даёт классическую рекурренцию Каталана:
$$a_0=1,a_k=\sum _{i=0}^{k-1}{a}_i{a}_{k-1-i}(k\ge 1).$$
3) Связь с числами Каталана: последовательность $a_k$ удовлетворяет уравнению для производящей функции $A(x)={\sum }_{k\ge 0}{a}_k{x}^k$:
$$A(x)=1+xA(x{)}^2,$$ откуда
$$A(x)=\frac{1-\sqrt{1-4x}}{2x},$$ и коэффициенты даются формулой
$$a_k=C_k=\frac{1}{k+1}\left(\genfrac{}{}{0ex}{}{2k}{k}\right).$$ Следовательно, для чётного $n=2k$ число непересекающих паросочетаний равно $C_k$, а для нечётного $n$ равно $0$.
Краткая интерпретация: непересекающие разбиения хордами биективно соответствуют структурам, считаемым числами Каталана (каталановы деревья, правильные скобочные последовательности, выпуклые триангуляции и т. п.).