Числа Каталана

Сколько существует правильных скобочных последовательностей из n пар скобок? Сколько существует способов разбить выпуклый (n+2)-угольник на треугольники непересекающимися диагоналями? Сколько существует бинарных деревьев с n листьями? Путей по линиям клеток от левого нижнего до правого верхнего угла квадрата n×n, не пересекающих побочную диагональ? На эти и еще многие вопросы дает ответ одна единственная математическая модель – ряд чисел Каталана.

Числа Каталана – это числовая последовательность, названная в честь любителя шоколада (sic!) Эжена-Шарля Каталана, но известная и до него. Ответами к вопросам, в зависимости от n, будут числа 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845…

Почему же это работает для таких разных задач? Работает ли вообще? Мы не верим без доказательства! И как определяется n-ное числа Каталана?

Соу, связь между задачами. Для n=3 на картинке с https://habrahabr.ru/post/165295/ показано соответствие. А по ссылке можно найти понятное объяснение.Давайте на примере многоугольников рассмотрим начало вывода формулы для n-ного числа Каталана. ОЧЕВИДНО, что для n=1, то есть для треугольника, есть 1 способ. Договоримся, что для n=0 ответом будем считать 1. Выберем одну из сторон (n+2)-угольника. И будем по очереди соединять ее концы с остальными вершинами многоугольника (которых n штук). Многоугольник получится разделенным на меньший многоугольник, треугольник и еще один меньший многоугольник (в случае соединения с соседней стороной получаем нечто, для чего ответ равен 1, n=0). При соединении стороны с заданной вершиной, количество способов равно (ответ для первого многоугольника)*(ответ для второго многоугольника). Осталось только сложить количество способов для всех вершин. Получается рекуррентная формула. Далее, после некоторых преобразований, получается производящая функция    T(n) = (2n)! / (n! * (n+1)!). Эти “некоторые” преобразования можно посмотреть тут. Красивейший вывод, рекомендую разобраться. И еще тут.

Числа Каталана, приятно познакомиться.

Поделиться постом
Have your say!
0 0

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>