Математические байки

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

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

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

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

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

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

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

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

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

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

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

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

Оно же число триангуляций [диагоналями] n+2-угольника. Ну и вообще у чисел Каталана очень много разных определений и свойств — но речь не об этом, а о том, как их посчитать.