Производящие функции и числа Каталана — Комбинаторика, эп. 20

Сколько вариантов рукопожатий без пересечения можно составить с кругом из 2n человек? Сколько существует допустимых способов расположить n пар скобок? Сколько корневых, упорядоченных, полных бинарных деревьев имеют n внутренних узлов? Ответ на все эти вопросы — числа Каталана. В этом видео мы выводим рекуррентное соотношение для чисел Каталана. Затем мы используем это рекуррентное соотношение и производящие функции для вывода явной формулы для n-го числа Каталана. Источники Adams, H., Emmrich, K., Gillespie, M., Golden, S., & Pries, R. (2023). Counting Rocks! An Introduction to Combinatorics. Colorado State University. https://www.mathematicalgemstones.com... Bogart, K. P. (2004). Combinatorics Through Guided Discovery. Dartmouth College. https://bogart.openmathbooks.org/pdf/... Гишар, Д. (2017). Введение в комбинаторику и теорию графов. Колледж Уитмена. https://www.whitman.edu/mathematics/c... Моррис, Дж. (2023). Комбинаторика: вводный курс продвинутого уровня по перечислению, теории графов и теории проектирования. Университет Летбриджа. https://opentext.uleth.ca/PDF/Combina...