Числа Каталана: различия между версиями
Глеб (обсуждение | вклад) (Новая страница: «Посчитаем количество правильных скобочных последовательностей (ПСП). Интуитивно понятн...») |
Глеб (обсуждение | вклад) |
||
Строка 1: | Строка 1: | ||
+ | ==Определение== | ||
+ | |||
Посчитаем количество правильных скобочных последовательностей (ПСП). Интуитивно понятно, что это, но формально они определятюся так: | Посчитаем количество правильных скобочных последовательностей (ПСП). Интуитивно понятно, что это, но формально они определятюся так: | ||
- Пустая последовательность является ПСП | - Пустая последовательность является ПСП | ||
Строка 4: | Строка 6: | ||
- Если $A$ и $B$ являются ПСП, то $AB$ является ПСП. | - Если $A$ и $B$ являются ПСП, то $AB$ является ПСП. | ||
− | Теперь, посчитаем количество ПСП с $2n$ скобками. Это называется числами Каталана и обозначается $C_n$. Рассмотрим первое место, где разность количества открывающих и закрывающих скобок впервые становится равна 0 и часть ПСП до этого места обозначим $(A)$, а часть после обозначим $B$. Понятно, что $A$ и $B$ являются ПСП меньшего размера (возможно, пустыми). | + | Теперь, посчитаем количество ПСП с $2n$ скобками. Это называется числами Каталана и обозначается $C_n$. |
+ | |||
+ | ==Формула== | ||
+ | |||
+ | Рассмотрим первое место, где разность количества открывающих и закрывающих скобок впервые становится равна 0 и часть ПСП до этого места обозначим $(A)$, а часть после обозначим $B$. Понятно, что $A$ и $B$ являются ПСП меньшего размера (возможно, пустыми). | ||
Теперь $C_n$ посчитать легко, перебирая размер $A$. | Теперь $C_n$ посчитать легко, перебирая размер $A$. | ||
Строка 11: | Строка 17: | ||
$C_n=C_0C_{n-1}+C_1C_{n-2}+\ldots+C_{n-1}C_0$ | $C_n=C_0C_{n-1}+C_1C_{n-2}+\ldots+C_{n-1}C_0$ | ||
+ | |||
+ | ==Альтернативные формулы== | ||
+ | |||
+ | $C_n = \frac{1}{n+1}{2 n \choose n} = \frac{1}{2 n+1}{2 n+1 \choose n} = \binom{2 n}{n} - \binom{2 n}{n-1}$ | ||
+ | |||
+ | Другими словами, число Каталана $C_n$ равно разности центрального биномиального коэффициента и соседнего с ним в той же строке треугольника Паскаля. | ||
{{Автор|Глеб Лобанов|glebodin}} | {{Автор|Глеб Лобанов|glebodin}} |
Текущая версия на 10:38, 30 октября 2019
Определение
Посчитаем количество правильных скобочных последовательностей (ПСП). Интуитивно понятно, что это, но формально они определятюся так: - Пустая последовательность является ПСП - Если $A$ является ПСП, то $(A)$ является ПСП - Если $A$ и $B$ являются ПСП, то $AB$ является ПСП.
Теперь, посчитаем количество ПСП с $2n$ скобками. Это называется числами Каталана и обозначается $C_n$.
Формула
Рассмотрим первое место, где разность количества открывающих и закрывающих скобок впервые становится равна 0 и часть ПСП до этого места обозначим $(A)$, а часть после обозначим $B$. Понятно, что $A$ и $B$ являются ПСП меньшего размера (возможно, пустыми).
Теперь $C_n$ посчитать легко, перебирая размер $A$.
$C_0=1$
$C_n=C_0C_{n-1}+C_1C_{n-2}+\ldots+C_{n-1}C_0$
Альтернативные формулы
$C_n = \frac{1}{n+1}{2 n \choose n} = \frac{1}{2 n+1}{2 n+1 \choose n} = \binom{2 n}{n} - \binom{2 n}{n-1}$
Другими словами, число Каталана $C_n$ равно разности центрального биномиального коэффициента и соседнего с ним в той же строке треугольника Паскаля.
Автор конспекта: Глеб Лобанов
По всем вопросам пишите в telegram @glebodin