Изменения
Нет описания правки
# Можно ли "и", "или" и "не" выразить через функции из множества $\{x\to y, \neg x\}$?
# Можно ли "и", "или" и "не" выразить через функции из множества $\{{\mathbf 0}, \langle xyz\rangle, \neg x\}$ ?
# <strike> Можно ли "и", "или" и "не" выразить через функции из множества $\{x \to y, \langle xyz\rangle, \neg x\}$ ?</strike>
# Можно ли выразить "и" через "или"?
# Выразите медиану 5 через медиану 3
# Докажите, что для достаточно больших $n$ существует код Грея, который отличается от любого, полученного из зеркального перестановкой столбцов, отражением и циклическим сдвигом строк
# Код Грея назвается монотонным, если нет таких слов $g_i$ и $g_j$, что $i < j$, а $g_i$ содержит на 2 или больше единиц больше, чем $g_j$. Докажите, что существует монотонный код Грея
# В этом и последующих заданиях необходимо подробно изложить алгоритм вычисления числа комбинаторных объектов с таким префиксом, чтобы можно было получить объект по номеру. Получение объекта по номеру для перестановок.
# Получение объекта по номеру для сочетаний.
# Получение объекта по номеру для размещений.
# Факториальная система счисления. Рассмотрим систему счисления, где бесконечно много цифр, в $i$-м разряде (нумерация разрядов с 1 от младшего к старшему) разрешается использовать цифры от 0 до $i$, вес $i$-го разряда $i!$. Докажите, что у каждого положительного числа ровно одно представление в факториальной системе счисления (с точностью до ведущих нулей). Предложите алгоритм перевода числа в факториальную систему счисления.
# Как связана факториальная система счисления и нумерация перестановок?
# Фибоначчиева система счисления. Рассмотрим систему счисления, где есть две цифры, 0 и 1. Пусть нумерация разрядов ведется с 0 от младшего к старшему, вес $i$-го разряда $F_i$, где $F_i$ - $i$-е число Фибоначчи ($F_0 = 1$, $F_1 = 1$). При этом запрещается исползовать две единицы в соседних разрядах, а также запрещается использовать 1 в разряде 1. Сколько представлений в Фибоначчиевой системе счисления у положительного числа $x$? Предложите алгоритм перевода числа в фибоначчиеву систему счисления.
# Свяжите фибоначчиеву систему счисления с нумерацией каких-либо комбинаторных объектов.
# Коды Грея для перестановок. Предложите способ перечисления перестановок, в котором соседние перестановки отличаются обменом двух соседних элементов (элементарной транспозицией).
# Коды Грея для сочетаний. Предложите способ перечисления сочетаний, в котором соседние сочетания отличаются заменой одного элемента.
# Коды Грея для размещений. Предложите способ перечисления сочетаний, в котором соседние размещения отличаются заменой одного элемента в одной позиции.
# Укажите способ подсчитать число разбиений заданного $n$-элементного множества на $k$ упорядоченных непустых подмножеств
# Докажите, что число различных триангуляций правильного $n$-угольника равно числу Каталана. В этом и нескольких следующих заданиях номер соответствующего числа Каталана может отличаться от $n$, требуется также установить соответствие между размером задачи и номерами чисел Каталана.
# Докажите, что число двоичных деревьев с $n$ вершинами равно числу Каталана.
# Докажите, что число подвешенных деревьев с порядком на детях с $n$ вершинами равно числу Каталана.
# Будем называть последоватедовательность ''сортируемой стеком'', если ее можно отсортировать, используя в произвольном порядке следующие операции: (а) взять первый элемент входной последовательности и положить в стек (б) взять верхний элемент стека и отправить в конец выходной последовательности. Докажите, что число перестановок $n$ элементов, сортируемых стеком, равно число Каталана.
# Докажите, что число перестановок $n$ элементов, в которых нет возрастающей последовательности длины 3, равно числу Каталана.
# Докажите, что число способов расставить числа от 1 до $2n$ в прямоугольник $2 \times n$, чтобы числа в каждой строке и каждом столбце возрастали, равно числу Каталана.
# Докажите, что число Каталана $C_n = \frac{1}{n+1}C_{2n}^n$.
# Матрица Ханкеля - матрица $n \times n$, такая что $a[i][j] = C_{i+j-2}$. Докажите, что определитель матрицы Ханкеля равен 1.
# В этом и последующих заданиях необходимо подробно изложить алгоритм вычисления числа комбинаторных объектов с таким префиксом, чтобы можно было получить объект по номеру и номер по объекту. Получение объекта по номеру и номера по объекту для правильных скобочных последовательностей с одним типом скобок.
# Получение объекта по номеру и номера по объекту для правильных скобочных последовательностей с двумя типами скобок.
# Предложите алгоритм получения следующего по номеру в лексикографическом порядке разбиения множества $\{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.
# Выведите рекуррентную формулу для числа разбиений числа $n$ на нечетные слагаемые
# Выведите рекуррентную формулу для числа разбиений числа $n$ на нечетное число слагаемых
# Выведите рекуррентную формулу для числа разбиений числа $n$ на различные слагаемые
# Предложите алгоритм подсчета количества разбиений числа $n$ на слагаемые за $O(n\sqrt{n})$.
# Выведите рекуррентную формулу для числа разбиений числа $a+ib$, где $a$ и $b$ целые неотрицательные числа, на комплексные слагаемые вида $c + id$, где $c$ и $d$ целые неотрицательные числа, хотя бы одно из которых положительно.
# Раскрашенные слагаемые. Будем называть разбиение числа $n$ на положительные слагаемые раскрашенным, если каждому слагаемому сопоставлен один из $k$ заданных цветов. Два разбиения считаются одинаковыми, если слагаемые в одном из них можно переставить так, чтобы получилось другое разбиение (цвета после перестановки тоже должны совпасть). Выведите рекуррентную формулу для числа раскрашенных разбиений числа $n$ на слагаемые
# Разноцветные слагаемые. Будем называть разбиение числа $n$ на положительные слагаемые разноцветным, если каждому слагаемому сопоставлен один из $k$ заданных цветов, причем одинаковым числам в разбиении не сопоставляются одинаковые цвета. Два разбиения считаются одинаковыми, если слагаемые в одном из них можно переставить так, чтобы получилось другое разбиение (цвета после перестановки тоже должны совпасть). Выведите рекуррентную формулу для числа разноцветных разбиений числа $n$ на слагаемые
# Раскрашенные деревья. Выведите формулу для числа подвешенных деревьев с $n$ вершинами без порядка на детях, раскрашенных в $k$ цветов.
# Раскрашенные деревья. Выведите формулу для числа подвешенных деревьев с $n$ вершинами с порядком на детях, раскрашенных в $k$ цветов.
# Коды Прюфера. Рассмотрим процедуру для помеченного неподвешенного дерева. Будем по очереди выбирать лист, помеченный минимальным числом и удалять его из дерева, выписывая число в вершине, с которой он был связан. Таким образом будет выписано $n - 1$ число, последнее выписанное число всегда $n$. Докажите, что различным деревьям соответствуют различные коды Прюфера.
# Докажите, что любой код Прюфера соответствует некоторому дереву. Предложите алгоритм восстановления дерева по коду Прюфера. Сделайте вывод о числе помеченных неподвешенных деревьев с $n$ вершинами.
</wikitex>
