Номер 6, страница 417 - гдз по алгебре 10 класс учебник Мерзляк, Номировский

6. Числа Каталане.

Рекомендуемая литература:

1) Спивак А. Числа Каталане // Квант. 2004. № 3.

2) Бурман Ю., Спивак А. Автостоянки, перестановки и деревья // Квант. 2004. № 4.

3) Сендеров В., Френкин Б. Гипотеза Каталане // Квант. 2007. № 4.

4) Гарднер М. Числа Каталане // Квант. 1978. № 7.

5) Шень А. Программирование: теоремы и задачи. — М. : МЦНМО, 2004.

Определение и формулы

Изображение относится к теме "Числа Каталана". Числа Каталана — это последовательность натуральных чисел, которая возникает во многих задачах комбинаторики. Они обозначаются как $C_n$ и названы в честь бельгийского математика Эжена Шарля Каталана.

Вот несколько классических примеров задач, решением которых являются числа Каталана:

• $C_n$ — это количество правильных скобочных последовательностей длины $2n$, то есть последовательностей, состоящих из $n$ открывающих и $n$ закрывающих скобок, в которых баланс скобок нигде не становится отрицательным. Например, для $n=3$ существует $C_3=5$ таких последовательностей: ((())), (()()), (())(), ()(()), ()()().
• $C_n$ — это количество способов разрезать выпуклый $(n+2)$-угольник на треугольники с помощью непересекающихся диагоналей.
• $C_n$ — это количество путей Дика (Dyck paths) длины $2n$. Это пути на квадратной сетке из точки $(0,0)$ в точку $(2n,0)$ с шагами "вверх-вправо" $(+1, +1)$ и "вниз-вправо" $(+1, -1)$, которые никогда не опускаются ниже оси абсцисс. Или, что эквивалентно, количество путей из $(0,0)$ в $(n,n)$ с шагами "вправо" и "вверх", которые не поднимаются выше главной диагонали.

Первые несколько чисел Каталана для $n = 0, 1, 2, 3, 4, 5, \dots$ равны: 1, 1, 2, 5, 14, 42, 132, ...

Для вычисления чисел Каталана используются следующие формулы:

1. Явная формула через биномиальные коэффициенты (наиболее распространенная): $$ C_n = \frac{1}{n+1} \binom{2n}{n} = \frac{(2n)!}{(n+1)!n!} $$

2. Рекуррентная формула: $$ C_0 = 1 \quad \text{и} \quad C_{n+1} = \sum_{i=0}^{n} C_i C_{n-i} \quad \text{для } n \ge 0 $$ Это означает, что каждое следующее число Каталана является сверткой предыдущих членов последовательности. Например, $C_3 = C_0C_2 + C_1C_1 + C_2C_0 = 1 \cdot 2 + 1 \cdot 1 + 2 \cdot 1 = 5$.

Ответ: Числа Каталана — это последовательность $C_n = \frac{1}{n+1}\binom{2n}{n}$, которая является решением многих комбинаторных задач, таких как подсчет правильных скобочных последовательностей, триангуляций многоугольника и путей Дика.

Рекомендуемая литература

На изображении приведен следующий список рекомендованной литературы по данной теме:

1. Спивак А. Числа Каталана // Квант. 2004. № 3.
2. Бурман Ю., Спивак А. Автостоянки, перестановки и деревья // Квант. 2004. № 4.
3. Сендеров В., Френкин Б. Гипотеза Каталана // Квант. 2007. № 4.
4. Гарднер М. Числа Каталана // Квант. 1978. № 7.
5. Шень А. Программирование: теоремы и задачи. — М. : МЦНМО, 2004.

Ответ: Список литературы по теме "Числа Каталана" представлен выше.