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

1. Пусть $R$ и $S$ - рефлексивные отношения на $A$. Будет ли рефлексивным их а) объединение? б) пересечение? В этом и следующих заданиях, если ответ отрицательный, при демонстрации контрпримера удобно использовать представление отношения в виде ориентированного графа.
2. Пусть $R$ и $S$ - симметричные отношения на $A$. Будет ли симметричным их а) объединение? б) пересечение?
3. Пусть $R$ и $S$ - транзитивные отношения на $A$. Будет ли транзитивным их а) объединение? б) пересечение?
4. Пусть $R$ и $S$ - антисимметричные отношения на $A$. Будет ли антисимметричным их а) объединение? б) пересечение?
5. Напомним, что композиция отношений $R$ и $S$ это отношение $T=RS$, где $xTy$, если найдется $z$, такой что $xRz$ и $zSy$. Пусть $R$ и $S$ - транзитивные отношения на $A$. Будет ли транзитивной их композиция?
6. Пусть $R$ и $S$ - антисимметричные отношения на A. Будет ли антисимметричной их композиция?
7. Определим $R^{-1}$ следующим образом: если $xRy$, то $yR^{-1}x$. Выполнено ли соотношение $RR^{-1} = I$, где $I$ - отношение равенства? Выполнен ли закон сложения степенией $R^iR^j=R^{i+j}$, если $i$ и $j$ разного знака?
8. Пусть $R$ обладает свойством $X$. Будет ли обладать свойством $X$ отношение $R^{-1}$? Следует проанализировать $X$ - рефлексивность, антирефлексивность, симметричность, антисимметричность, транзитивность
9. Постройте пример рефлексивного, симметричного, но не транзитивного отношения
10. Постройте пример рефлексивного, антисимметричного, но не транзитивного отношения
11. Постройте пример отношения, которое не симметрично и не антисимметрично
12. Постройте пример отношения, которое симметрично и антисимметрично
13. Является ли отношение $R$, такое что $(a, b) R (c, d)$, если $ad = bc$ на ${\mathbb Z}^+ \times {\mathbb N}$ отношением эквивалентности?
14. Может ли отношение частичного порядка быть отношением эквивалентности? Если да, то в каких случаях?
15. Можно ли в определении отношения эквивалентности убрать требование рефлексивности отношения, потому что оно следует из симметричности и транзитивности?
16. Транзитивный остов. Задано антисимметричное транзитивное отношение $R$ на $X$. Предолжите полиномиальный алгоритм построения отношения $S$, такого что $S^+=R$, причем в $S$ содержится минимальное число пар элементов.
17. В предыдущем задании требование транзитивности опустить нельзя. Задано антисимметричное отношение $R$ на $X$. Докажите, что если существует полиномиальный алгоритм построения отношения $S$, такого что $S \subset R$ и $S^+=R^+$, причем в $S$ содержится минимальное число пар элементов, то можно проверить, есть ли в графе гамильтонов цикл (цикл, проходящий по каждой вершине графа ровно один раз) за полиномиальное время.
18. СКНФ. Будем называть формулу для функции совершенной конъюнктивной нормальной формой, если ее эта формула является конъюнкцией клозов, каждый из которых представляет дизъюнкцию переменных и их отрицаний, причем каждая переменная встречается в каждом клозе ровно один раз. Докажите, что любую функцию, кроме тождественной 1, можно представить в виде СКНФ.
19. Стрелка Пирcа (NOR) - булева функция $a \downarrow b = \neg (a \vee b)$. Выразите в явном виде "и", "или" и "не" через стрелку Пирса
20. Штрих Шеффера (NAND) - булева функция $a \uparrow b = \neg (a \wedge b)$. Выразите в явном виде "и", "или" и "не" через штрих Шеффера
21. Булева функция называется пороговой, если $f(x_1, x_2, \ldots, x_n) = 1$ тогда и только тогда, когда $a_1x_1+a_2x_2+\ldots+a_nx_n \ge b$, где $a_i$ и $b$ - вещественные числа. Докажите, что "и", "или", "не" - пороговые функции.
22. Приведите пример непороговой функции
23. Можно ли "и", "или" и "не" выразить через функции из множества $\{x\oplus y, x = y\}$?
24. Можно ли "и", "или" и "не" выразить через функции из множества $\{x\to y, {\mathbf 0}\}$?
25. Можно ли "и", "или" и "не" выразить через функции из множества $\{\langle xyz\rangle, \neg x\}$?
26. Можно ли "и", "или" и "не" выразить через функции из множества $\{{\mathbf 0}, \langle xyz\rangle, \neg x\}$?
27. Можно ли выразить "и" через "или"?
28. Медиана $2n+1$ булевского значения равна 1 если и только если среди аргументов больше 1. Выразите медиану 5 через медиану 3
29. Выразите медиану $2n+1$ через медиану 3
30. Рассмотрим булеву функцию $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$
31. Говорят, что формула имеет вид 2-КНФ, если она имеет вид $(t_{11}\vee t_{12})\wedge(t_{21}\vee t_{22})\wedge\ldots$, где $t_{ij}$ представляет собой либо переменную, либо ее отрицание (в каждом дизъюнкте ровно два терма). Предложите полиномиальный алгоритм проверки, что формула, заданная в 2-КНФ имеет набор значений переменных, на которых она имеет значение 1.
32. КНФ называется КНФ Хорна, если в каждом дизъюнкте не более одной переменной находится без отрицания. Пример: $x\wedge(x \vee \neg y \vee \neg z) \wedge (\neg x \vee \neg t)$. Предложите полиномиальный алгоритм проверки, что формула, заданная в форме КНФ Хорна имеет набор аргументов, на котором она равна 1.
33. Функция $f$ называется самодвойственной, если $f(\neg x_1, \ldots, \neg x_n) = \neg f(x_1, \ldots, x_n)$. Сколько существует самодвойственных функций от $n$ аргуметов?
34. Будем говорить, что функция существенно зависит от переменной $x_i$, если существует два набора аргументов, различающихся только значением $x_i$, на которых функция принимает различные значения. Сколько существует булевых функций от $n$ аргументов, существенно зависящих от всех аргументов? Достаточно привести рекуррентную формулу.
35. Приведите пример функции, существенно зависящей хотя бы от 3 аргументов, которая лежит во всех 5 классах Поста.
36. Приведите пример функции, существенно зависящей хотя бы от 3 аргументов, которая не лежит ни в одном классе Поста.
37. Булева функция $f(x_1, x_2, \ldots, x_n)$ называется форсируемой, если существует такое назначение $x_i=const$ , что для любых значений других переменных значение функции является константой. Например, $x_1 \wedge x_2$ является форсируемой, поскольку при $x_1 = 0$ значение функции равно 0 для любого значения $x_2$. Для каждой функции от двух переменных определите, является ли она форсируемой.
38. Булева функция называется симметричной, если ее значение не меняется при любой перестановке ее переменных. Сколько существует симметричных функций от $n$ переменных?
39. Докажите, что любую функцию от $n$ переменных можно представить с использованием стрелки Пирса формулой, длиной не больше чем $2^n\cdot poly(n)$, где $poly(n)$ - полином, общий для всех функций
40. Докажите, что любую монотонную функцию можно выразить через "и", "или", 0 и 1.
41. Докажите, что любую монотонную самодвойственую функцию можно выразить через медиану
42. Докажите, что если булеву функцию $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$
43. Докажите, что если выполнено следствие: $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$ можно задать в форме Крома.
44. Докажите, что если булеву функцию $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$
45. Докажите, что если выполнено следствие: $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$ можно задать в форме Хорна
46. Докажите, что $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$.
47. Докажите, что биномиальный коэффициент $C_n^k$ нечетен тогда и только тогда, когда в двоичной записи $k$ единицы стоят только на тех позициях, где в двоичной записи $n$ также находятся единицы (иначе говоря, двоичная запись $k$ доминируется двоичной записью $n$ как двоичным вектором).
48. Докажите "метод треугольника" построения полинома Жегалкина по таблице истинности.
49. Постройте схему из функциональных элементов для операции медиана трех над базисом $\{ \vee, \wedge, \neg\}$. Постарайтесь использовать минимальное число элементов.
50. Постройте схему из функциональных элементов для операции $x \oplus y \oplus z$ над базисом $\{ \vee, \wedge, \neg\}$. Постарайтесь использовать минимальное число элементов.
51. Предложите способ построить схему для функции $x_1 \oplus ... \oplus x_n$ над базисом $\{ \vee, \wedge, \neg\}$ с линейным числом элементов и глубиной $O(\log n)$.
52. Докажите, что для функции "большинство из $2n+1$" существует схема из функциональных элементов глубины $O(\log n)$
53. Докажите, что любую булеву функцию от $n$ аргументов можно представить схемой из функциональных элементов, содержащей $O(n2^n)$ элементов.
54. Докажите, что любую булеву функцию от $n$ аргументов можно представить схемой из функциональных элементов, содержащей $O(2^n)$ элементов.
55. Докажите, что не существует схем константной глубины для функций $x_1 \vee ... \vee x_n$, $x_1 \wedge ... \wedge x_n$, $x_1 \oplus ... \oplus x_n$.
56. Докажите формулу разложения Шеннона по переменной $x$: $f(x, y_2, y_3, \ldots, y_n)=x\wedge f(1, y_2, y_3, \ldots, y_n)\vee \neg x\wedge f(0, y_2, y_3, \ldots, y_n)$
57. Для булевых векторов $\alpha$ и $\beta$ обозначим как $\alpha\vee\beta$ побитовое $\vee$ этих векторов, аналогично введём $\alpha \wedge \beta$. Обозначим как $\succeq$ отношение доминирования на булевых векторах, $\alpha\succeq\beta$, если для всех $i$ выполнено $a_i\ge b_i$. Докажите, что $\alpha \wedge \beta$ удовлетворяет свойству, что $(\alpha \succeq\gamma)\wedge(\beta \succeq \gamma) \Leftrightarrow (\alpha\wedge\beta)\succeq \gamma$. Докажите, что $\alpha \vee \beta$ удовлетворяет свойству, что $\gamma \succeq \alpha \wedge \gamma \succeq \beta \Leftrightarrow \gamma\succeq(\alpha\vee\beta)$.
58. Докажите равенства $\alpha \wedge(\beta\vee\gamma)=(\alpha \wedge\beta)\vee(\alpha\wedge\gamma)$ и $\alpha \vee(\beta\wedge\gamma)=(\alpha \vee\beta)\wedge(\alpha\vee\gamma)$.
59. Будем говорить, что булевый вектор $\alpha = (a_1, a_2, \ldots, a_n)$ префиксно мажорирует вектор $\beta = (b_1, b_2, \ldots, b_n)$, если для любого $k$ выполнено $a_1+\ldots+a_k \ge b_1+\ldots+b_k$ и писать $\alpha \ge_p \beta$. Докажите, что отношение $\ge_p$ является частичным порядком.
60. Докажите. что $\alpha$ префиксно мажорирует $\beta$ тогда и только тогда, когда $\overline{\beta}$ префиксно мажорирует $\overline{\alpha}$ ($\overline{\alpha}$ означает побитовую инверсию).
61. Докажите, что для любых двух векторов $\alpha$ и $\beta$ существует и единственный вектор $\alpha \curlywedge \beta$, такой что $\alpha \ge_p \gamma \wedge \beta \ge_p \gamma \Leftrightarrow (\alpha\curlywedge\beta)\ge_p\gamma$. Предложите алгоритм построения такого вектора.
62. Докажите, что для любых двух векторов $\alpha$ и $\beta$ существует и единственный вектор $\alpha \curlyvee \beta$, такой что $\gamma \ge_p \alpha \wedge \gamma \ge_p \beta \Leftrightarrow \gamma\ge_p(\alpha\curlyvee\beta)$. Предложите алгоритм построения такого вектора.
63. Докажите или опровергните равенства $\alpha \curlywedge(\beta\curlyvee\gamma)=(\alpha \curlywedge\beta)\curlyvee(\alpha\curlywedge\gamma)$ и $\alpha \curlyvee(\beta\curlywedge\gamma)=(\alpha \curlyvee\beta)\curlywedge(\alpha\curlyvee\gamma)$.
64. Будем называть функцию $f$ регулярной, если из $x \ge_p y$ следует, что $f(x) \ge f(y)$. Верно ли, что регулярная функция является монотонной?
65. Докажите, что если функция $f$ является пороговой и $a_1 \ge a_2 \ge \ldots \ge a_n \ge 0$, то $f$ является регулярной.
66. Мультиплексором называется схема, которая имеет $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}$. Постройте схему линейного (от суммарного количества входов и выходов) размера для мультиплексора.
67. Дешифратором называется схема, которая имеет $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}$. Постройте схему линейного (от суммарного количества входов и выходов) размера для дешифратора.
68. Контактной схемой называется ориентированный ациклический граф, на каждом ребре которого написана переменная или ее отрицание (ребра в контактных схемах называют контактами, а вершины - полюсами). Зафиксируем некоторые значения переменным. Тогда замкнутыми называются ребра, на которых записана 1, ребра, на которых записан 0, называются разомкнутыми. Зафиксируем две вершины $u$ и $v$. Тогда контактная схема вычисляет некоторую функцию $f$ между вершинами $u$ и $v$, равную 1 на тех наборах переменных, на которых между $u$ и $v$ есть путь по замкнутым ребрам. Постройте контактные схемы для функций ""и"", ""или"" и ""не"".
69. Постройте контактную схему для функции ""xor"".
70. Постройте контактную схему для функции медиана трех.
71. Докажите, что любую булеву функцию можно представить контактной схемой.
72. Постройте контактную схему ""xor от $n$ переменных"", содержащую $O(n)$ ребер.
73. Постройте контактную схему ""большинство из $2n+1$ переменных"", содержащую $O(n)$ ребер.
74. Постройте контактную схему, в которой для каждого из $2^n$ наборов дизъюнкций переменных и их отрицаний есть пара вершин, между которыми реализуется эта дизъюнкция, используя $O(2^n)$ ребер.
75. Докажите, что любую булеву функцию можно представить контактной схемой, содержащей $O(2^n)$ ребер.
76. Будем интерпретировать битовые строки длины $n$ как целые числа с соответствующей двоичной записью. Заданы $n$-битные числа $v_0 < v_1 < \ldots < v_{m-1}$. Предложите алгоритм за $O(m)$, который по заданным числам и числу $j$ находит все такие пары индексов $i, k$, что $v_i \oplus 2^j = v_k$. Считайте, что операции с числами выполняются за $O(1)$.
77. Приведите пример формулы, которая одновременно (а) равна тождественному нулю (б) находится в форме Хорна (в) находится в форме Крома (г) содержит хотя бы 3 переменные
78. Докажите, что $(x \oplus 3x) \wedge ((x \oplus 3x) >> 1)=0$, где $>>$ означает битовый сдвиг вправо.
79. Предложите алгоритм, который для заданного $d \ge 3$ вычисляет $x^y\bmod 2^d$ для заданных $x$ и $y$, где $x$ нечетен, используя $O(d)$ сложений и битовых операций и одно умножение на $y$.
80. Предложите алгоритм, который по заданной своей таблицей истинности $n$-арной булевой функции строит за полином от $2^n$ монотонную булеву функцию, которая одновременно (а) мажорирует заданную на каждом входном наборе (б) имеет минимальное число входных наборов, на которых она равна 1.
81. Предложите алгоритм проверки, что можно выбрать удовлетворяющее назначение для формулы, которая является конъюнкцией клозов, каждый из которых является либо клозом Хорна, либо клозом Крома
82. Формулы с кванторами. Рассмотрим формулу с кванторами $Qx_1Qx_2\ldots Qx_n f(x_1, \ldots, x_n)$, где $Q$ может быть квантором ""существует"" или ""для любого"". Докажите, что если если $f(x_1,\ldots,x_n)$ имеет ровно $k$ удовлетворяющих её назначений переменных, то существует ровно $k$ (из $2^n$ возможных) формул с кванторами в указанной форме, которые являются истинными.
83. Как выглядит дерево Хаффмана для частот символов $1, 2, ..., 2^{n-1}$ (степени двойки) ?
84. Как выглядит дерево Хаффмана для частот символов $1, 1, 2, 3, ..., F_{n-1}$ (числа Фибоначчи)?
85. Докажите, что если размер алфавита - степень двойки и частоты никаких двух символов не отличаются в 2 или более раз, то код Хаффмана не лучше кода постоянной длины
86. Модифицируйте алгоритм Хаффмана, чтобы строить $k$-ичные префиксные коды
87. Обобщите неравенство Крафта-Макмиллана на $k$-ичные коды
88. Укажите, как построить дерево Хаффмана за линейное время, если символы уже отсортированы по частоте
89. Предложите алгоритм построения оптимального кода среди префиксных кодов с длиной кодового слова не более L бит
90. Предложите способ хранения информации об оптимальном префиксном коде для n-символьного алфавита, использующий не более $2n - 1 + n \lceil\log_2(n)\rceil$ бит ($\lceil x\rceil$ - округление $x$ вверх)
91. Можно ли разработать алгоритм, который сжимает любой файл не короче заданной величины $N$ хотя бы на 1 бит?
92. Приведите пример однозначно декодируемого кода оптимальной длины, который не является ни префиксным, ни развернутым префиксным
93. Для каких префиксных кодов существует строка, для которой он является кодом Хаффмана? Предложите алгоритм построения такой строки.
94. Пусть заданы пары $(u_i, v_i)$. Предложите полиномиальный алгоритм проверки, что существует код Хаффмана для некоторой строки, в котором $i$-е кодовое слово содержит $u_i$ нулей и $v_i$ единиц.
95. Докажите, что если в коде Хаффмана для некоторой строки $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)$.
96. Изучите коды Шеннона-Фано https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A8%D0%B5%D0%BD%D0%BD%D0%BE%D0%BD%D0%B0_%E2%80%94_%D0%A4%D0%B0%D0%BD%D0%BE. Приведите пример текста, для которого код Шеннона-Фано хуже кода Хаффмана.
97. Обобщите коды Шеннона-Фано на $k$-ичные коды.
98. При арифметическом кодировании может повезти и у достаточно длинной строки код получится коротким, хотя длина строки большая, и оценка на длину кода тоже большая. Приведите пример такой строки.
99. Для предыдущего задания приведите пример бесконечной последовательности строк возрастающей длины, для которых проявляется описанный эффект.
100. При арифметическом кодировании можно учитывать, что с учетом уже потраченных символов соотношения символов становятся другими и отрезок надо делить в другой пропорции. Всегда ли кодирование с таким уточнением лучше классического арифметического кодирования?
101. При арифметическом кодировании трудным моментом является деление отрезка в пропорциях, не являющихся степенями двойки. Рассмотрим модификацию арифметического кодирования, когда соотношения между символами приближаются дробями со знаменателями - степенями двойки. Что можно сказать про получившийся алгоритм?
102. Проанализируйте время работы алгоритма арифиметического кодирования
103. Троичное арифметическое кодирование. Пусть при арифметичском кодировании мы используем в качестве знаменателя не $2^q$, а $3^q$, а числитель записываем как трочное число. Затем это число записывается в двоичной записи. Приведите пример строки, когда такой метод будет лучше классического арифметического кодирования.
104. Приведите пример строки, когда такой метод будет хуже классического арифметического кодирования.
105. Докажите, что для любого $c > 1$ существует распределение частот $p_1, p_2, .., p_n$, что арифметическое кодирование в $c$ раз лучше Хаффмана
106. Докажите, что при оптимальном кодирование с помощью LZ не выгодно делать повтор блока, который можно увеличить вправо
107. Разработайте алгоритм оптимального кодирования текста с помощью LZ, если на символ уходит $c$ бит, а на блок повтора $d$ бит
108. Предложите семейство строк $S_1, S_2, \ldots, S_n, \ldots$, где $S_i$ имеет длину $i$, таких, что при их кодировании с помощью LZW длина строки увеличивается. Начальный алфавит $\{0, 1\}$.
109. Предложите алгоритм декодирования кода Барроуза-Уиллера.
110. Предложите алгоритм декодирования кода Барроуза-Уиллера за $O(n)$.
111. Предложите реализацию преобразования Move to Front за $O(n \log n)$.
112. Предложите реализацию преобразования Move to Front за $O(n)$.
113. Докажите, что в зеркальном коде Грея $g_i = i \oplus \lfloor i / 2\rfloor$
114. Докажите, что в зеркальном коде Грея при переходе от $g_i$ к $g_{i+1}$ меняется тот же бит, который меняется с 0 на 1 при переходе от $i$ к $i+1$
115. Разработайте код Грея для k-ичных векторов
116. При каких $a_1, a_2, ..., a_n$ существует обход гиперпараллелепипеда $a_1 \times a_2 \times ... \times a_n$, который переходит каждый раз в соседнюю ячейку и бывает в каждой ячейке ровно один раз?
117. При каких $a_1, a_2, ..., a_n$ существует обход гиперпараллелепипеда $a_1 \times a_2 \times ... \times a_n$, который переходит каждый раз в соседнюю ячейку и бывает в каждой ячейке ровно один раз, а в конце возвращается в исходную ячейку?
118. Код ""антигрея"" - постройте двоичный код, в котором соседние слова отличаются хотя бы в половине бит
119. Троичный код ""антигрея"" - постройте троичный код, в котором соседние слова отличаются во всех позициях
120. При каких $n$ и $k$ существует двоичный $n$-битный код, в котором соседние кодовые слова отличаются ровно в $k$ позициях?
121. Докажите, что для достаточно больших $n$ существует код Грея, который отличается от любого, полученного из зеркального перестановкой столбцов, отражением и циклическим сдвигом строк
122. Код Грея назвается монотонным, если нет таких слов $g_i$ и $g_j$, что $i < j$, а $g_i$ содержит на 2 или больше единиц больше, чем $g_j$. Докажите, что существует монотонный код Грея
123. Выведите рекуррентную формулу для числа комбинаторных объектов: вектор длины $2n$, в котором каждое число от $1$ до $n$ встречается ровно два раза.
124. Коды Грея для перестановок. Предложите способ перечисления перестановок, в котором соседние перестановки отличаются обменом двух соседних элементов (элементарной транспозицией).
125. Коды Грея для сочетаний. Предложите способ перечисления сочетаний, в котором соседние сочетания отличаются заменой одного элемента.
126. Коды Грея для размещений. Предложите способ перечисления размещений, в котором соседние размещения отличаются заменой одного элемента в одной позиции.
127. Факториальная система счисления. Рассмотрим систему счисления, где бесконечно много цифр, в $i$-м разряде (нумерация разрядов с 1 от младшего к старшему) разрешается использовать цифры от 0 до $i$, вес $i$-го разряда $i!$. Докажите, что у каждого положительного числа ровно одно представление в факториальной системе счисления (с точностью до ведущих нулей). Предложите алгоритм перевода числа в факториальную систему счисления.
128. Как связана факториальная система счисления и нумерация перестановок?
129. Фибоначчиева система счисления. Рассмотрим систему счисления, где есть две цифры, 0 и 1. Пусть нумерация разрядов ведется с 1 от младшего к старшему, вес $i$-го разряда $F_i$, где $F_i$ - $i$-е число Фибоначчи ($F_0 = 1$, $F_1 = 1$, нулевой разряд не используется). При этом запрещается исползовать две единицы в соседних разрядах. Сколько представлений в Фибоначчиевой системе счисления у положительного числа $x$? Предложите алгоритм перевода числа в фибоначчиеву систему счисления.
130. Свяжите фибоначчиеву систему счисления с нумерацией каких-либо комбинаторных объектов.
131. Выразите $n \choose k$ через $n-1 \choose k-1$, $n$ и $k$.
132. Выразите $n \choose k$ через $n-1 \choose k$, $n$ и $k$.
133. Докажите, что ${n \choose m}{m \choose k}={n \choose k}{n-k \choose m - k}$.
134. Докажите, что $\sum\limits_{k=0}^n {m+k \choose k}={m+n+1 \choose n}$.
135. Докажите, что $\sum\limits_{k=0}^n {k \choose m}={n+1 \choose m+1}$.
136. Докажите, что $\sum\limits_{k=0}^n {r \choose k}{s \choose n - k}={r+s \choose n}$.
137. Докажите, что $\sum\limits_{k=0}^m {r \choose k}\left(\frac{r}{2} - k\right)=\frac{m+1}{2}{r \choose m+1}$. // Забавно, что нет простого выражения для $\sum\limits_{k=0}^m {r \choose k}$.
138. Обобщите формулу бинома Ньютона на степень суммы трёх: $(x+y+z)^n=?$
139. Докажите, что $\sum\limits_k{r \choose m + k}{s \choose n - k}={r+s \choose m+n}$. В этом и следующих заданиях сумма берётся по всем допустимым целым $k$.
140. Докажите, что $\sum\limits_k{r \choose m + k}{s \choose n + k}={r+s \choose r-m+n}$
141. Докажите, что $\sum\limits_k(-1)^k{r \choose m + k}{s+k \choose n}=(-1)^{r+n}{s-m \choose n-r}$
142. Докажите, что $\sum\limits_k(-1)^k{r-k \choose m}{s \choose k-n}=(-1)^{r+n}{s-m-1 \choose r-m-n}$
143. Докажите, что $\sum\limits_k{m-r+s\choose k}{n+r-s \choose n-k}{r+k \choose m+n}={r \choose m}{s \choose n}$
144. Вычислите сумму $\sum\limits_{k=0}^m{m \choose k}/{n \choose k}$.
145. Докажите, что $\sum\limits_k {n - k \choose k} = F_n$ ($n$-е число Фибоначчи).
146. Докажите, что число Каталана $C_n = \frac{1}{n+1}C_{2n}^n$.
147. Докажите, что число различных триангуляций правильного $n$-угольника равно числу Каталана. В этом и нескольких следующих заданиях номер соответствующего числа Каталана может отличаться от $n$, требуется также установить соответствие между размером задачи и номерами чисел Каталана.
148. Будем называть последовательность сортируемой стеком, если ее можно отсортировать, используя в произвольном порядке следующие операции: (а) взять первый элемент входной последовательности и положить в стек (б) взять верхний элемент стека и отправить в конец выходной последовательности. Докажите, что число перестановок $n$ элементов, сортируемых стеком, равно число Каталана.
149. Докажите, что число перестановок $n$ элементов, в которых нет возрастающей последовательности длины 3, равно числу Каталана.
150. Докажите, что число способов расставить числа от 1 до $2n$ в прямоугольник $2 \times n$, чтобы числа в каждой строке и каждом столбце возрастали, равно числу Каталана.
151. Укажите способ подсчитать число разбиений заданного $n$-элементного множества на $k$ упорядоченных непустых подмножеств (например, для $n = 3$, $k = 2$ есть следующие разбения: $\{[1], [2, 3]\}$, $\{[1], [3, 2]\}$, $\{[1, 2], [3]\}$, $\{[1, 3], [2]\}$, $\{[2, 1], [3]\}$, $\{[2], [3, 1]\}$.
152. Подъемом в перестановке называется пара соседних элементов, таких что $a_{i-1} < a_i$. Выведите рекуррентную формулу для числа перестановок $n$ элементов с $k$ подъемами
153. Неподвижной точкой в перестановке называется элемент $a_i = i$. Выведите рекуррентную формулу для числа перестановок $n$ элементов с $k$ неподвижными точками
154. Докажите формулу $t^{\overline{n}}=\sum\limits_{k=0}^n\left[n\atop k\right]t^k$
155. Докажите формулу $t^n=\sum\limits_{k=0}^n(-1)^{n-k}\left\{n\atop k\right\}t^{\overline k}$
156. Придумайте аналогичные двум предыдущим заданиям формулы для $t^{\underline{n}} = t (t - 1) \ldots (t-n+1)$.
157. Выведите рекуррентную формулу для числа перестановок $n$ элементов с $k$ циклами без неподвижных точек
158. Выведите рекуррентную формулу для числа разбиений числа $n$ на нечетные слагаемые
159. Выведите рекуррентную формулу для числа разбиений числа $n$ на нечетное число слагаемых
160. Выведите рекуррентную формулу для числа разбиений числа $n$ на различные слагаемые
161. Докажите, что число разбиений числа $n$ на нечетные слагаемые и число разбиений числа $n$ на различные слагаемые совпадает.
162. Для каких $n$ число разбиений $n$ на чётное число различных слагаемых и число разбиений $n$ на нечётное число различных слагаемых различно?
163. Выведите рекуррентную формулу для числа разбиений числа $a+ib$, где $a$ и $b$ целые неотрицательные числа, на комплексные слагаемые вида $c + id$, где $c$ и $d$ целые неотрицательные числа, хотя бы одно из которых положительно.
164. Раскрашенные слагаемые. Будем называть разбиение числа $n$ на положительные слагаемые раскрашенным, если каждому слагаемому сопоставлен один из $k$ заданных цветов. Два разбиения считаются одинаковыми, если слагаемые в одном из них можно переставить так, чтобы получилось другое разбиение (цвета после перестановки тоже должны совпасть). Выведите рекуррентную формулу для числа раскрашенных разбиений числа $n$ на слагаемые
165. Разноцветные слагаемые. Будем называть разбиение числа $n$ на положительные слагаемые разноцветным, если каждому слагаемому сопоставлен один из $k$ заданных цветов, причем одинаковым числам в разбиении не сопоставляются одинаковые цвета. Два разбиения считаются одинаковыми, если слагаемые в одном из них можно переставить так, чтобы получилось другое разбиение (цвета после перестановки тоже должны совпасть). Выведите рекуррентную формулу для числа разноцветных разбиений числа $n$ на слагаемые
166. Найдите число таких различных булевых функций от 2 переменных, что ни одна из них не может быть получена ни из какой другой навешиванием отрицаний над переменными
167. Найдите число таких различных булевых функций от $n$ переменных, что ни одна из них не может быть получена ни из какой другой навешиванием отрицаний над переменными
168. Выведите формулу для числа ожерелий из $n$ бусинок $k$ цветов с точностью до циклического сдвига и отражения.
169. Выведите формулу для числа ожерелий из $n$ бусинок 2 цветов с точностью до циклического сдвига, в которых ровно две белые бусины.
170. Выведите формулу для числа ожерелий из $n$ бусинок 2 цветов с точностью до циклического сдвига, в которых ровно $k$ белых бусин.
171. Пусть $p$ простое. Найдите число ожерелий из $p^2$ бусинок 2 цветов с точностью до циклического сдвига.
172. Пусть $p$ и $q$ простые. Найдите число ожерелий из $pq$ бусинок 2 цветов с точностью до циклического сдвига.
173. Выведите формулу для числа раскрасок $n$ шаров в $k$ цветов, порядок не важен.
174. Выведите формулу для числа раскрасок прямоугольника $n \times m$ в $k$ цветов с точностью до отражения относительно горизонтальной и вертикальной оси.
175. Выведите формулу для числа раскрасок граней тетраэдра в $k$ цветов с точностью до любого поворота в 3D.
176. Выведите формулу для числа раскрасок ребер тетраэдра в $k$ цветов с точностью до любого поворота в 3D.
177. Выведите формулу для числа раскрасок граней куба в $k$ цветов с точностью до любого поворота в 3D.
178. Выведите формулу для числа раскрасок ребер куба в $k$ цветов с точностью до любого поворота в 3D.
179. Выведите формулу для числа раскрасок граней октаэдра в $k$ цветов с точностью до любого поворота в 3D.
180. Почему мы не сделали задачу про вершины тетраэдра, вершины куба, вершины и ребра октаэдра? Неужели оставили на контрольную?
181. Пусть $3$ - множество из трёх различных элементов, каждый из которых имеет вес 1. Можно условно называть их красный, синий и зелёный. Что представляет собой $Seq(3)$? Посчитайте число элементов для него, в зависимости от веса.
182. Что представляет собой $Set(3)$? Посчитайте число элементов для него, в зависимости от веса.
183. Что представляет собой $MSet(3)$? Посчитайте число элементов для него, в зависимости от веса.
184. Что представляет собой $Cycle(3)$? Посчитайте число элементов для него, в зависимости от веса.
185. Пусть $F$ - множество из трёх различных элементов, два из которых имеют вес 1, а один - 2. Можно условно называть их маленький чёрный, маленький белый и большой. Что представляет собой $Seq(F)$? Посчитайте число элементов для него, в зависимости от веса.
186. Что представляет собой $Set(F)$? Посчитайте число элементов для него, в зависимости от веса.
187. Что представляет собой $MSet(F)$? Посчитайте число элементов для него, в зависимости от веса.
188. Что представляет собой $Cycle(F)$? Посчитайте число элементов для него, в зависимости от веса.
189. Пусть $U$ - множество, состоящее из одного атома веса 1. Обозначим как $Seq^+(U)$ множество непустых последовательностей из элементов $U$. Выведите формулу для числа элементов в зависимости от веса для $Seq^+(Seq^+(U))$.
190. Пусть $A$ - комбинаторные объекты, $a_i$ - число объектов веса $i$. Выведите рекуррентную формулу для числа элементов в зависимости от веса для $Seq^+(Seq^+(A))$.
191. Пусть $A$ - комбинаторные объекты. Выведите формулу для числа элементов в зависимости от веса для $Pair(Seq(A), Seq(A))$.
192. Укажите, как построить разбиения на слагаемые как конструируемый комбинаторный объект.
193. Укажите, как построить разбиения на множества как конструируемый комбинаторный объект.
194. Укажите, как построить разбиения на циклы как конструируемый комбинаторный объект.