Изменения
Нет описания правки
# Предложите алгоритм получения следующего по номеру в лексикографическом порядке разбиения множества $\{1, \ldots, n\}$ на множества. Множества в каждом разбиении упорядочиваются лексикографически по представлениям в виде возрастающего списка элеметов. Разбиения далее упорядочиваются лексикографически как списки множеств.
# Предложите алгоритм получения следующего по номеру в лексикографическом порядке разбиения множества $\{1, \ldots, n\}$ на множества. Множества в каждом разбиении упорядочиваются лексикографически как битовые вектора. Разбиения далее упорядочиваются лексикографически как списки множеств.
# Максимумом в перестановке называется элемент, который больше своих соседей (одного, если он первый или последний, обоих иначе). Выведите рекуррентную формулу для числа перестановок $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$ бусинок $k$ цветов с точностью до циклического сдивига и отражения.
# Выведите формулу для числа раскрасок прямоугольника $n \times m$ в $k$ цветов с точностью до отражения относительно горизонтальной и вертикальной оси.
# Выведите формулу для числа раскрасок граней тетраэдра в $k$ цветов с точностью до любого поворота в 3D.
# Выведите формулу для числа раскрасок ребер тетраэдра в $k$ цветов с точностью до любого поворота в 3D.
</wikitex>
