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