Презентация на тему: "Числа Каталана"

ЧИСЛА КАТАЛАНА

Числа Каталана — числовая последовательность, встречающаяся в удивительном числе комбинаторных задач. Эта последовательность названа в честь бельгийского математика Каталана (Catalan), жившего в 19 веке, хотя на самом деле она была известна ещё Эйлеру (Euler), жившему за век до Каталана.

Само число Каталана выражается формулой C(n) = (2n)!/n!(n+1)!,
где восклицательный знак, как обычно, обозначает факториал. Начало последовательности выглядит так: 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796…

Известно, как минимум 66 различных конструкций, которые приводят к появлению чисел Каталана. Вот некоторые из них:  
Правильные скобочные последовательности – наборы открывающихся и закрывающихся скобок, в которых каждой открывающейся скобке соответствует закрывающаяся. Число возможных последовательностей с фиксированным числом пар скобок выражается числом Каталана. Например, 14 правильных последовательностей из четырех пар скобок: (((()))), ((()())), ((())()), ((()))(), (()(())), (()()()), (()())(), (())(()), (())()(), ()((())), ()(()()), ()(())(), ()()(()), ()()()()

Первым с числами Каталана столкнулся Леонард Эйлер. Он подсчитал, сколькими способами выпуклый многоугольник может быть разделён на треугольники непересекающимися диагоналями.
В качестве примера можно привести способы разбиения на треугольники следующих фигур: квадрата, пятиугольника и шестиугольника.

Заметим, что в каждом из случаев¸ независимо от количества сторон n- угольника, число диагоналей равно (n – 3), а число треугольников (n – 2).
Число различных комбинаций указанного вида для каждого из многоугольников есть первые четыре члена (если начинать с треугольника) последовательности Каталана.

Эйлер, используя метод математической индукции, который, по его словам, здесь оказался трудоёмким, получил такую формулу:




Пусть k – последнее вычисленное число Каталана, а n – номер следующего числа.
Тогда это число вычисляется по формуле: