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

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. Последовательность $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. Последовательность $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. Докажите, что $(A(B(t))'=A'(B(t))\cdot B'(t)$
19. Формальный степенной ряд $(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)^{1/2}(1+s)^{1/2}=1+s$.
20. Докажите, что $(1+s)^\alpha(1+s)^\beta=(1+s)^{\alpha+\beta}$ для рациональных $\alpha$ и $\beta$.
21. Докажите, что $(1+s)^\alpha(1+s)^\beta=(1+s)^{\alpha+\beta}$.
22. Найдите производящую функцию для чисел "трибоначчи" $f_0=f_1=f_2=1$, $f_n = f_{n-1}+f_{n-2}+f_{n-3}$.
23. Найдите производящую функцию для последовательности, заданной рекуррентностью $f_0=f_1=f_2=1$, $f_n = f_{n-1}-2f_{n-3}$.
24. Производящая функция называется рациональной, если она представима в виде отношения двух многочленов. Для производящих функций каждой из следующих последовательностей выясните, является ли она рациональной, если да, приведите ее представление в таком виде. Последовательность $1, -2, 3, -4, 5, \ldots$.
25. Последовательность $0, 1, 8, 27, 64, 125, \ldots, k^3,\ldots$
26. Последовательность $1, 1, 4, 9, 25, \ldots, f_k^2,\ldots$ ($f_i$ --- числа Фибоначчи).
27. Последовательность $1, 1, 2, 6, \ldots, n!, \ldots$.
28. Несложно заметить, что производящая функция последовательности $a_n = n^m$ будет иметь вид $\frac {P_m(s)}{(1-s)^{m+1}}$. Выведите рекуррентное соотношение для коэффициентов многочленов $P_{m, k}$.
29. Оказывается, что коэффициенты $P_{m,k}$ также являются количеством некоторых комбинаторных объектов. Каких?
30. Пользуясь производящей функцией для чисел Фибоначчи, докажите утверждение, что $f_0+f_1+\ldots+f_n=f_{n+2}-1$.
31. Пользуясь производящей функцией для чисел Фибоначчи, докажите утверждение, что $f_0+f_2+\ldots+f_{2n}=f_{2n+1}$.
32. Пользуясь производящей функцией для чисел Фибоначчи, докажите утверждение, что $f_1+f_3+\ldots+f_{2n-1}=f_{2n}-1$.
33. Пользуясь производящей функцией для чисел Фибоначчи, докажите утверждение, что $f_0^2+f_1^2+f_2^2+\ldots+f_n^2=f_nf_{n+1}$.
34. Найдите производящую функцию для строк над алфавитом $\{0, 1\}$, не содержащих три нуля подряд.
35. Найдите производящую функцию для строк над алфавитом $\{0, 1\}$, не содержащих подстроки 010.
36. Найдите производящую функцию для строк над алфавитом $\{0, 1\}$, не содержащих подстроки 011.
37. Обозначим за $a_n$ количество способов разменять $n$ рублей монетами по $1$, $2$ и $5$ рублей (порядок монет важен). Постройте производящую функцию для $a_n$.
38. То же самое, что в предыдущем задании, но порядок монет не важен.