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

И — что "Студенческие чтения", что выпуски "Глобуса" я очень советую. Собственно, вот оглавление первого выпуска "Глобуса", https://www.mccme.ru/free-books/globus/globus1.pdf —

Ну и в заключение — вот ссылка на "Студенческие чтения НМУ", где опубликована лекция Кириллова — https://www.mccme.ru/free-books/globus/iumlectures1.pdf , и соответствующий скриншот:

Насколько я понимаю, такое и аналогичные рассуждения в теории вероятностей/случайных блужданиях называются "методом отражения".

Получаем путь из точки (0,-1). Сдвигаем его на 2 вверх, получаем опять путь из (0,1). После чего повторяем процедуру — если разорения нет, оставляем, если есть, отражаем на участке "до разорения включительно" и сдвигаем на 2 вверх.

А именно — берём такой путь. Если он уже нигде не касается оси абсцисс, то оставляем. Если где-нибудь касается, то берём первый момент разорения, и отражаем путь относительно оси абсцисс на участке до этого момента (а потом не меняем).

На самом деле, это несложно превратить и в биективное соответствие между путями из (0,1) длины n, не касающимися оси абсцисс, и всеми путями из (0,1) в (n,a), где a=1 или 2 в зависимости от чётности n (наименьшая возможная сумма у Васи).

— где k это n/2 при чётном n и (n+1)/2 при нечётном. То есть эта сумма, это просто центральный биномиальный коэффициент.

Но эта сумма телескопическая — это сумма разностей биномиальных коэффициентов, и каждый коэффициент, кроме первого, в ней сокращается. А именно — там будет

Понятно, что если умножить эту вероятность на 2^n, то получится число путей, делающих n шагов и не пересекающих запретную "линию нулей" — но приходящих куда угодно. И это сумма элементов (справа от линии нулей) в соответствующей строке нашего треугольника.

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

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

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

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

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

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