Список заданий по ДМ 2017 осень

Дискретная математика, 1 семестр

Задания, помеченные 🤔 - задания повышенной сложности. Задания, помеченные 😱 - задания очень высокой сложности. ✋ помечены задания, где мы передаем привет курсу "Алгоритмы и структуры данных", 👻 - задания только для групп M3132-M3135.

1. Пусть [math]R[/math] и $S$ - рефлексивные отношения на $A$. Будет ли рефлексивным их а) объединение? б) пересечение? В этом и следующих заданиях, если ответ отрицательный, при демонстрации контрпримера удобно использовать представление отношения в виде ориентированного графа.
2. Пусть $R$ и $S$ - симметричные отношения на $A$. Будет ли симметричным их а) объединение? б) пересечение?
3. Пусть $R$ и $S$ - транзитивные отношения на $A$. Будет ли транзитивным их а) объединение? б) пересечение?
4. Пусть $R$ и $S$ - антисимметричные отношения на $A$. Будет ли антисимметричным их а) объединение? б) пересечение?
5. Определим $R^{-1}$ следующим образом: если $xRy$, то $yR^{-1}x$. Выполнено ли соотношение $RR^{-1} = I$, где $I$ - отношение равенства? Выполнен ли закон сложения степенией $R^iR^j=R^{i+j}$, если $i$ и $j$ разного знака?
6. Пусть $R$ обладает свойством $X$. Будет ли обладать свойством $X$ отношение $R^{-1}$? Следует проанализировать $X$ - рефлексивность, антирефлексивность, симметричность, антисимметричность, транзитивность
7. Пусть $R$ и $S$ - транзитивные отношения на $A$. Будет ли транзитивным их композиция?
8. Пусть $R$ и $S$ - антисимметричные отношения на A. Будет ли антисимметричным их композиция?
9. Постройте пример рефлексивного, симметричного, но не транзитивного отношения
10. Постройте пример рефлексивного, антисимметричного, но не транзитивного отношения
11. Является ли отношение $R$, такое что $(a, b) R (c, d)$, если $ad = bc$ на ${\mathbb Z}^+ \times {\mathbb N}$ отношением эквивалентности?
12. Может ли отношение частичного порядка быть отношением эквивалентности? Если да, то в каких случаях?
13. Можно ли в определении отношения эквивалентности убрать требование рефлексивности отношения, потому что оно следует из симметричности и транзитивности?
14. 🤔✋ Транзитивный остов. Задано антисимметричное транзитивное отношение $R$ на $X$. Предолжите полиномиальный алгоритм построения отношения $S$, такого что $S^+=R$, причем в $S$ содержится минимальное число пар элементов.
15. 🤔 В предыдущем задании требование транзитивности опустить нельзя. Задано антисимметричное отношение $R$ на $X$. Докажите, что если существует полиномиальный алгоритм построения отношения $S$, такого что $S \subset R$ и $S^+=R^+$, причем в $S$ содержится минимальное число пар элементов, то можно проверить, есть ли в графе гамильтонов цикл (цикл, проходящий по каждой вершине графа ровно один раз) за полиномиальное время.
16. СКНФ. Будем называть формулу для функции совершенной конъюнктивной нормальной формой, если ее эта формула является конъюнкцией клозов, каждый из которых представляет дизъюнкцию переменных и их отрицаний, причем каждая переменная встречается в каждом клозе ровно один раз. Докажите, что любую функцию, кроме тождественной 1, можно представить в виде СКНФ.
17. Выразите в явном виде "и", "или" и "не" через стрелку Пирса
18. Выразите в явном виде "и", "или" и "не" через штрих Шеффера
19. Можно ли "и", "или" и "не" выразить через функции из множества $\{x\oplus y, x = y\}$?
20. Можно ли "и", "или" и "не" выразить через функции из множества $\{x\to y, \neg x\}$?
21. Можно ли "и", "или" и "не" выразить через функции из множества $\{{\mathbf 0}, \langle xyz\rangle, \neg x\}$ ?
22. Можно ли выразить "и" через "или"?
23. Выразите медиану 5 через медиану 3
24. 🤔 Выразите медиану $2n+1$ через медиану 3
25. Булева функция называется пороговой, если $f(x_1, x_2, \ldots, x_n) = 1$ тогда и только тогда, когда $a_1x_1+a_2x_2+\ldots+a_nx_n \ge b$, где $a_i$ и $b$ - вещественные числа. Докажите, что "и", "или", "не" - пороговые функции.
26. Приведите пример непороговой функции
27. 🤔 Рассмотрим булеву функцию $f$. Обозначим как $N(f)$ число наборов аргументов, на которых $f$ равна 1. Например, $N(\vee) = 3$. Обозначим как $\Sigma(f)$ сумму всех наборов аргументов, на которых $f$ равна 1 как векторов. Например, $\Sigma(\vee) = (2, 2)$. Докажите, что если для пороговой функции $f$ и функции $g$ выполнено $N(f) = N(g)$ и $\Sigma(f) = \Sigma(g)$, то $f = g$
28. 🤔✋ Говорят, что формула имеет вид 2-КНФ, если она имеет вид $(t_{11}\vee t_{12})\wedge(t_{21}\vee t_{22})\wedge\ldots$, где $t_{ij}$ представляет собой либо переменную, либо ее отрицание (в каждом дизъюнкте ровно два терма). Предложите полиномиальный алгоритм проверки, что формула, заданная в 2-КНФ имеет набор значений переменных, на которых она имеет значение 1.
29. 🤔✋ КНФ называется КНФ Хорна, если в каждом дизъюнкте не более одной переменной находится без отрицания. Пример: $x\wedge(x \vee \neg y \vee \neg z) \wedge (\neg x \vee \neg t)$. Предложите полиномиальный алгоритм проверки, что формула, заданная в форме КНФ Хорна имеет набор аргументов, на котором она равна 1.
30. [только гр. 32-35 👻] Постройте двойственную функцию для каждой функции от 2 аргументов.
31. 👻 Сколько существует самодвойственных функций от $n$ аргуметов?
32. Будем говорить, что функция существенно зависит от переменной $x_i$, если существует два набора аргументов, различающихся только значением $x_i$, на которых функция принимает различные значения. Сколько существует булевых функций от $n$ аргументов, существенно зависящих от всех аргументов? Достаточно привести рекуррентную формулу.
33. Приведите пример функции, существенно зависящей хотя бы от 3 аргументов, которая лежит во всех 5 классах Поста.
34. Приведите пример функции, существенно зависящей хотя бы от 3 аргументов, которая не лежит ни в одном классе Поста.
35. Булева функция $f(x_1, x_2, \ldots, x_n)$ называется форсируемой, если существует такое назначение $x_i=const$ , что для любых значений других переменных значение функции является константой. Например, $x_1 \wedge x_2$ является форсируемой, поскольку при $x_1 = 0$ значение функции равно 0 для любого значения $x_2$. Для каждой функции от двух переменных определите, является ли она форсируемой.
36. Булева функция называется симметричной, если ее значение не меняется при любой перестановке ее переменных. Сколько существует симметричных функций от $n$ переменных?
37. 🤔 Докажите, что любую функцию от $n$ переменных можно представить с использованием стрелки Пирса формулой, длиной не больше чем $2^n\cdot poly(n)$, где $poly(n)$ - полином, общий для всех функций
38. Докажите, что любую монотонную функцию можно выразить через "и", "или", 0 и 1.
39. 🤔 Докажите, что любую монотонную самодвойственую функцию можно выразить через медиану
40. Докажите, что если булеву функцию $f$ можно задать в форме Крома (в виде 2-КНФ), то выполнено следствие: $f(x_1, ..., x_n) = f(y_1, ..., y_n) = f(z_1, ..., z_n) = 1$ $\Rightarrow f(\langle x_1, y_1, z_1\rangle, ..., \langle x_n, y_n, z_n \rangle) = 1$
41. 😱 Докажите, что если выполнено следствие: $f(x_1, ..., x_n) = f(y_1, ..., y_n) = f(z_1, ..., z_n) = 1$ $\Rightarrow f(\langle x_1, y_1, z_1\rangle, ..., \langle x_n, y_n, z_n \rangle) = 1$, то булеву функцию $f$ можно задать в форме Крома.
42. Докажите, что если булеву функцию $f$ можно задать в форме Хорна, то выполнено следствие: $f(x_1, ..., x_n) = f(y_1, ..., y_n) = 1 \Rightarrow f(x_1\wedge y_1, ..., x_n \wedge y_n) = 1$
43. 😱 Докажите, что если выполнено следствие: $f(x_1, ..., x_n) = f(y_1, ..., y_n) = 1 \Rightarrow f(x_1\wedge y_1, ..., x_n \wedge y_n) = 1$, то булеву функцию $f$ можно задать в форме Хорна
44. Докажите, что $x_0\oplus x_1\oplus\ldots\oplus x_{2m} = \langle \neg x_0,s_1,s_2,\ldots,s_{2m}\rangle$, где $s_j=\langle x_0,x_j,x_{j+1},\ldots,x_{j+m-1},\neg x_{j+m},\neg x_{j+m+1},\ldots,\neg x_{j+2m-1}\rangle$, для удобства $x_{2m+k}$ обозначет то же, что и $x_k$ для $k \ge 1$.
45. Докажите, что биномиальный коэффициент $C_n^k$ нечетен тогда и только тогда, когда в двоичной записи $k$ единицы стоят только на тех позициях, где в двоичной записи $n$ также находятся единицы (иначе говоря, двоичная запись $k$ доминируется двоичной записью $n$ как двоичным вектором).
46. Докажите "метод треугольника" построения полинома Жегалкина по таблице истинности.
47. Постройте схему из функциональных элементов для операции медиана трех над базисом $\{ \vee, \wedge, \neg\}$. Постарайтесь использовать минимальное число элементов.
48. Постройте схему из функциональных элементов для операции $x \oplus y \oplus z$ над базисом $\{ \vee, \wedge, \neg\}$. Постарайтесь использовать минимальное число элементов.
49. Предложите способ построить схему для функции $x_1 \oplus ... \oplus x_n$ над базисом $\{ \vee, \wedge, \neg\}$ с линейным числом элементов и глубиной $O(\log n)$.
50. Докажите, что для функции "большинство из $2n+1$" существует схема из функциональных элементов глубины $O(\log n)$
51. Докажите, что любую булеву функцию от $n$ аргументов можно представить схемой из функциональных элементов, содержащей $O(2^n)$ элементов.
52. Докажите, что не существует схем константной глубины для функций $x_1 \vee ... \vee x_n$, $x_1 \wedge ... \wedge x_n$, $x_1 \oplus ... \oplus x_n$.
53. Мультиплексором называется схема, которая имеет $2^n+n$ входов и один выход. Обозначим входы как $x_0, x_1, \ldots, x_{2^n-1}, y_0, y_1, \ldots, y_{n-1}$. На выход подается то же, что подается на вход $x_i$, где $i$ - двоичное число, которое кодируется входами $y_0, \ldots, y_{n-1}$. Постройте схему линейного (от суммарного количества входов и выходов) размера для мультиплексора.
54. Дешифратором называется схема, которая имеет $n+1$ входов и $2^n$ выходов. Обозначим входы как $y_0, y_1, \ldots, y_{n-1}, x$, а выходы как $z_0, z_1, \ldots, z_{2^n-1}$. На все выходы подается 0, а на выход $z_i$ то же, что подается на вход $x$, где $i$ - двоичное число, которое кодируется входами $y_0, \ldots, y_{n-1}$. Постройте схему линейного (от суммарного количества входов и выходов) размера для
55. Игра "два шага вперед, один назад". Задана булева функция от $n$ аргументов $f(x_1, \ldots, x_n)$. Играют два игрока: 0 и 1. Игроки делают ходы по очереди. Для хода используется вспомогательное значение $m$, исходно равное 0, кроме того исходно все значения переменных не определены. Ход заключается в следующем. Игрок либо увеличивает $m$ на 2, либо уменьшает на 1. После этого действия значение $m$ должно удовлетворять неравенству $1 \le m \le n$. Затем, если значение $x_m$ не определено, то игрок присваивает переменной $x_m$ значение на свое усмотрение. Если же значение $x_m$ определено, то оно меняется на противоположное. Игра заканчивается, когда все значения определены. Если значение функции $f$ на получившемся наборе переменных равно 1, то выигрывает 1, иначе выигрывает 0. Проанализируйте описанную игру для значений $n$ от 2 до 9 на функции $f(x_1, \ldots, x_n)$, равной 1, если строка $x_1x_2\ldots x_n$ лексикографически строго меньше строки $x_nx_{n-1}\ldots x_1$.
56. Проанализируйте игру "два шага вперед, один назад" для значений $n$ от 2 до 9 на функции $f(x_1, \ldots, x_n)=x_1\oplus x_2\oplus \ldots\oplus x_n$.
57. Проанализируйте игру "два шага вперед, один назад" для значений $n$ от 2 до 9 на функции $f(x_1, \ldots, x_n)$, равной 1, если строка $x_1x_2\ldots x_n$ не содержит двух единиц подряд.
58. Проанализируйте игру "два шага вперед, один назад" для значений $n$ от 2 до 9 на функции $f(x_1, \ldots, x_n)$, равной 1, если строка $x_1x_2\ldots x_n$ представляет собой (возможно дополненную ведущими нулями) двоичную запись простого числа.дешифратора.
59. Докажите, что не существует схемы константной глубины для сложения.
60. На одном китайском заводе в матричном умножителе случайно использовали элементы "или" вместо "и". Можно ли из получившихся значений получить произведение исходных чисел (доступа к входам нет, есть только доступ к $n\times n$ выходам матричного псевдоумножителя).
61. Контактной схемой называется ориентированный ациклический граф, на каждом ребре которого написана переменная или ее отрицание (ребра в контактных схемах называют контактами, а вершины - полюсами). Зафиксируем некоторые значения переменным. Тогда замкнутыми называются ребра, на которых записана 1, ребра, на которых записан 0, называются разомкнутыми. Зафиксируем две вершины $u$ и $v$. Тогда контактная схема вычисляет некоторую функцию $f$ между вершинами $u$ и $v$, равную 1 на тех наборах переменных, на которых между $u$ и $v$ есть путь по замкнутым ребрам. Постройте контактные схемы для функций "и", "или" и "не".
62. Постройте контактную схему для функции "xor".
63. Постройте контактную схему для функции медиана трех.
64. Докажите, что любую булеву функцию можно представить контактной схемой.
65. Постройте контактную схему "xor от $n$ переменных", содержащую $O(n)$ ребер.
66. Постройте контактную схему "большинство из $2n+1$ переменных", содержащую $O(n)$ ребер.
67. Постройте контактную схему, в которой для каждого из $2^n$ наборов дизъюнкций переменных и их отрицаний есть пара вершин, между которыми реализуется эта дизъюнкция, используя $O(2^n)$ ребер.
68. Докажите, что любую булеву функцию можно представить контактной схемой, содержащей $O(2^n)$ ребер.
69. 👻 По числам $l_1, l_2, \ldots, l_n$, удовлетворяющим неравенству $\sum\limits_{i=1}^n 2^{-l_i} \le 1$, постройте префиксный код с таким набором длин кодовых слов.
70. Как выглядит дерево Хаффмана для частот символов $1, 2, ..., 2^{n-1}$ (степени двойки) ?
71. Как выглядит дерево Хаффмана для частот символов $1, 1, 2, 3, ..., F_{n-1}$ (числа Фибоначчи)?
72. Докажите, что если размер алфавита - степень двойки и частоты никаких двух символов не отличаются в 2 или более раз, то код Хаффмана не лучше кода постоянной длины
73. Модифицируйте алгоритм Хаффмана, чтобы строить $k$-ичные префиксные коды
74. Укажите, как построить дерево Хаффмана за линейное время, если символы уже отсортированы по частоте
75. Предложите алгоритм построения оптимального кода среди префиксных кодов с длиной кодового слова не более L бит
76. Предложите способ хранения информации об оптимальном префиксном коде для n-символьного алфавита, использующий не более $2n - 1 + n \lceil\log_2(n)\rceil$ бит ($\lceil x\rceil$ - округление $x$ вверх)
77. Можно ли разработать алгоритм, который сжимает любой файл не короче заданной величины $N$ хотя бы на 1 бит?
78. Приведите пример однозначно декодируемого кода оптимальной длины, который не является ни префиксным, ни развернутым префиксным
79. Для каких префиксных кодов существует строка, для которой он является кодом Хаффмана? Предложите алгоритм построения такой строки.
80. Пусть заданы пары $(u_i, v_i)$. Предложите полиномиальный алгоритм проверки, что существует код Хаффмана для некоторой строки, в котором $i$-е кодовое слово содержит $u_i$ нулей и $v_i$ единиц.
81. Докажите, что если в коде Хаффмана для некоторой строки $i$-е кодовое слово содержит $u_i$ нулей и $v_i$ единиц, то для многочлена от двух переменных $f(x, y) = \sum_{i=1}^n x^{u_i}y^{v_i}$ выполнено $f(x, y) - 1 = (x + y - 1) g(x, y)$ для некоторого многочлена $g(x, y)$.
82. При арифметическом кодировании можно учитывать, что с учетом уже потраченных символов соотношения символов становятся другими и отрезок надо делить в другой пропорции. Всегда ли кодирование с таким уточнением лучше классического арифметического кодирования?
83. При арифметическом кодировании трудным моментом является деление отрезка в пропорциях, не являющихся степенями двойки. Рассмотрим модификацию арифметического кодирования, когда соотношения между символами приближаются дробями со знаменателями - степенями двойки. Что можно сказать про получившийся алгоритм?
84. Проанализируйте время работы алгоритма арифиметического кодирования
85. Докажите, что для любого $c > 1$ существует распределение частот $p_1, p_2, .., p_n$, что арифметическое кодирование в $c$ раз лучше Хаффмана
86. Докажите, что при оптимальном кодирование с помощью LZ77 не выгодно делать повтор блока, который можно увеличить вправо
87. Верно ли утверждение из предыдущего задания при кодировании с помощью L78?
88. Разработайте алгоритм оптимального кодирования текста с помощью LZ77, если на символ уходит $c$ бит, а на блок повтора $d$ бит
89. Предложите семейство строк $S_1, S_2, \ldots, S_n, \ldots$, где $S_i$ имеет длину $i$, таких, что при их кодировании с помощью LZW длина строки увеличивается. Начальный алфавит $\{0, 1\}$.
90. Предложите алгоритм декодирования кода Барроуза-Уиллера.
91. Предложите алгоритм декодирования кода Барроуза-Уиллера за $O(n)$.
92. Предложите реализацию преобразования Move to Front за $O(n \log n)$.
93. Предложите реализацию преобразования Move to Front за $O(n)$.
94. Докажите, что $n$-битный код, исправляющий одну ошибку содержит не более, чем $2^n/(n+1)$ кодовое слово.
95. Обобщите оценку из предыдущего задания на код, исправляющий $k$ ошибок.
96. Разработайте оптимальный код исправляющий одну ошибку при пересылке 2 битов
97. Разработайте оптимальный код исправляющий одну ошибку при пересылке 3 битов
98. Разработайте оптимальный код исправляющий одну ошибку при пересылке 4 битов
99. Разработайте код, исправляющий две ошибки, использующий асимптотически не более $2n$ бит для кодирования $2^n$ символьного алфавита (для $n > n_0$)
100. Докажите, что в зеркальном коде Грея $g_i = i \oplus \lfloor i / 2\rfloor$
101. Докажите, что в зеркальном коде Грея при переходе от $g_i$ к $g_{i+1}$ меняется тот же бит, который меняется с 0 на 1 при переходе от $i$ к $i+1$
102. Разработайте код Грея для k-ичных векторов
103. При каких $a_1, a_2, ..., a_n$ существует обход гиперпараллелепипеда $a_1 \times a_2 \times ... \times a_n$, который переходит каждый раз в соседнюю ячейку и бывает в каждой ячейке ровно один раз?
104. При каких $a_1, a_2, ..., a_n$ существует обход гиперпараллелепипеда $a_1 \times a_2 \times ... \times a_n$, который переходит каждый раз в соседнюю ячейку и бывает в каждой ячейке ровно один раз, а в конце возвращается в исходную ячейку?
105. Код "антигрея" - постройте двоичный код, в котором соседние слова отличаются хотя бы в половине бит
106. Троичный код "антигрея" - постройте троичный код, в котором соседние слова отличаются во всех позициях
107. При каких $n$ и $k$ существует двоичный $n$-битный код, в котором соседние кодовые слова отличаются ровно в $k$ позициях?
108. Докажите, что для достаточно больших $n$ существует код Грея, который отличается от любого, полученного из зеркального перестановкой столбцов, отражением и циклическим сдвигом строк
109. 🤔 Код Грея назвается монотонным, если нет таких слов $g_i$ и $g_j$, что $i < j$, а $g_i$ содержит на 2 или больше единиц больше, чем $g_j$. Докажите, что существует монотонный код Грея
110. Факториальная система счисления. Рассмотрим систему счисления, где бесконечно много цифр, в $i$-м разряде (нумерация разрядов с 1 от младшего к старшему) разрешается использовать цифры от 0 до $i$, вес $i$-го разряда $i!$. Докажите, что у каждого положительного числа ровно одно представление в факториальной системе счисления (с точностью до ведущих нулей). Предложите алгоритм перевода числа в факториальную систему счисления.
111. Как связана факториальная система счисления и нумерация перестановок?
112. Фибоначчиева система счисления. Рассмотрим систему счисления, где есть две цифры, 0 и 1. Пусть нумерация разрядов ведется с 1 от младшего к старшему, вес $i$-го разряда $F_i$, где $F_i$ - $i$-е число Фибоначчи ($F_0 = 1$, $F_1 = 1$, нулевой разряд не используется). При этом запрещается исползовать две единицы в соседних разрядах. Сколько представлений в Фибоначчиевой системе счисления у положительного числа $x$? Предложите алгоритм перевода числа в фибоначчиеву систему счисления.
113. Свяжите фибоначчиеву систему счисления с нумерацией каких-либо комбинаторных объектов.
114. Выведите рекуррентную формулу для числа комбинаторных объектов: вектор длины $2n$, в котором каждое число от $1$ до $n$ встречается ровно два раза.
115. Коды Грея для перестановок. Предложите способ перечисления перестановок, в котором соседние перестановки отличаются обменом двух соседних элементов (элементарной транспозицией).
116. Коды Грея для сочетаний. Предложите способ перечисления сочетаний, в котором соседние сочетания отличаются заменой одного элемента.
117. Коды Грея для размещений. Предложите способ перечисления размещений, в котором соседние размещения отличаются заменой одного элемента в одной позиции.
118. Докажите, что $C_r^mC_m^k=C_r^kC_{r-k}^{m-k}$.
119. Докажите, что $\sum_{k=0}^n C_{m+k}^k=C_{m+n+1}^n$.
120. Докажите, что $\sum_{k=0}^n C_r^kC_s^{n-k}=C_{r+s}^n$.
121. Для решения этой и следующих задач вам понадобится понятие чисел Каталана. Числом Каталана $C_n$ называется количество правильных скобочных последовательностей с $n$ открывающимися скобками. Докажите, что $C_n = \sum_{i=0}^{n-1}C_iC_{n-i-1}$.
122. Докажите, что число Каталана $C_n = \frac{1}{n+1}C_{2n}^n$.
123. Докажите, что число различных триангуляций правильного $n$-угольника равно числу Каталана. В этом и нескольких следующих заданиях номер соответствующего числа Каталана может отличаться от $n$, требуется также установить соответствие между размером задачи и номерами чисел Каталана.
124. Докажите, что число двоичных деревьев с $n$ вершинами равно числу Каталана.
125. Докажите, что число подвешенных деревьев с порядком на детях с $n$ вершинами равно числу Каталана.
126. Будем называть последоватедовательность сортируемой стеком, если ее можно отсортировать, используя в произвольном порядке следующие операции: (а) взять первый элемент входной последовательности и положить в стек (б) взять верхний элемент стека и отправить в конец выходной последовательности. Докажите, что число перестановок $n$ элементов, сортируемых стеком, равно число Каталана.
127. Докажите, что число перестановок $n$ элементов, в которых нет возрастающей последовательности длины 3, равно числу Каталана.
128. Докажите, что число способов расставить числа от 1 до $2n$ в прямоугольник $2 \times n$, чтобы числа в каждой строке и каждом столбце возрастали, равно числу Каталана.
129. Матрица Ханкеля - матрица $n \times n$, такая что $a[i][j] = C_{i+j-2}$. Докажите, что определитель матрицы Ханкеля равен 1.
130. В этом и последующих заданиях необходимо подробно изложить алгоритм вычисления числа комбинаторных объектов с таким префиксом, чтобы можно было получить объект по номеру и номер по объекту. Получение объекта по номеру и номера по объекту для правильных скобочных последовательностей с одним типом скобок.
131. Получение объекта по номеру и номера по объекту для правильных скобочных последовательностей с двумя типами скобок.
132. Укажите способ подсчитать число разбиений заданного $n$-элементного множества на $k$ упорядоченных непустых подмножеств (например, для $n = 3$, $k = 2$ есть следующие разбения: $\{[1], [2, 3]\}$, $\{[1], [3, 2]\}$, $\{[1, 2], [3]\}$, $\{[1, 3], [2]\}$, $\{[2, 1], [3]\}$, $\{[2], [3, 1]\}$.
133. Подъемом в перестановке называется пара соседних элементов, таких что $a_{i-1} < a_i$. Выведите рекуррентную формулу для числа перестановок $n$ элементов с $k$ подъемами
134. Неподвижной точкой в перестановке называется элемент $a_i = i$. Выведите рекуррентную формулу для числа перестановок $n$ элементов с $k$ неподвижными точками
135. Чему равно число перестановок с заданным циклическим классом?
136. Степенью перестановки $\pi$ называется минимальное $k$, такое что $\pi^k=i$, где $i$ - тождественная перестановка. Как связана степень перестановки с ее циклическим классом?
137. Предложите алгоритм поиска перестановки из $n$ элементов с максимальной степенью за $O(n^3)$.
138. Рассмотрим коды Грея для перестановок и коды Грея для их таблиц инверсий. Есть ли между ними связь?
139. Докажите, что минимальное число невозрастающих подпоследовательностей, на которые можно разбить заданную последовательность, равно длине ее наибольшей возрастающей подпоследовательности
140. Докажите, что произведение длины наибольшей возрастающей подпоследовательности и наибольшей убывающей подпоследовательности перестановки не меньше $n$
141. Выведите рекуррентную формулу для числа разбиений числа $n$ на нечетные слагаемые
142. Выведите рекуррентную формулу для числа разбиений числа $n$ на нечетное число слагаемых
143. Выведите рекуррентную формулу для числа разбиений числа $n$ на различные слагаемые
144. Предложите алгоритм подсчета количества разбиений числа $n$ на слагаемые за $O(n\sqrt{n})$.
145. Выведите рекуррентную формулу для числа разбиений числа $a+ib$, где $a$ и $b$ целые неотрицательные числа, на комплексные слагаемые вида $c + id$, где $c$ и $d$ целые неотрицательные числа, хотя бы одно из которых положительно.
146. Раскрашенные слагаемые. Будем называть разбиение числа $n$ на положительные слагаемые раскрашенным, если каждому слагаемому сопоставлен один из $k$ заданных цветов. Два разбиения считаются одинаковыми, если слагаемые в одном из них можно переставить так, чтобы получилось другое разбиение (цвета после перестановки тоже должны совпасть). Выведите рекуррентную формулу для числа раскрашенных разбиений числа $n$ на слагаемые
147. Разноцветные слагаемые. Будем называть разбиение числа $n$ на положительные слагаемые разноцветным, если каждому слагаемому сопоставлен один из $k$ заданных цветов, причем одинаковым числам в разбиении не сопоставляются одинаковые цвета. Два разбиения считаются одинаковыми, если слагаемые в одном из них можно переставить так, чтобы получилось другое разбиение (цвета после перестановки тоже должны совпасть). Выведите рекуррентную формулу для числа разноцветных разбиений числа $n$ на слагаемые
148. Приведите другое доказательство формулы включения-исключения на базе формулы $\sum_{i=1}^n (-1)^i C_n^i = -1$.
149. Сколько существует чисел, не превышающих $n$, которые взаимно просты с числом $n$?
150. Докажите, что $\max(x_1, \ldots , x_n)$ = $\sum_{i} x_i - \sum_{i < j} \min(x_i, x_j) +$ $\sum_{i < j < k} \min(x_i, x_j, x_k) + \ldots + (-1)^{n-1} \min(x_1, \ldots , x_n)$
151. Формула обращения Мёбиуса. Пусть $S$ — конечное множество, и пусть $f \colon 2^S \to \mathbb{R}$ — произвольная функция, определенная на совокупности подмножеств $S$ и принимающая вещественные значения. Определим функцию $g \colon 2^S \to \mathbb{R}$ следующим соотношением: $g(Y) = \sum_{X \supseteq Y} f(X)$. Докажите, что $f(Y) = \sum_{X \supseteq Y} (-1)^{|X| - |Y|} \, g(X)$.
152. Чему равно число сюрьекций из $n$-элементного множества в $m$-элементное?
153. Сколько существует пар взаимно-простых чисел от $1$ до $n$?
154. Выведите формулу для числа ожерелий из $n$ бусинок $k$ цветов с точностью до циклического сдивига и отражения.
155. Выведите формулу для числа раскрасок прямоугольника $n \times m$ в $k$ цветов с точностью до отражения относительно горизонтальной и вертикальной оси.
156. Выведите формулу для числа раскрасок граней тетраэдра в $k$ цветов с точностью до любого поворота в 3D.
157. Выведите формулу для числа раскрасок ребер тетраэдра в $k$ цветов с точностью до любого поворота в 3D.
158. Выведите формулу для числа раскрасок граней куба в $k$ цветов с точностью до любого поворота в 3D.
159. Выведите формулу для числа раскрасок ребер куба в $k$ цветов с точностью до любого поворота в 3D.
160. Выведите формулу для числа раскрасок граней октаэдра в $k$ цветов с точностью до любого поворота в 3D.
161. Почему мы не сделали задачу про вершины тетраэдра, вершины куба, вершины и ребра октаэдра? Неужели оставили на контрольную?
162. Раскрашенные деревья. Выведите формулу для числа подвешенных деревьев с $n$ вершинами без порядка на детях, раскрашенных в $k$ цветов.
163. Раскрашенные деревья. Выведите формулу для числа подвешенных деревьев с $n$ вершинами с порядком на детях, раскрашенных в $k$ цветов.
164. Коды Прюфера. Рассмотрим процедуру для помеченного неподвешенного дерева. Будем по очереди выбирать лист, помеченный минимальным числом и удалять его из дерева, выписывая число в вершине, с которой он был связан. Таким образом будет выписано $n - 1$ число, последнее выписанное число всегда $n$. Докажите, что различным деревьям соответствуют различные коды Прюфера.
165. Докажите, что любой код Прюфера соответствует некоторому дереву. Предложите алгоритм восстановления дерева по коду Прюфера. Сделайте вывод о числе помеченных неподвешенных деревьев с $n$ вершинами.
166. Пусть 2 - множество из двух различных элементов, каждый из которых имеет вес 1. Можно условно называть их черный и белый. Что представляет собой $Seq(2)$? Посчитайте число элементов для него, в зависимости от веса.
167. Что представляет собой $Set(2)$? Посчитайте число элементов для него, в зависимости от веса.
168. Что представляет собой $MSet(2)$? Посчитайте число элементов для него, в зависимости от веса.
169. Что представляет собой $Cycle(2)$? Посчитайте число элементов для него, в зависимости от веса.
170. Пусть $F$ - множество из двух различных элементов, один из которых имеет вес 1, а другой - 2. Можно условно называть их маленький и большой. Что представляет собой $Seq(F)$? Посчитайте число элементов для него, в зависимости от веса.
171. Что представляет собой $Set(F)$? Посчитайте число элементов для него, в зависимости от веса.
172. Что представляет собой $MSet(F)$? Посчитайте число элементов для него, в зависимости от веса.
173. Что представляет собой $Cycle(F)$? Посчитайте число элементов для него, в зависимости от веса.
174. Пусть $A$ - комбинаторные объекты. Выведите формулу для числа элементов в зависимости от веса для $Pair(Seq(A), Seq(A))$.
175. Пусть $A$ - комбинаторные объекты. Обозначим как $Seq^+(A)$ множество непустых последовательностей из элементов $A$. Выведите рекуррентную формулу для числа элементов в зависимости от веса для $Seq^+(Seq^+(A))$.
176. Пусть $A$ - комбинаторные объекты. Обозначим как $Seq^1(A) = Seq^+(A)$, $Seq^k(A) = Seq^+(Seq^{k-1}(A))$. Выведите рекуррентную формулу для числа элементов в зависимости от веса для $Seq^k(A)$.
177. Разбиения на множества. Проинтерпретируйте разбиения $n$-элементного множества на $k$ множеств как конструируемый помеченный комбинаторный объект. Получите альтернативную рекуррентную формулу для чисел Стирлинга 2 рода.
178. Разбиения на циклы. Проинтерпретируйте разбиения $n$-элементного множества на $k$ циклов как конструируемый помеченный комбинаторный объект. Получите альтернативную рекуррентную формулу для чисел Стирлинга 1 рода.
179. Будем называть граф циклическим мультибамбуком, если он устроен следующим образом: есть цикл, из каждой вершины которого выходит путь. Предложите способ посчитать непомеченные циклические мультибамбуки.
180. Предложите способ посчитать помеченные циклические мультибамбуки.
181. Подсчет помеченных унициклических графов. Граф называется унициклическим, если он содержит ровно один цикл. Предложите способ подсчета помеченных унициклических графов.
182. Подсчет помеченных двудольных графов. Граф называется двудольным, если его вершины можно разбить на два множества, таких что ребра соединяют только вершины различных множеств. Сколько существует помеченных двудольных графов?
183. Подсчет помеченных связных двудольных графов. Сколько существует помеченных связных двудольных графов?