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

<wikitex>

1. Формальный степенной ряд $\exp(s) = e^s$ определен как $e^s=1+\frac{1}{1!}s+\frac{1}{2!}s^2+\frac{1}{3!}s^3+\ldots+\frac{1}{n!}s^n+\ldots$. Логично, что $e^{-s}=1-\frac{1}{1!}s+\frac{1}{2!}s^2-\frac{1}{3!}s^3+\ldots+(-1)^n\frac{1}{n!}s^n+\ldots$. Докажите, используя определение умножения для степенных рядов, что $e^se^{-s}=1$.
2. Формальный степенной ряд $(1+s)^\alpha$ определен как $(1+s)^\alpha=1+\frac{\alpha}{1}s+\frac{\alpha(\alpha-1)}{1 \cdot 2}s^2+\ldots+\frac{\alpha(\alpha-1)\ldots(\alpha-n+1)}{1 \cdot 2 \cdot\ldots\cdot n}s^n+\ldots$. Докажите, что $(1+s)^\alpha(1+s)^\beta=(1+s)^{\alpha+\beta}$.
3. Формальный степенной ряд $\ln\left(\frac{1}{1-s}\right)$ определен как $\ln\left(\frac{1}{1-s}\right)=s+\frac{1}{2}s^2+\frac{1}{3}s^3+\ldots+\frac{1}{n}s^n+\ldots$. Докажите, что $\exp\left(\ln\left(\frac{1}{1-s}\right)\right)=(1-s)^{-1}$.
4. Пусть $B(s) = b_1s+b_2s^2+b_3s^3+\ldots+b_ns^n+\ldots$, причем $b_1\ne 0$. Пусть формальные степенные ряды $A(s)$ и $C(s)$ таковы, что $A(B(s)) = s$, $B(C(s))=s$. Докажите, что $A(s)=C(s)$ Этот ряд называется обратным к $B(s)$, обозначается как $B^{-1}(s)$.
5. Докажите, что не существует формального степенного ряда $A(s)$, такого что $sA(s)=1$.
6. Будем называть нулем степенной ряд $0(s) = 0 + 0s + 0s^2 + \ldots$. Докажите, что $A(s) \ne 0(s)$, $B(s) \ne 0(s)$, то $A(s)B(s) \ne 0(s)$.
7. Пусть формальный степенной ряд $A(s)$ имеет целые коэффициенты. При каких условиях ряд $\frac{1}{A(s)}$ имеет целые коэффициенты?
8. Пусть формальный степенной ряд $A(s)$ имеет целые коэффициенты. При каких условиях ряд $A^{-1}(s)$ имеет целые коэффициенты?
9. Докажите, что $(A(s) + B(s))' = A'(s) + B'(s)$.
10. Докажите, что $(A(s)B(s))' = A'(s)B(s) + A(s)B'(s)$.
11. Докажите, что $\int(A'(s)B(s) + A(s)B'(s)) = A(s)B(s) - A(0)B(0)$.
12. Найдите производящую функцию для последовательности $1, 2, 3, \ldots, n, \ldots$.
13. Найдите производящую функцию для последовательности $0 \cdot 1, 1 \cdot 2, 2 \cdot 3, 3 \cdot 4, \ldots, (n - 1) \cdot n, \ldots$.
14. Найдите производящую функцию для последовательности $1^2, 2^2, 3^2, \ldots, n^2, \ldots$.
15. Производящая функция называется рациональной, если она представима в виде отношения двух многочленов. Для производящих функций каждой из следующих последовательностей выясните, является ли она рациональной, если да, приведите ее представление в таком виде. Последовательность $1, -2, 3, -4, 5, \ldots$.
16. Последовательность $2, -6, 12, \ldots, (-1)^k(k+1)(k+2),\ldots$
17. Последовательность $1, -4, 9, -16, \ldots, (-1)^k(k+1)^2,\ldots$
18. Последовательность $1, 1, 4, 9, 25, \ldots, F_k^2,\ldots$
19. Последовательность $a_0, a_1, a_2, \ldots, a_k, \ldots$ имеет производящую функцию $A(s)=a_0+a_1s+a_2s^2+\ldots$. Найдите производящую функцию последовательности $a_0 + a_1, a_1 + a_2, \ldots, a_k+a_{k+1}$
20. Последовательность $a_0, a_1, a_2, \ldots, a_k, \ldots$ имеет производящую функцию $A(s)=a_0+a_1s+a_2s^2+\ldots$. Найдите производящую функцию последовательности $a_0, a_0 + a_1, a_0 + a_1 + a_2, \ldots, \sum\limits_{i=0}^ka_i,\ldots$
21. Последовательность $a_0, a_1, a_2, \ldots, a_k, \ldots$ имеет производящую функцию $A(s)=a_0+a_1s+a_2s^2+\ldots$. Найдите производящую функцию последовательности $a_0, a_1b, a_2b^2, \ldots, a_kb^k, \ldots$
22. Последовательность $a_0, a_1, a_2, \ldots, a_k, \ldots$ имеет производящую функцию $A(s)=a_0+a_1s+a_2s^2+\ldots$. Найдите производящую функцию последовательности $a_0, 0, a_1, 0, a_2, 0, a_3 \ldots$
23. Последовательность $a_0, a_1, a_2, \ldots, a_k, \ldots$ имеет производящую функцию $A(s)=a_0+a_1s+a_2s^2+\ldots$. Найдите производящую функцию последовательности $a_0, a_2, a_4, a_6 \ldots$
24. Пользуясь производящей функцией для чисел Фибоначчи, докажите утверждение, что $f_0+f_1+\ldots+f_n=f_{n+2}-1$.
25. Пользуясь производящей функцией для чисел Фибоначчи, докажите утверждение, что $f_0+f_2+\ldots+f_{2n}=f_{2n+1}$.
26. Найдите производящую функцию для замощений прямоугольника $2\times n$ доминошками и единичными клетками.
27. Найдите производящую функцию для замощений прямоугольника $2\times n$ уголками (квадратами $2\times 2$ с вырезанной одной клеткой) и единичными клетками.
28. Найдите производящую функцию для чисел Каталана.
29. Произведением Адамара производящих функций $A(t) = a_0 + a_1t + a_2t^2 + \ldots$ и $B(t) = n_0 + n_1t + n_2t^2 + \ldots$ называется функция $C(t) = a_0b_0 + a_1b_1t + a_2b_2t^2 + \ldots$. Докажите, что если функции $A(t)$ и $B(t)$ рациональны, то такова и функция $C(t)$.
30. Ландо, 2.16
31. Является ли произведение Адамара для производящих функций допустимым конструировнием?
32. Ландо, 2.9
33. Ландо, 2.11 (а)
34. Ландо, 2.11 (б)
35. Ландо, 2.11 (в)
36. Ландо, 2.11 (г)
37. Ландо, 2.12
38. Как оценить асимптотическое поведение чисел Каталана, используя производящую функцию?
39. Докажите, что объединение перечислимых языков перичислимо.
40. Докажите, что пересечение перечислимых языков перичислимо.
41. Докажите, что конкатенация перечислимых языков перичислима.
42. Докажите, что замыкание Клини перечислимого языка перичислимо.
43. Докажите, что декартово произведение перечислимых языков перичислимо.
44. Докажите, что проекция перечислимого языка пар на каждую из осей перечислима.
45. Докажите, что функция вычислима тогда и только тогда, когда ее график перечислим.
46. Докажите, что образ перечислимого множества под действием вычислимой функции перечислим.
47. Докажите, что прообраз перечислимого множества под действием вычислимой функции перечислим.
48. Шень, задание 7
49. Шень, задание 8
50. Шень, задание 9
51. Шень, задание 10
52. Шень, задание 11
53. Шень, задание 12
54. Шень, задание 13
55. Шень, задание 14(а)
56. Шень, задание 14(б)
57. Шень, задание 14(в)
58. Шень, задание 14(г)
59. Шень, задание 14(д)
60. Шень, задание 14(е)
61. Шень, задание 14(ж)
62. Шень, задание 15
63. Шень, задание 16
64. Шень, задание 23
65. Шень, задание 24, разрешимым?
66. Шень, задание 24, перечислимым?
67. Шень, задание 25
68. Шень, задание 26
69. Используя теорему о рекурсии, докажите, что язык программ, которые останавливаются на пустом вводе, является неразрешимым. Является ли этот язык перечислимым? Как по-другому можно доказать неразрешимость этого языка?
70. Используя теорему о рекурсии, докажите, что язык программ, которые не останавливаются на пустом вводе, является неразрешимым. Является ли этот язык перечислимым? Как по-другому можно доказать неразрешимость этого языка?
71. Используя теорему о рекурсии, докажите, что язык программ, которые допускают бесконечное число слов, является неразрешимым. Как по-другому можно доказать неразрешимость этого языка?

</wikitex>