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 — но там немного другое утверждение и уж совсем другое доказательство (но тоже, кстати, поучительное)
Около минуты
19 ноября 2023