Числа Каталана: различия между версиями

Материал из Algocode wiki
Перейти к: навигация, поиск
(Новая страница: «Посчитаем количество правильных скобочных последовательностей (ПСП). Интуитивно понятн...»)
 
 
Строка 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