(конечно же, бином Ньютона для нецелой степени это то же самое, что и ряд Тейлора) — и немного переписав получившееся произведение (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
Вот правильная картинка —

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

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

Поэтому вся эта картинка строится просто по тому же правилу, что и обычный треугольник Паскаля, но из первой строчки "(-1) 1".

Но поскольку правило линейное — то она будет разностью обычных треугольников Паскаля, растущего из правой 1 и из левой (-1).

В частности, n-е число Каталана равно:

Ну и вообще, если нам нужно расставить k символов "+1" и m-k символов "-1" — так, чтобы ни на каком начальном участке сумма не была бы отрицательной — то количество способов это сделать будет равно

Из этой же картины/интерпретации можно получить и ответ на связанный вопрос из теории вероятностей/случайных блужданий. Допустим, у Васи есть один рубль, и он играет в орлянку — каждый раз ставя по рублю и с равной вероятностью выигрывая и проигрывая. Если в какой-то момент денег у него не остаётся — то он уходит. С какой вероятностью за n шагов он не разорится?