Список заданий по ДМ 2к 2022 весна

1. Найдите производящую функцию для последовательности $0 \cdot 1, 1 \cdot 2, 2 \cdot 3, 3 \cdot 4, \ldots, (n - 1) \cdot n, \ldots$.
2. Найдите производящую функцию для последовательности $1^2, 2^2, 3^2, \ldots, n^2, \ldots$.
3. Последовательность $a_0, a_1, a_2, \ldots, a_k, \ldots$ имеет производящую функцию $A(t)=a_0 + a_1t + a_2t^2 + \ldots$. Найдите производящую функцию последовательности $a_0 + a_1, a_1 + a_2, \ldots, a_k+a_{k+1}, \ldots$
4. Последовательность $a_0, a_1, a_2, \ldots, a_k, \ldots$ имеет производящую функцию $A(t)=a_0 + a_1t + a_2t^2 + \ldots$. Найдите производящую функцию последовательности $a_0, a_0 + a_1, a_0 + a_1 + a_2, \ldots, \sum\limits_{i=0}^ka_i,\ldots$
5. (только для 34-35) Последовательность $a_0, a_1, a_2, \ldots, a_k, \ldots$ имеет производящую функцию $A(t) = a_0 + a_1t + a_2t^2 + \ldots$. Найдите производящую функцию последовательности $a_0, a_1b, a_2b^2, \ldots, a_kb^k, \ldots$
6. (только для 34-35) Последовательность $a_0, a_1, a_2, \ldots, a_k, \ldots$ имеет производящую функцию $A(t)=a_0 + a_1t + a_2t^2 + \ldots$. Найдите производящую функцию последовательности $a_0, 0, a_1, 0, a_2, 0, a_3 \ldots$
7. Последовательность $a_0, a_1, a_2, \ldots, a_k, \ldots$ имеет производящую функцию $A(t) = a_0 + a_1t + a_2t^2 + \ldots$. Найдите производящую функцию последовательности $a_0, a_2, a_4, a_6, \ldots$
8. Найдите производящую функцию для последовательности гармонических чисел $H_n = 1+1/2+\ldots+1/n$.
9. Формальный степенной ряд $\exp(t) = e^t$ определен как $e^t=1+\frac{1}{1!}t+\frac{1}{2!}t^2+\frac{1}{3!}t^3+\ldots+\frac{1}{n!}t^n+\ldots$. Логично, что $e^{-t}=1-\frac{1}{1!}t+\frac{1}{2!}t^2-\frac{1}{3!}t^3+\ldots+(-1)^n\frac{1}{n!}t^n+\ldots$. Докажите, используя определение умножения для степенных рядов, что $e^t e^{-t}=1$.
10. Определим $\alpha \choose n$ для любого $\alpha$, как $\frac {\alpha (\alpha - 1) \ldots (\alpha - n + 1)}{n!}$. Найдите простое выражение для ${-n} \choose k$ для натуральных $n$ и $k$. Опишите коэффициенты производящей функции $\frac {1}{(1-t)^n}$.
11. Формальный степенной ряд $\cos(t)$ определен как $\sum_{n=0}^{\infty} (-1)^n \frac {t^{2n}}{(2n)!}$, а $\sin(t)$ определен как $\sum_{n=0}^{\infty} (-1)^n \frac {t^{2n+1}}{(2n+1)!}$. Докажите, что $\sin^2(t) + \cos^2(t) = 1$.
12. Докажите, что $\sin(2t) = 2 \sin(t) \cos(t)$.
13. Найдите последовательность вещественных чисел $a_0, a_1, \ldots, a_n, \ldots$, удовлетовряющую условию $a_0=1$, $\sum\limits_{k=0}^n a_ka_{n-k} = 1$.
14. Пусть $B(t) = b_1 t + b_2 t^2 + b_3 t^3 + \ldots + b_n t^n + \ldots$, причем $b_1 \ne 0$. Пусть формальные степенные ряды $A(t)$ и $C(t)$ таковы, что $A(B(t)) = t$, $B(C(t))=t$. Докажите, что $A(t)=C(t)$. Этот ряд называется обратным к $B(t)$, обозначается как $B^{-1}(t)$.
15. Будем называть нулем степенной ряд $0(t) = 0 + 0t + 0t^2 + \ldots$. Докажите, что если $A(t) \ne 0(t)$, $B(t) \ne 0(t)$, то $A(t)B(t) \ne 0(t)$.
16. Докажите, что $(A(t)B(t))' = A'(t)B(t) + A(t)B'(t)$.
17. Докажите, что $\int(A'(t)B(t) + A(t)B'(t)) = A(t)B(t) - A(0)B(0)$.
18. (только для 36-39) Докажите, что $(A(B(t))'=A'(B(t))\cdot B'(t)$
19. Найдите производящую функцию для чисел ""трибоначчи"" $f_0=f_1=f_2=1$, $f_n = f_{n-1}+f_{n-2}+f_{n-3}$.
20. Найдите производящую функцию для последовательности, заданной рекуррентностью $f_0=f_1=f_2=1$, $f_n = f_{n-1}-2f_{n-3}$.
21. Производящая функция называется рациональной, если она представима в виде отношения двух многочленов. Для производящих функций каждой из следующих последовательностей выясните, является ли она рациональной, если да, приведите ее представление в таком виде. Последовательность $1, -2, 3, -4, 5, \ldots$.
22. Последовательность $0, 1, 8, 27, 64, 125, \ldots, k^3,\ldots$
23. Последовательность $1, 1, 4, 9, 25, \ldots, f_k^2,\ldots$ ($f_i$ --- числа Фибоначчи).
24. Последовательность $1, 1, 2, 6, \ldots, n!, \ldots$.
25. Несложно заметить, что производящая функция последовательности $a_n = n^m$ будет иметь вид $\frac {P_m(s)}{(1-s)^{m+1}}$. Выведите рекуррентное соотношение для коэффициентов многочленов $P_{m, k}$.
26. Оказывается, что коэффициенты $P_{m,k}$ также являются количеством некоторых комбинаторных объектов. Каких?
27. Пользуясь производящей функцией для чисел Фибоначчи, докажите утверждение, что $f_0+f_1+\ldots+f_n=f_{n+2}-1$.
28. Пользуясь производящей функцией для чисел Фибоначчи, докажите утверждение, что $f_0+f_2+\ldots+f_{2n}=f_{2n+1}$.
29. Пользуясь производящей функцией для чисел Фибоначчи, докажите утверждение, что $f_1+f_3+\ldots+f_{2n-1}=f_{2n}-1$.
30. Пользуясь производящей функцией для чисел Фибоначчи, докажите утверждение, что $f_0^2+f_1^2+f_2^2+\ldots+f_n^2=f_nf_{n+1}$.
31. Найдите производящую функцию для числа строк над алфавитом $\{0, 1\}$, не содержащих три нуля подряд.
32. Найдите производящую функцию для числа строк над алфавитом $\{0, 1\}$, не содержащих подстроки 010.
33. Найдите производящую функцию для числа строк над алфавитом $\{0, 1\}$, не содержащих подстроки 011.
34. Обозначим за $a_n$ количество способов разменять $n$ рублей монетами по $1$, $2$ и $5$ рублей (порядок монет важен). Постройте производящую функцию для $a_n$.
35. То же самое, что в предыдущем задании, но порядок монет не важен.
36. Последовательность задана рекуррентным соотношением $a_0=a_1=1$, $a_n = 6a_{n-1}-8a_{n-2}$. Оцените асимптотическое поведение $a_n$ при $n\to+\infty$.
37. Последовательность задана рекуррентным соотношением $a_0=a_1=1$, $a_n = 6a_{n-2}-a_{n-1}$. Оцените асимптотическое поведение $a_n$ при $n\to+\infty$.
38. Последовательность задана рекуррентным соотношением $a_0=a_1=1$, $a_n = 6a_{n-1}-9a_{n-2}$. Оцените асимптотическое поведение $a_n$ при $n\to+\infty$.
39. Последовательность задана рекуррентным соотношением $a_0=a_1=1$, $a_n = 2a_{n-1}-2a_{n-2}$. Оцените асимптотическое поведение $a_n$ при $n\to+\infty$.
40. Пусть рациональная производящая функция имеет вид $A(t) = \frac {P(t)}{Q(t)}$, где единственный минимальный по модулю корень $Q(t)$ равен $1 / \beta$ и имеет кратность $k$. Тогда $a_n \approx C \beta^n n^{k-1}$. Покажите, что $C = k \frac {(-\beta)^k P(1 / \beta)} {Q^{(k)}(1 / \beta)}$
41. Найдите ПФ последовательности $a_n$, где $a_n = n + 1$ для четных $n$, $a_n = 2^n$ для $n = 1, 5, \ldots, 4k+1, \ldots$, $a_n = 3^n$ для $n = 3, 7, \ldots, 4k+3, \ldots$; проанализируйте асимптотическое поведение.
42. Докажите, что если последовательность $a_n$ допускает представление в виде $a_n = \sum_i p_i(n)q_i^n$, где $p_i(n)$ - полиномы, и все $q_i$ различны, то такое представление единственно с точностью до порядка слагаемых.
43. Из производящей функции чисел Каталана $C(t) = \frac {1 - \sqrt{1-4t}} {2t}$ покажите, что $C_n = \frac {1}{n+1} {2n \choose n}$.
44. Путь Моцкина - путь, начинающийся в точке $(0, 0)$, составленный из векторов $(1, 1)$, $(1, 0)$, $(1, -1)$, не опускающийся ниже оси $OX$ и заканчивающийся в точке $(n, 0)$. Напишите рекуррентное соотношение для числа путей Моцкина, найдите производящую функцию для числа таких путей. Указание: в этом и нескольких следующих заданиях напишите рекуррентное соотношение, похожее на соотношение для чисел Каталана.
45. Рассмотрим множество путей на прямой, начинающихся в 0, состоящих из шагов длины 1 вправо или влево. Будем называть такой путь блужданием. Найдите рекуррентную формулу и производящую функцию для числа блужданий из $n$ шагов, оканчивающихся в 0.
46. Найдите рекуррентную формулу и производящую функцию для числа блужданий из $n$ шагов, оканчивающихся в фиксированной точке $N > 0$.
47. Найдите рекуррентную формулу и производящую функцию для числа блужданий из $n$ шагов, оканчивающихся в фиксированной точке $N > 0$ и не заходящих в отрицательную полупрямую.
48. Произведением Адамара двух производящих функций $A(t)$ и $B(t)$ называется призводящая функция для ряда $C(t) = a_0b_0+a_1b_1t+a_2b_2t^2+\ldots+a_nb_nt^n+\ldots$. Докажите, что если $A(t)$ и $B(t)$ являются рациональными, то и $C(t)$ рациональна.
49. Найдите произведение Адамара $\frac{1}{1-t}$ и $\frac{1}{1-2t}$.
50. Найдите произведение Адамара $\frac{1}{1-2t}$ и $\frac{1}{1-3t}$.
51. Найдите произведение Адамара $\frac{1}{1+3t-t^2}$ и $\frac{1}{1-2t}$.
52. Найдите произведение Адамара $\frac{1}{(1-3t)^2}$ и $\frac{1}{(1-2t)^2}$.
53. Найдите произведение Адамара $\frac{t}{1-3t+2t^2}$ и $\frac{2-4t}{1-4t+3t^2}$.
54. Один эксцентричный коллекционер покрытий при помощи домино $2 \times x$-прямоугольника платит 4 доллара за каждую вертикально расположенную костяшку и 1 доллар — за горизонтальную. Сколько покрытий будут оценены по этому способу ровно в $n$ долларов (для всех возможных $x$)? Найдите производящую функцию для числа таких покрытий.
55. Найдите производящую функцию для замощений прямоугольника $2\times n$ доминошками и единичными клетками.
56. Найдите производящую функцию для замощений прямоугольника $2\times n$ уголками (квадратами $2\times 2$ с вырезанной одной клеткой) и единичными клетками.
57. Найдите производящую функцию для замощений трехмерной колонны $2 \times 2 \times n$ кирпичами $2 \times 1\times 1$.
58. Неявное задание КО. (а) Пусть $A$, $B$ и $X$ - семейства комбинаторных объектов, причем $B \cap X = \varnothing$, $A = B \cup X$. Пусть производящие функции для $A$ и $B$ - $A(t)$ и $B(t)$, соответственно. Найдите производящую функцию $X(t)$. (б) Пусть $A$, $B$ и $X$ - семейства комбинаторных объектов, причем $A = B \times X$. Пусть производящие функции для $A$ и $B$ - $A(t)$ и $B(t)$, соответственно. Найдите производящую функцию $X(t)$. (в) Пусть $A$ и $X$ - семейства комбинаторных объектов, причем $A = Seq(X)$. Пусть производящая функция для $A$ - $A(t)$. Найдите производящую функцию $X(t)$.
59. Неявное задание КО 2. Пусть $A$ и $X$ - семейства комбинаторных объектов, причем $A = MSet(X)$. Пусть производящая функция для $A$ - $A(t)$. Докажите, что производящая функция для $X(t)$ равна $\sum\limits_{k\ge 1}\frac{\mu(k)}{k}\log A(t^k)$, где $\mu$ - функция Мёбиуса.
60. Пусть $A$ - семейство комбинаторных объектов с производящей функцией $A(t)$. Обозначим как $Seq^{\le k}(A)$ множество последовательностей длины не большей $k$, каждый элемент которого является последовательностью из не более чем $k$ объектов. Найдите производящую функцию для $Seq^{\le k}(A)$.
61. Пусть $A$ - семейство комбинаторных объектов с производящей функцией $A(t)$. Обозначим как $Seq^{\ge k}(A)$ множество последовательностей длины не меньшей $k$, каждый элемент которого является последовательностью из не менее чем $k$ объектов. Найдите производящую функцию для $Seq^{\ge k}(A)$.
62. Пусть $A$ - семейство комбинаторных объектов. Пусть $M = MSet(A)$, а $P = Set(A)$. Докажите, что $M(t) = P(t)M(t^2)$.
63. Пусть $A$ - семейство комбинаторных объектов с производящей функцией $A(t)$. Пусть $\mathbb{N}$ - множество натуральных чисел, (вес числа $k$ равен $k$). Пусть $T \subset \mathbb{N}$, обозначим как $T(t)$ производящую функцию для множества $T$. Обозначим как $Seq_T(A)$ множество последовательностей элементов из $A$, где длина последовательности лежит в множестве $T$. Обозначим как $Z$ множество из одного элемента веса $1$. Обозначим как $C^T$ множество представлений в виде суммы, где порядок слагаемых важен и слагаемые выбраны из множества $T$. Осознайте, что $C^T = Seq(Seq_T(Z))$. Найдите производящую функцию для $C^T$.
64. Докажите, что $\frac{1}{1-z}=\prod\limits_{j=0}^\infty(1+z^{2^j})$.
65. Обозначим как $F_n$ число Фибоначчи с номером $n$ ($F_0 = 1$, $F_1 = 1$, $F_k = F_{k - 1} + F_{k - 2}$). Чему равна сумма $\sum_{\substack{m \ge 0, \, k_i > 0 \\ k_1+k_2+\ldots+k_m=n}} F_{k_1}F_{k_2}\cdots F_{k_m}?$
66. Обозначим за $B$ множество всех конечных подмножеств $A$, в которых все элементы имеют различный вес. Выведите производящую функцию $B(t)$.
67. Определим множество "неориентированных последовательностей" $B = USeq(A)$, как множество всех последовательностей элементов из $A$, где последовательность $L$ и $rev(L)$ считаются одинаковыми. Покажите, что $B(t) = \frac 12 \frac {1}{1 - A(t)} + \frac 12 \frac {1 + A(t)}{1 - A(t^2)}$
68. Зафиксируем числа $k$ и $t$. Найдите производящую функцию для числа сочетаний из $n$ по $k$, где любые два выбранных числа отличаются как минимум на $t$. Исследуя ПФ, найдите количество таких сочетаний.
69. Зафиксируем числа $k$ и $t$. Найдите производящую функцию для числа сочетаний из $n$ по $k$, где разница между любыми соседними выбранными числами не больше $t$. Исследуя ПФ, найдите количество таких сочетаний.
70. Обозначим как $W$ множество всех слов над алфавитом $\{a, b\}$. Объясните равенство $W=Seq\{a\}\times Seq(\{b\}\times Seq\{a\})$. Проверьте равенство производящих функций.
71. Обозначим как $W^{e}$ множество слов над алфавитом $\{a, b\}$, где все отрезки подряд идущих букв $a$ имеют четную длину. Представьте $W^{e}$ как конструируемый комбинаторный объект. Найдите производящую функцию для $W^{e}$.
72. Обозначим как $W^{(k)}$ множество слов над алфавитом $\{a, b\}$, не содержащих $k$ букв $a$ подряд. Представьте $W^{(k)}$ как конструируемый комбинаторный объект. Найдите производящую функцию для $W^{(k)}$.
73. Постройте производящую функцию для строк над алфавитом $\{a, b\}$, содержащих заданную строку $s$ длины $k$ как подпоследовательность. Сделайте вывод об асимптотическом количестве таких строк.
74. Постройте производящую функцию для строк над алфавитом $\{a, b\}$, в которых нет более $k$ подряд идущих букв $a$ или $b$.
75. На лекции мы доказали, что если язык регулярный, то производящая функция его слов является рациональной. Докажите или опровергните обратное утверждение: если производящая функция слов языка является рациональной, то язык регулярный.
76. Постройте производящую функцию для строк над алфавитом $\{0, 1\}$, в которых число нулей делится на 3.
77. Постройте производящую функцию для строк над алфавитом $\{0, 1\}$, задающие числа в двоичной системе счисления, которые делятся на 3.
78. Из ПФ в предыдущем задании, найдите явную формулу для числа таких строк.
79. Постройте производящую функцию для строк над алфавитом $\{a, b\}$, удовлетворяющих регулярному выражению $(ab|a)^* | (ab|b)^*$
80. Найдите производящую функцию для строк, содержащих заданный паттерн $p$ как подстроку.
81. Рассмотрим бесконечную случайную строку из $0$ и $1$. Докажите, что матожидание позиции первого вхождения строки $p$ длины $k$ равно $2^k c(\frac 12)$, где $c(z)$ - автокорреляционный многочлен. Указание: можно использовать формулу $EX = \sum\limits_{n=0}^{\infty} P(X > n)$.
82. Обозначим как $P^T$ множество разбиений на слагаемые, где порядок слагаемых не важен, а слагаемые выбраны из множества $T$. Осознайте, что $P^T = MSet(Seq_T(Z))$. Найдите производящую функцию для $P^T$.
83. Постройте производящие функции для разбиений на различные слагаемые и на нечетные слагаемые. Покажите, что они совпадают.
84. Постройте производящую функцию для разбиений на слагаемые, не превосходящие $k$.
85. Постройте производящую функцию для разбиений на не больше, чем $k$ положительных слагаемых.
86. Индекс Хирша. Докажите, что $\prod\limits_{n=1}^\infty\frac{1}{1-z^n}=\sum\limits_{n\ge 1}\frac{z^{n^2}}{((1-z)\cdots(1-z^n))^2}$.
87. Будем обозначать $Seq_T$, $Cyc_T$, $Set_T$ соответственно последовательности, циклы и множества, размер которых принадлежит множеству $T$. Опишите класс помеченных объектов $Set(Cyc_{> 1}(Z))$. Найдите его экспоненциальную производящую функцию.
88. Для производящей функции из прошлого задания найдите явную формулу и асимптотическое поведение количества объектов веса $n$.
89. Опишите класс помеченных объектов $Set(Cyc_{1, 2}(Z))$. Найдите его экспоненциальную производящую функцию.
90. Сюрьекции на $r$-элементное множество. Осознайте, что $Seq_{=r}(Set_{\ge 1}(Z))$ задаёт сюрьекции на $r$-элементное множество. Найдите экспоненциальную производящую функцию.
91. Разбиения на $r$ множеств. Осознайте, что $Set_{=r}(Set_{\ge 1}(Z))$ задаёт разбиения на $r$ множеств. Найдите экспоненциальную производящую функцию. Чему равен коэффициент при $z^n$?
92. Числа Белла. Число Белла $b_n$ равно числу разбиений $n$-элементного множества на подмножества (число подмножеств не фиксировано). Докажите, что экспоненциальная производящая функция для чисел Белла равна $e^{e^z-1}$.
93. Гиперболический синус $\mathrm{sh}\,z$ равен $\frac{1}{2}(e^{z}-e^{-z})$. Гиперболический косинус $\mathrm{ch}\,z$ равен $\frac{1}{2}(e^{z}+e^{-z})$. Рассмотрим разбиения $n$-элементного множества на непустые подмножества. Докажите, что для разбиений на нечетное число подмножеств экспоненциальная производящая функция равна $\mathrm{sh}(e^z-1)$. Докажите, что для разбиений на четное число подмножеств экспоненциальная производящая функция равна $\mathrm{ch}(e^z-1)$.
94. Докажите, что для разбиений на произвольное число подмножеств, каждое из которых содержит нечетное число элементов, экспоненциальная производящая функция равна $e^{\mathrm{sh}\,z}$. Докажите, что для разбиений на произвольное число подмножеств, каждое из которых содержит четное число элементов, экспоненциальная производящая функция равна $e^{\mathrm{ch}\,z-1}$. Почему здесь в показателе степени есть $-1$, а в предыдущем пункте нет?
95. Обобщите два предыдущих задания. Как выглядят экспоненциальные производящие функции для разбиений на (не)четное число подмножеств, каждое из которых содержит (не)четное число элементов? (Необходимо дать четыре ответа для всех комбинаций)
96. Найдите экспоненциальную производящую функцию числа строк из 0 и 1, в которых четное число единиц.
97. Найдите экспоненциальную производящую функцию числа строк из букв a..z, в которых каждая гласная буква (aeiou) встречается нечетное число раз.
98. Из вида ЭПФ, найдите явную формулу числа строк из предыдущего задания.
99. Постройте экспоненциальную производящую функцию для перестановок, состоящих из четных циклов
100. Постройте экспоненциальную производящую функцию для перестановок, состоящих из нечетных циклов.
101. Докажите, что для четного $n$ количество перестановок, в которых все циклы четные, и количество перестановок, в которых все циклы нечетные, совпадают.
102. "Произведение с коробочкой": Обозначим $C = A^{\square} \times B$, как множество упорядоченных пар объектов из $A$ и $B$ со всеми возможными нумерациями, где атом с номером $1$ принадлежит первому элементу пары. Выведите формулу для $C_n$.
103. Докажите, что если $C = A^{\square} \times B$, то $C'(z) = A'(z) \cdot B(z)$.
104. Комбинаторный объект "двоичная куча". Рассмотрим помеченные двоичные деревья, где каждая вершина имеет двух детей, левого и правого (любое из этих поддеревьев может быть пустым), а также число в родителе вершины меньше числа в самой вершине (так, вершина с номером 1 --- всегда корень). Используя комбинаторную конструкцию "произведение с коробочкой", составьте и решите уравнение на экспоненциальную производящую функцию для двоичных куч.
105. Обозначим за $G(t)$ экспоненциальную производящую функцию всех помеченных графов. Чему равно $g_n$? Выразите экспоненциальную производящую функцию связных помеченных графов, используя $G(t)$.
106. Найдите среднее число слагаемых, равных 1, в случайном упорядоченном разбиении числа $n$ на положительные слагаемые.
107. Найдите среднее число слагаемых, равных $k$, в случайном упорядоченном разбиении числа $n$ на положительные слагаемые.
108. Рассмотрим комбинаторный объект ""строки из 0 и 1, без двух 1 подряд"". Представьте его как конструируемый комбинаторный объект, найдите его ПФ от двух переменных ($A_{n, m}$ равно количеству строк длины $n$ из $m$ единиц).
109. Найдите асимптотический главный член среднего количества единиц в таких строках длины $n$.
110. Рассмотрим производящую функцию для непомеченных деревьев с порядком на детях, заданную уравнением $T(z) = \frac {z} {1 - T(z)}$. Введем производящую функцию $G(z)$, равную сумме $d+1$ по всем таким деревьям (где $d$ - степень корня). Докажите, что $G(z) = \frac {T(z)}{z} - 1$.
111. Найдите точное выражение для средней степени корня в деревьях из прошлого задания. Найдите предел при $n \to \infty$.
112. Используя формулу обращения Лагранжа, найдите количество корневых лесов, состоящих из $k$ непомеченных деревьев с порядком на детях, порядок деревьев важен.
113. Выразите дисперсию средней стоимости комбинаторных объектов веса $n$ через производящую функцию $A(z, u)$.
114. Напишите ЭПФ от двух переменных для числа функций из $n$-элементного множества в $m$-элементное.
115. Напишите ЭПФ от двух переменных для числа инъекций из $n$-элементного множества в $m$-элементное.
116. Напишите ЭПФ от двух переменных для числа сюрьекций из $n$-элементного множества в $m$-элементное.
117. Найдите среднюю степень корня в случайном дереве Кэли из $n$ вершин.
118. Возрастающе-убывающей перестановкой называется перестановка, которая поочередно возрастает и убывает: $x_1 < x_2 > x_3 < x_4 \ldots$. Обозначим количество возрастающе-убывающих перестановок размера $n$ как $a_n$. Докажите, что экспоненциальной производящей функцией для последовательности $a_n$ является $(1+\sin t)/\cos t$.
119. Производящая функция Ньютона. Для последовательности $g_0, g_1, \ldots, g_n, \ldots$ производящая функция Ньютона определена как $\dot G(z) = \sum_n g_n{z \choose n}$. Пусть выполнено равенство: $\dot H(z) = \dot F(z) \cdot \dot G(z)$. Как связаны последовательности $f_i$, $g_i$ и $h_i$?
120. Найдите ЭПФ для чисел Эйлера I рода
121. Найдите ЭПФ для чисел Эйлера II рода
122. В этом и следующих заданиях нужно выразить ПФД в замкнутом виде, возможно, используя $\zeta(s)$. Обозначим как $\sigma_k(n)$ сумму $d^k$, где $d$ пробегает все делители $n$ . Найдите ПФД для $\sigma_1(n)$
123. Найдите ПФД для $\sigma_k(n)$.
124. Найдите ПФД для последовательности $a_n$, где $a_n = 1$ если $n$ является квадратом целого числа, и $a_n = 0$ иначе.
125. Найдите ПФД для последовательности $a_n$, где $a_n = 1$ если $n$ свободно от квадратов, и $a_n = 0$ иначе.
126. Зная ПФД для последовательности $a_n$, найдите ПФД для последовательности $a_n \cdot \ln n$.
127. Функция Мангольдта $\Lambda_n$ равна $\ln p$, если $n = p^k$ для некоторого $k \ge 1$, и 0 иначе. Найдите ПФД для последовательности $\Lambda_n$.
128. Докажите, что если $f(n)$ - мультипликативная функция, то $g(n) = \sum\limits_{d | n} f(d)$ тоже мультипликативна.
129. Докажите, что свертка Дирихле двух мультипликативных функций мультипликативна.
130. Докажите, что обратная по Дирихле функция к мультипликативной функции мультипликативна.
131. Используя ПФД, докажите, что $\sum\limits_{d | n}\varphi(d) = n$
132. Используя ПФД, докажите, что $\sum\limits_{d | n}\sigma_1(d)\varphi(n/d) = n \sigma_0(n)$.
133. Назовем функцию полностью мультипликативной, если $f(ab) = f(a)f(b)$ для любых $a$ и $b$. Какие значения $f(n)$ достаточно задать, чтобы определить $f$ на всех положительных натуральных числах?
134. Найдите ПФД для функции $\lambda(n) = (-1)^k$, где $k$ - количество простых делителей $n$ (с учетом кратности). Чему равна $\sum\limits_{d | n} \lambda(d)$?
135. Рассмотрим строки из 0 и 1. Скажем, что строка $s$ периодичная, если ее можно представить как $k$ копий одной строки $p$: $s = p^k$ для некоторого $k > 1$. Выведите формулу для количества апериодичных строк для произвольного $n$. Указание: используйте формулу обращения Мебиуса.
136. Найдите ПФД для последовательности $a_n = $ количество упорядоченных разбиений числа $n$ на (не обязательно простые) $k$ множителей, множитель 1 разрешен.
137. Найдите ПФД для последовательности $a_n = $ количество упорядоченных разбиений числа $n$ на $\ge 0$ (не обязательно простых) множителей, множитель 1 запрещен.
138. Найдите ПФД для последовательности $a_n = 2^{\omega(n)}$, где $\omega(n)$ - количество различных простых делителей $n$.
139. Найдите ПФД для последовательности $a_n = 3^{\omega(n)}$, где $\omega(n)$ - количество различных простых делителей $n$.
140. Докажите, что объединение перечислимых языков перeчислимо, используя перечислители (без сведения к полуразрешителям).
141. Докажите, что пересечение перечислимых языков перeчислимо, используя перечислители.
142. Докажите, что конкатенация перечислимых языков перeчислима.
143. Докажите, что замыкание Клини перечислимого языка перeчислимо.
144. Докажите, что декартово произведение перечислимых языков перeчислимо.
145. Докажите, что проекция перечислимого языка пар на каждую из осей перечислима.
146. Пусть $A \subset \Sigma^*$. Функция $f:A \to \Sigma^*$ называется вычислимой, если существует программа, которая по входу $x \in A$ выдает $f(x)$, а на входах не из $A$ зависает. Приведите пример невычислимой функции.
147. Графиком функции $f$ называется множество пар $(x, f(x))$ для тех $x$, на которых $f$ определена. Докажите, что функция вычислима тогда и только тогда, когда ее график перечислим.
148. Докажите, что образ перечислимого множества под действием вычислимой функции перечислим.
149. Докажите, что прообраз перечислимого множества под действием вычислимой функции перечислим.
150. В этой и последующих задачах вместо разрешимых и перечислимых языков рассматриваются разрешимые и перечислимые множества натуральных чисел. Это на самом деле одно и то же, достаточно установить естественную биекцию между натуральными числами и словами в градуированном лексикографическом порядке. Теорема об униформизации. Пусть $F$ — перечислимое множество пар натуральных чисел. Докажите. что существует вычислимая функция $f$, определённая на тех и только тех $x$, для которых найдётся $y$, при котором $\langle x,y\rangle \in F$, причём значение $f(x)$ является одним из таких $y$
151. Даны два перечислимых множества $X$ и $Y$. Докажите, что найдутся два непересекающихся перечислимых множества $X'$ и $Y'$, таких что $X' \subset X$, $Y' \subset Y$, $X' \cup Y' = X \cup Y$.
152. Докажите, что если перечислимое множество перечислимо в возрастающем порядке, то оно является разрешимым.
153. Докажите, что любое бесконечное перечислимое множество содержит бесконечное разрешимое подмножество.
154. Покажите, что для всякой вычислимой функции $f$ существует вычислимая функция, являющаяся «псевдообратной» к $f$ в следующем смысле: область определения $g$ совпадает с областью значений $f$, и при этом $f(g(f(x))) = f(x)$ для всех $x$, при которых $f(x)$ определено.
155. Покажите, что следующие три свойства множества $X$ равносильны: (1) $X$ можно представить в виде $A \setminus B,$ где $A$ — перечислимое множество, а $B$ — его перечислимое подмножество; (2) $X$ можно представить в виде $A \setminus B$, где $A$ и $B$ — перечислимые множества; (3) $X$ можно представить в виде симметрической разности двух перечислимых множеств.
156. Покажите, что множество $X$ можно представить в виде $A\setminus (B \setminus C)$, где $A \supset B \supset C$ — перечислимые множества, если и только если его можно представить в виде симметрической разности трёх перечислимых множеств.
157. Покажите, что существует множество, которое можно представить в виде симметрической разности трёх перечислимых множеств, но нельзя представить в виде симметрической разности двух перечислимых множеств
158. Докажите, что если $A$ неперечислимо и $A \le_m B$, то $B$ неперечислимо.
159. Пусть $A$ перечислимо и $\mathbb{N} \setminus A \le_m A$. Что можно сказать про $A$?
160. Пусть $A$ перечислимо и $A \le_m \mathbb{N} \setminus A$. Что можно сказать про $A$?
161. Пусть дана функция $f : A \to \mathbb{N}$. Ее продолжением на множество $B \supset A$ называется функция $g:B \to \mathbb{N}$, что если $x\in A$, то $g(x) = f(x)$. Докажите, что существует вычислимая функция $f$, у которой не существует всюду определенного вычислимого продолжения.
162. Два перечислимых множества $A$ и $B$, где $A \cap B = \varnothing$ называются неотделимыми, если не сущестует разрешимых множеств $X$ и $Y$, таких что $A \subset X$, $B \subset Y$, $X \cap Y = \varnothing$. Покажите, что существуют неотделимые множества. Указание: рассмотрите множества пар $\langle p, x\rangle$, где $p$ - программа, возвращающая целое число, для некоторого условия.
163. Обобщите определение неотделимых множеств на счетное семейство множеств. Докажите, что существует счетное семейство неотделимых множеств.
164. Докажите, что множество программ, допускающих заданное конечное множество слов $x_1, \ldots, x_n$, перечислимо, но не разрешимо.
165. Докажите, что множество программ, допускающих бесконечное множество слов не разрешимо.
166. Докажите, что множество программ, зависающих на любом входе, не разрешимо.
167. Докажите, что множество программ, останавливающихся на своём собственном исходном коде, перечислимо, но не разрешимо.
168. Язык ограниченной задачи останова (bounded halting) $BH = \{ (p, t) | p$ завершается на пустом входе за $t$ шагов $\}$. Докажите, что $BH$ разрешим.
169. Докажите, что существует разрешимое множество пар, проекция которого на одну из осей не является разрешимой.
170. Докажите, что существует разрешимое множество пар, проекция которого на каждую из осей не является разрешимой.
171. Некоторое множество $S$ натуральных чисел разрешимо. Разложим все числа из $S$ на простые множители и составим множество $D$ всех простых чисел, встречающихся в этих разложениях. Можно ли утверждать, что множество $D$ перечислимо?
172. Некоторое множество $S$ натуральных чисел разрешимо. Разложим все числа из $S$ на простые множители и составим множество $D$ всех простых чисел, встречающихся в этих разложениях. Можно ли утверждать, что множество $D$ разрешимо?
173. Множество $A \subset \mathbb{N} \times \mathbb{N}$ разрешимо. Можно ли утверждать, что множество «нижних точек» множества $A$, то есть множество $B = \{\langle x,y\rangle | (\langle x,y\rangle \in A)$ и $(\langle x,z\rangle \not\in A$ для всех $z < y)\}$ является разрешимым?
174. В предыдущем задании можно ли утверждать, что $B$ перечислимо, если $A$ перечислимо?
175. Существует ли множество натуральных чисел $A$, к которому m-сводится любой множество натуральных чисел?
176. Множество называется m-полным, если к нему m-сводится любое перечислимое множество. Докажите, что универсальное множество является $m$-полным.
177. Докажите, что диагональ универсального множества (множество $\{u | (u, u) \in U\}$ является m-полным.
178. Используя теорему о рекурсии, докажите, что язык программ, которые останавливаются на пустом вводе, является неразрешимым. Является ли этот язык перечислимым?
179. Используя теорему о рекурсии, докажите, что язык программ, которые не останавливаются на пустом вводе, является неразрешимым. Является ли этот язык перечислимым?
180. Используя теорему о рекурсии, докажите, что язык программ, которые допускают бесконечное число слов, является неразрешимым.
181. Используя теорему о рекурсии, докажите, что язык программ, которые допускают свой собственный исходный код, является неразрешимым.
182. Докажите, что существуют две различные программы $p$ и $q$, такие что программа $p$ печатает текст программы $q$, а программа $q$ печатает текст программы $p$.
183. Докажите, что существует бесконечная последовательность различных программ $p_i$, такая что $p_1$ печатает пустую строку, а $p_i$ печатает текст программы $p_{i-1}$.
184. Докажите, что существует бесконечная последовательность различных программ $p_i$, такая что $p_i$ печатает текст программы $p_{i+1}$.
185. Докажите, что для любого конечного $n$ существует последовательность программ $p_1, p_2, \ldots, p_n$, что $p_i$ печатает текст $p_{i+1}$, а $p_n$ печатает текст $p_1$.
186. Докажите, что язык программ, для которых не существует более короткой программы, которая на любом входе ведёт себя так же, является неразрешимым.
187. Докажите, что язык программ, для которых не существует программы такой же длины, которая на любом входе ведёт себя так же, является либо конечным, либо неразрешимым.
188. Докажите, что для любой всюду определенной вычислимой функции $f$ найдется значение $n$, для которого $BB(n) > f(n)$.
189. Докажите, что для любой всюду определенной вычислимой функции $f$ найдется бесконечно много значений $n$, для которых $BB(n) > f(n)$.
190. Пусть для любой строки $s$ выполнено $K(s) \ge f(s)$, где $f$ — всюду определенная вычислимая функция. Докажите, что найдется константа $C$, такая что $f(s) \le C$ для любой $s$.
191. Рассмотрим функцию $S(n)$, равную максимальной длине строки, выводимой программой длины $n$ на пустом входе. Докажите, что $S(n)$ невычислима.
192. Рассмотрим произвольную всюду определенную вычислимую функцию $f : \Sigma^* \to \Sigma^*$. Докажите, что существует программа $p$, что $L(p) = L(f(p))$.
193. Докажите, что счётчиковые машины с одним счётчиком распознают больше языков, чем конечные автоматы.
194. Модифицируем счётчиковую машину: разрешим счётчикам хранить как положительные, так и отрицательные значения (сравнивать можно по прежнему только с нулём). Докажите, что получившаяся модель эквивалентна по вычислительной мощности обычной счётчиковой машине с тем же числом счётчиков.
195. Стековая машина с бесконечным числом стеков. Пусть у стековой машины бесконечное число стеков и специальный счётчик, который показывает, какой стек сейчас анализируется. Функция переходов: $delta: Q \times (\Sigma \cup \varepsilon) \times \Pi \to {\cal P}_{<+\infty}\left( Q \times \Pi^* \times \{-1, 0, +1\}\right)$, где последний компонент результата функции указывает, что происходит с номером текущего стека. Докажите, что такая машина эквивалентна машине с двумя стеками.
196. Модифицируем счётчиковую машину: разрешим на переходе сравнивать значение в счётчике не только с 0, но и с любым другим целым числом (общее число переходов должно быть конечно). Докажите, что получившаяся модель эквивалентна по вычислительной мощности обычной счётчиковой машине с тем же числом счётчиков.
197. Отберем у машины Тьюринга возможность перемещаться налево, но разрешим новую команду RESET, которая перемещает головку на первый символ входного слова. Докажите, что такая модификация не меняет вычислительной мощности машины Тьюринга.
198. Пусть машине Тьюринга разрешено производить запись в каждую ячейку ленты только два раза: если значение в этой ячейке менялось уже дважды, запрещается записывать туда другой символ. Докажите, что такая модификация не меняет вычислительной мощности машины Тьюринга.
199. Пусть машине Тьюринга разрешено производить запись в каждую ячейку ленты только один раз: если значение в этой ячейке уже менялось, запрещается записывать туда другой символ. Докажите, что такая модификация не меняет вычислительной мощности машины Тьюринга.
200. Докажите, что машина Тьюринга без возможности записи на ленту, эквивалентна по вычислительной мощности конечному автомату.
201. Докажите, что счётчиковые машины с одним счётчиком распознают меньше языков, чем автоматы с одним стеком, даже детерминированные.
202. Модифицируем счётчиковую машину: пусть зафиксировано число $b$ и разрешим счётчикам хранить только числа от $0$ до $b$. Какие языки распознают такие машины для различного числа счётчиков?
203. Вещественное число $\alpha$ называется вычислимым, если существует вычислимая функция $a$, которая по любому рациональному $\varepsilon > 0$ даёт рациональное приближение к $\alpha$ с ошибкой не более $\varepsilon$, то есть $|\alpha − a(\varepsilon)| \le \varepsilon$ для любого рационального $\varepsilon > 0$. Докажите, что число $\alpha$ вычислимо тогда и только тогда, когда множество рациональных чисел, меньших $\alpha$, разрешимо.
204. Докажите, что число $\alpha$ вычислимо тогда и только тогда, когда последовательность знаков представляющей его десятичной (или двоичной) дроби вычислима. Последовательность называется вычислимой, если существует программа, которая по номеру $i$ выдает соответствующий элемент последовательности $a_i$.
205. Докажите, что число $\alpha$ вычислимо тогда и только тогда, когда существует вычислимая последовательность рациональных чисел, вычислимо сходящаяся к $\alpha$ (последнее означает, что можно алгоритмически указать $N$ по $\varepsilon$ в стандартном $\varepsilon$-$N$-определении сходимости.)
206. Покажите, что сумма, произведение, разность и частное вычислимых вещественных чисел вычислимы.
207. Покажите, что корень многочлена с вычислимыми коэффициентами вычислим.
208. Сформулируйте и докажите утверждение о том, что предел вычислимо сходящейся последовательности вычислимых вещественных чисел вычислим.
209. Вещественное число $\alpha$ называют перечислимым снизу, если множество всех рациональных чисел, меньших $\alpha$, перечислимо. (Перечислимость сверху определяется аналогично.) Докажите, что число $\alpha$ перечислимо снизу тогда и только тогда, когда оно является пределом некоторой вычислимой возрастающей последовательности рациональных чисел.
210. Докажите, что действительное число вычислимо тогда и только тогда, когда оно перечислимо снизу и сверху.
211. Докажите, что множество функций-приближений для рациональных вычислимых чисел $\alpha$ является неразрешимым. Указание: вспомните теорему о рекурсии.
212. Покажите, что существуют перечислимые снизу, но не вычислимые числа. Указание: рассмотрим сумму ряда $\sum 2^{-k}$ по $k$ из какого-либо множества $P$.
213. Приведите пример невычислимого предела сходящейся (но не вычислимо) последовательности вычислимых чисел
214. Приведите пример невычислимого предела вычислимо сходящейся (но не вычислимой) последовательности вычислимых чисел
215. (только 34-35) Рассмотрим список слов $A = \{\alpha_1, \alpha_2, \ldots, \alpha_n\}$ над алфавитом $\Sigma$. Введем $n$ новых различных символов $d_1, d_2, \ldots, d_n$. Рассмотрим алфавит $\Sigma' = \Sigma \cup \{d_1, d_2, \ldots, d_n\}$. Рассмотрим КС-грамматику с одним нетерминалом $S$, алфавитом $\Sigma'$ и $n + 1$ правилом: $S \to \alpha_1 S d_1$, $S \to \alpha_2 S d_2, \ldots, S \to \alpha_n S d_n$, $S \to \varepsilon$. Язык, порождаемый этой грамматикой, называется языком списка $A$ и обозначается как $L_A$. Опишите все слова языка $L_A$.
216. Докажите, что для любого списка $A$ дополнение до его языка списка $\overline{L_A}$ является КС-языком. Указание: постройте МП-автомат для $\overline{L_A}$.
217. (только 34-35) Докажите, что проблема проверки пустоты пересечения двух КС-грамматик неразрешима.
218. Докажите, что проблема проверки эквивалентности двух КС-грамматик неразрешима.
219. Докажите, что проблема проверки, что язык заданной КС-грамматики совпадает с языком заданного регулярного выражения, неразрешима.
220. Докажите, что проблема проверки того, что любое слово можно породить в заданной КС-грамматике, неразрешима.
221. Докажите, что проблема проверки того, что язык одной заданной КС-грамматики входит в язык другой заданной КС-грамматики, неразрешима.
222. Докажите, что проблема проверки того, что язык заданного регулярного выражения входит в язык заданной КС-грамматики, неразрешима.
223. Докажите, что проблема проверки того, что язык заданной КС-грамматики содержит палиндром, неразрешима.
224. Пусть задано два списка $A$ и $B$. Докажите, что $\overline{L_A} \cup \overline{L_B}$ является регулярным тогда и только тогда, когда он совпадает с $\Sigma'^*$. Следовательно проблема проверки того, что КС-грамматика порождает регулярный язык, неразрешима.
225. Докажите, что проблема проверки того, что дополнение языка заданной КС-грамматики является КС-языком, неразрешима.
226. Односторонние исчисления. Рассмотрим конечный набор правил $P$ вида $\alpha \rightarrow \beta$. Будем говорить, что из слова $x$ выводится $y$ с помощью $P$, если можно получить $x$ из $y$, выполнив ноль или более раз замену подстроки $x$, совпадающей с $\alpha$ для некоторого правила на $\beta$ для этого правила. Докажите, что множество троек $(P, x, y)$, где из $x$ выводится $y$ с помощью $P$ неразрешимо.
227. Двусторонние исчисления. Рассмотрим конечный алфавит $\Sigma$ и набор правил вида $\alpha \leftrightarrow \beta$. Будем говорить, что слова $x$ и $y$ эквивалентны с точностью до $P$, если можно получить $x$ из $y$, выполнив ноль или более раз замену подстроки $x$, совпадающей с $\alpha$ для некоторого правила на $\beta$ для этого правила или $\beta$ для некоторого правила на $\alpha$ для этого правила. Докажите, что множество троек $(P, x, y)$, где $x$ эквивалентен $y$ с точность до $P$ неразрешимо.
228. Докажите, существует конкретное множество правил одностороннего исчисления $P$, что для него множество пар $(x, y)$, где из $x$ выводится $y$ с помощью $P$ неразрешимо.
229. Докажите, существует конкретное множество правил двустороннего исчисления $P$, что для него множество пар $(x, y)$, где $x$ эквивалентно $y$ с точностью до $P$ неразрешимо. (Это задание можно переформулировать в терминах полугрупп так: докажите, что существует полугруппа с конечным множеством образующих и конечным множеством соотношений, что проверка равенства слов в этой полугруппе неразрешима)
230. Предыдущее задание можно обобщить на группы: докажите, что существует группа с конечным множеством образующих и конечным множеством соотношений, что проверка равенства слов в этой группе неразрешима. Отличие от предыдущего задания: вместе с каждым символом $c$ существует также символ $c^{-1}$ и соотношения $cc^{-1}\leftrightarrow\varepsilon$, $c^{-1}c\leftrightarrow\varepsilon$.
231. Множество $A$ назвается эффективно бесконечным, если существует всюду определенная вычислимая функция $f$, которая по числу $n$ выводит $n$ различных элементов множества $A$. Докажите, что если множество $A$ содержит бесконечное перечислимое подмножество, то оно эффективно бесконечно.
232. Докажите, что если множество $A$ эффективно бесконечно, то оно содержит бесконечное перечислимое подмножество.
233. Обозначим как $L(p)$ множество слов, которые допускается программой $p$. Множество $A$ назвается эффективно неперечислимым, если существует всюду определенная вычислимая функция $f$, которая по программе $p$ указывает слово $x$, такое что $x \in L(p) \oplus A$. Докажите, что дополнение к диагонали универсального множества $\overline D$, где $D = \left\{p | \langle p, p\rangle \in U\right\}$, является эффективно неперечислимым.
234. Докажите, что дополнение к универсальному множеству $\overline U$ является эффективно неперечислимым.
235. Докажите, что любое эффективно неперечислимое множество является эффективно бесконечным.
236. Множество называется иммунным, если оно бесконечно, но не содержит бесконечных перечислимых подмножеств. Перечислимое множество называется простым, если дополнение к нему иммунно. Докажите, что существует простое множество.
237. Докажите, что множество является иммунным тогда и только тогда, когда оно не содержит бесконечных разрешимых подмножеств.