Отсюда находим 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
Вот правильная картинка —

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

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

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

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

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