Изменения
Нет описания правки
# Рассмотрим коды Грея для перестановок и коды Грея для их таблиц инверсий. Есть ли между ними связь?
# Сочетание с повторениями - это способ выбрать из $n$ элементов $k$, причем один элемент можно выбирать несколько раз. Порядок не важен. Чему равно число сочетаний с повторениями из $n$ по $k$?
# Предложите альтернативное доказательство формулы включения-исключения: посчитайте для каждого элемента, сколько раз он будет посчитан в правой части формулы и используйте формулу $\sum_{k=0}^n (-1)^kC_n^k = 0$.
# Предложите алгоритм получения по перестановке ее таблицы инверсий за $O(n \log n)$.
# Предложите алгоритм получения перестановки по ее таблице инверсий за $O(n \log n)$.
# Максимумом в перестановке называется элемент, который больше своих соседей (одного, если он первый или последний, обоих иначе). Выведите рекуррентную формулу для числа перестановок $n$ элементами с $k$ максимумами
# Подъемом в перестановке называется пара соседних элементов, таких что $a_{i-1} < a_i$. Выведите рекуррентную формулу для числа перестановок $n$ элементов с $k$ подъемами
# Неподвижной точкой в перестановке называется элемент $a_i = i$. Выведите рекуррентную формулу для числа перестановок $n$ элементов с $k$ неподвижными точками
# Докажите, что числа Стирлинга 1 рода образуют матрицу переходов в линейном пространстве полиномов базиса возрастающих факториальных степеней к базису обычных степеней
# Докажите, что числа Стирлинга 2 рода образуют матрицу переходов в линейном пространстве полиномов от базиса обычных степеней к базису убывающих факториальных степеней
# Укажите способ подсчитать число разбиений заданного $n$-элементного множества на $k$ упорядоченных непустых подмножеств
# Докажите, что $n$-е число Каталана равно ${2n \choose n}/(n+1)$
# Двоичное дерево - это подвешенное дерево, где каждая вершина может иметь двух детей: левого и правого. Каждый из них также является двоичным деревом (либо отсутствует). Докажите, что число двоичных деревьев с $n$ вершинами равно $n$-му числу Каталана.
# Подвешенное дерево с порядком на детях - это подвешенное дерево, где каждая вершина может иметь произвольное число детей, причем дети упорядочены. Каждый ребенок в свою очередь является подвешенным деревом. Докажите, что число подвешенных деревьев порядком на детях с $n$ вершинами равно $n-1$-му числу Каталана.
# Докажите, что число триангуляций правильного $n$-угольника равно $n-2$-му числу Каталана.
# Установите явное взаимно-однозначное соответствие между объектами из предыдущих трех заданий и правильными скобочными последовательностями.
# Укажите способ подсчитать число разбиений числа на слагаемые за $O(n \sqrt{n})$
</wikitex>
