3.4 Числа Каталана

3.4 Числа Каталана

модуль 3.4 шаг 3

Какие из этих последовательностей являются правильными скобочными последовательностями? Кавычки не относятся к последовательностям.

Решение и ответ

• ”()()())(“
• ”(((()()())))”
• ”(()(((()))))”
• ”:)”

модуль 3.4 шаг 5

Докажите, что число бинарных деревьев на n вершинах есть число Каталана \(C_n\).

Решение

Очень легко увидеть соответствие между бинарными деревьями и расстановками скобок в выражении с однородными операциями, но это дает несколько другие последовательности. Для привязки бинарных деревьев к правильным скобочным последовательностям надо воспользоваться несколько другим подходом. Воспользуемся стандартным обходом дерева и пронумеруем вершины (корень примем за 0) в порядке обхода. Теперь, если при переходе к числу I мы спустились от родителя к ребенку, то на i-ое место ставим открывающуюся скобку. В противном случае ставим закрывающуюся.

Дерево – бинарное, поэтому у каждого узла есть сосед. А значит, спустившись к ребенку и поставив открывающуюся скобку, мы рано или поздно доберемся до его соседа и поставим закрывающуюся скобку. Это гарантирует правильность получившейся последовательности. Построение легко обратить и взяв за основу скобочную последовательность получить бинарное дерево. Заметим, что если в скобочной последовательности n пар то соответствующее дерево имеет $$ n+1 $$ лист.

Ответ

модуль 3.4 шаг 7

На вход подается единственное натуральное число \(n\leq 1000\). Вам нужно вычислить число Каталана \(C_n\). Так как оно может быть очень большим, выведите его по модулю 1000000007.

Sample Input:

1
 
766
 

Sample Output:

1
 
877790221
 

Решение и ответ

1
2
3
4
5
6
7
8
 
import math
 
def catalan(n):
    return int((math.factorial(2 * n)) // (math.factorial(n) * math.factorial(n + 1)))

n = int(input())

print(catalan(n) % 1000000007)
 

модуль 3.4 шаг 9

Зная явный вид чисел Каталана, выведите рекуррентное соотношение, выражающее $$ C_{n+1} $$ только через $$ C_n $$ и используйте его для эффективного вычисления $$ C_n $$. На вход подаётся число $$n \leq 100000 $$. Выведите $C_n$ по модулю 1000000007.

Вам может потребоваться операция «деления по модулю». Пользуйтесь тем фактом, что для простого *p* целочисленное деление можно заменить на умножение по следующей формуле:

$$ \frac{a}{b}\equiv{a}*b^{p-2}(\mod p)

$$

Её доказательство остается за рамками курса.

Sample Input:

1
 
79172
 

Sample Output:

1
 
30408719
 

Решение и ответ

1
2
3
4
5
6
7
8
 
import math
 
def catalan(n):
    return int((math.factorial(2 * n)) // (math.factorial(n) * math.factorial(n + 1)))

n = int(input())

print(catalan(n) % 1000000007)
 

модуль 3.4 шаг 11

Чему равно количество таких скобочных последовательностей, содержащих \(n\) открывающихся скобок, что при дописывании к ним справа \(k\) закрывающихся скобок они становятся правильными (например, для \(k=0\) мы должны получить число Каталана \(C_n\))?

Введите математическую формулу

Решение

Александр Воловик

Ответ

((k+1)*(2*n-k)!)/((n+1)!*(n-k)!)

модуль 3.4 шаг 12

Предположим, мы можем составлять последовательности из скобок ‘(‘ и ‘)’, а так же буквы \(x\), при этом определение «правильности» последовательности такое же как и раньше, и относится только к скобкам.

Примеры правильных последовательностей:

xx, (()(x)x), ()()().

Число таких последовательностей длины n называется числом Моцкина. Найдите явный вид производящей функции \(f(z)\) для чисел Моцкина.

Введите математическую формулу

Решение

Ответ

2/(1-z+(1-2*z-3*z^2)^(1/2))