Во-первых, можно через производящие функции. Несложно увидеть рекуррентное соотношение для чисел Каталана C_n:

Если собрать их в производящую функцию,
F(z)=\sum_n C_n z^n,
то в правой части рекуррентного соотношения стоят коэффициенты F(z)^2 — которые ещё нужно сдвинуть на одну степень. Поэтому оно превращается в квадратное уравнение на производящую функцию:
F(z)-1=z F^2(z).

Отсюда находим F(z) —

(знак в числителе должен быть минусом, потому что иначе числитель не обратится в ноль при z=0, а у нас не может быть особенности вида 1/z).

И, наконец, разложив (1-4z)^{1/2} по биному Ньютона для нецелой степени — где нецелый биномиальный коэффициент определяется как

(конечно же, бином Ньютона для нецелой степени это то же самое, что и ряд Тейлора) — и немного переписав получившееся произведение (1/2)*(1/2)*(3/2)*(5/2)*...*4^n/n!, получаем явный ответ

И это, конечно, очень техничный способ получить ответ. Но мне больше всего нравится другой способ — который я узнал из лекции А. А. Кириллова на "Студенческих чтениях НМУ" (предшественник семинара "Глобус").

Давайте находить сразу для всех точек (n,k) число способов добраться до них ломаными (с шагами (1,1) и (1,-1)), не спускаясь ниже оси абсцисс. Только развернём картинку на 90 градусов по часовой стрелке — чтобы ломаные шли вниз-вправо или вниз-влево.

Получается вот такая картинка —

Верхняя 1 это точка старта, (0,0); до каждой точки можно дойти из той, которая выше-левее или выше-правее, поэтому число способов складывается. Наконец, на один ряд левее её идёт запрещённая вертикаль — в этих точках мы нарушили запрет "ниже нуля не спускаться", поэтому там по определению стоят [красные] нули.

То есть — правило как у треугольника Паскаля, только вот красные нули "прибиты гвоздями по определению".

Прошу прощения — не заметил опечатку в картинке выше: в последней строчке должно быть, конечно,
5 9 5 1
Вот правильная картинка —

Так вот — а нельзя ли нам эти нули как-нибудь тоже включить в правило треугольника Паскаля?
Оказывается, что можно. Давайте заменим их на зеркало — а за зеркалом пусть будет антимир: такие же числа, но с минусами.

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