Разделы 
Дополнительно
Задача по математике - 1427
2018-12-13 
На окружности расположены шестнадцать точек. Эти точки требуется соединить восемью хордами, не имеющими общих точек (даже общих концов). Сколькими способами это можно сделать?
Решение:
Предположим, что на окружности последовательно отмечено $2n$ точек: $A_{1}, A_{2}, A_{3}, A_{4}, \cdots , A_{2n - 1}, A_{2n}$. Пусть $x_{n}$ - количество способов провести $n$ непересекающихся хорд. Заметим, что любая хорда, удовлетворяющая условию, должна быть проведена так, чтобы по обе стороны от нее располагалось четное количество данных точек. При этом, если какая-то хорда зафиксирована, то группы точек с одной и с другой стороны от нее можно рассматривать независимо, и решать задачу отдельно для каждой группы. Тогда количество способов провести $n - 1$ хорду равно произведению количества способов провести хорды в каждой из образовавшихся групп точек.
Будем последовательно фиксировать хорды $A_{1}A_{2}, A_{1}A_{4}, A_{1}A_{6}, \cdots, A_{1}A_{2n}$. Тогда число $x_{n}$ будет складываться из количества способов провести оставшиеся хорды в каждом из этих $n$ случаев, то есть $x_{n} = x_{n-1} + x_{1}x_{n-2} + x_{2}x_{n - 3} + x_{3}x_{n -4} + \cdots + x_{n - 2}x_{1} + x_{n-1}$. Заметим, что ни один из способов расстановки хорд мы не подсчитали дважды, так как в каждом из случаев можно провести только одну хорду с концом $A_{1}$. Итак, $x_{1} = 1, x_{2} = 2$ (это можно было заметить и без общей формулы), $x_{3} = 5, x_{4} = 14, x_{5} = 42, x_{6} = 132, x_{7} = 429, x_{8} = 1430$.
Числа, полученные в процессе решения задачи, называются числами Каталана. Их общая формула: $x_{n} = \frac{1}{2n + 1} C_{2n + 1}^{n}$, где $C_{2n+1}^{n}$ - количество сочетаний из $2n + 1$ по $n$, то есть, количество способов шбрать $n$ предметов из $2n + 1$. Более подробно о числах Катала-на - см., например, Р. Грэхем, Д. Кнут, О. Паташник «Конкретная математика» или Н.Б. Алфутова, А.В. Устинов «Алгебра и теория чисел».
Ответ: 1430 способами.
На окружности расположены шестнадцать точек. Эти точки требуется соединить восемью хордами, не имеющими общих точек (даже общих концов). Сколькими способами это можно сделать?
Решение:
Предположим, что на окружности последовательно отмечено $2n$ точек: $A_{1}, A_{2}, A_{3}, A_{4}, \cdots , A_{2n - 1}, A_{2n}$. Пусть $x_{n}$ - количество способов провести $n$ непересекающихся хорд. Заметим, что любая хорда, удовлетворяющая условию, должна быть проведена так, чтобы по обе стороны от нее располагалось четное количество данных точек. При этом, если какая-то хорда зафиксирована, то группы точек с одной и с другой стороны от нее можно рассматривать независимо, и решать задачу отдельно для каждой группы. Тогда количество способов провести $n - 1$ хорду равно произведению количества способов провести хорды в каждой из образовавшихся групп точек.
Будем последовательно фиксировать хорды $A_{1}A_{2}, A_{1}A_{4}, A_{1}A_{6}, \cdots, A_{1}A_{2n}$. Тогда число $x_{n}$ будет складываться из количества способов провести оставшиеся хорды в каждом из этих $n$ случаев, то есть $x_{n} = x_{n-1} + x_{1}x_{n-2} + x_{2}x_{n - 3} + x_{3}x_{n -4} + \cdots + x_{n - 2}x_{1} + x_{n-1}$. Заметим, что ни один из способов расстановки хорд мы не подсчитали дважды, так как в каждом из случаев можно провести только одну хорду с концом $A_{1}$. Итак, $x_{1} = 1, x_{2} = 2$ (это можно было заметить и без общей формулы), $x_{3} = 5, x_{4} = 14, x_{5} = 42, x_{6} = 132, x_{7} = 429, x_{8} = 1430$.
Числа, полученные в процессе решения задачи, называются числами Каталана. Их общая формула: $x_{n} = \frac{1}{2n + 1} C_{2n + 1}^{n}$, где $C_{2n+1}^{n}$ - количество сочетаний из $2n + 1$ по $n$, то есть, количество способов шбрать $n$ предметов из $2n + 1$. Более подробно о числах Катала-на - см., например, Р. Грэхем, Д. Кнут, О. Паташник «Конкретная математика» или Н.Б. Алфутова, А.В. Устинов «Алгебра и теория чисел».
Ответ: 1430 способами.
