Изменения
Нет описания правки
# В этом и последующих заданиях необходимо подробно изложить алгоритм вычисления числа комбинаторных объектов с таким префиксом, чтобы можно было получить объект по номеру и номер по объекту. Получение объекта по номеру и номера по объекту для правильных скобочных последовательностей с одним типом скобок.
# Получение объекта по номеру и номера по объекту для правильных скобочных последовательностей с двумя типами скобок.
# Укажите способ подсчитать число разбиений заданного $n$-элементного множества на $k$ упорядоченных непустых подмножеств
# Подъемом в перестановке называется пара соседних элементов, таких что $a_{i-1} < a_i$. Выведите рекуррентную формулу для числа перестановок $n$ элементов с $k$ подъемами
# Неподвижной точкой в перестановке называется элемент $a_i = i$. Выведите рекуррентную формулу для числа перестановок $n$ элементов с $k$ неподвижными точками
# Чему равно число перестановок с заданным циклическим классом?
# Степенью перестановки $\pi$ называется минимальное $k$, такое что $\pi^k=i$, где $i$ - тождественная перестановка. Как связана степень перестановки с ее циклическим классом?
# Предложите алгоритм поиска перестановки из $n$ элементов с максимальной степенью за $O(n^3)$.
# Рассмотрим коды Грея для перестановок и коды Грея для их таблиц инверсий. Есть ли между ними связь?
# Докажите, что минимальное число невозрастающих подпоследовательностей, на которые можно разбить заданную последовательность, равно длине ее наибольшей возрастающей подпоследовательности
# Докажите, что произведение длины наибольшей возрастающей подпоследовательности и наибольшей убывающей подпоследовательности перестановки не меньше $n$
# Выведите рекуррентную формулу для числа разбиений числа $n$ на нечетные слагаемые
# Выведите рекуррентную формулу для числа разбиений числа $n$ на нечетное число слагаемых
# Выведите рекуррентную формулу для числа разбиений числа $n$ на различные слагаемые
# Предложите алгоритм подсчета количества разбиений числа $n$ на слагаемые за $O(n\sqrt{n})$.
= ЭТО НЕ КОНЕЦ, ЭТО ЕЩЕ ТОЛЬКО НАЧАЛО =
