Найти тему
84 подписчика

В ответ на пост

Классическое применение леммы Рени — формула для чисел Каталана:

пути Дика можно отождествить с последовательностями из n+1 числа +1 и n чисел -1, все частичные суммы которых положительны — а по лемме Рени последнее условие выделяет 1/(2n+1) часть от всех \binom{2n+1}{n+1} последовательностей (для каждой последовательности подойдет ровно один циклический сдвиг)

про последовательности ±1, частичные суммы и циклические перестановки есть также статья Эрдеша и Капланского 1946 года

https://old.renyi.hu/~p_erdos/1946-09.pdf — но там немного другое утверждение и уж совсем другое доказательство (но тоже, кстати, поучительное)
Около минуты