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

Материал из Викиконспекты
Перейти к: навигация, поиск
  1. Формальный степенной ряд $\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$.
  2. Определим $\alpha \choose n$ для любого $\alpha$, как $\frac {\alpha (\alpha - 1) \ldots (\alpha - n + 1)}{n!}$. Найдите простое выражение для ${-n} \choose k$ для натуральных $n$ и $k$.
  3. Формальный степенной ряд $\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$.
  4. Докажите, что $\sin(2t) = 2 \sin(t) \cos(t)$.
  5. Пусть $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)$.
  6. Будем называть нулем степенной ряд $0(t) = 0 + 0t + 0t^2 + \ldots$. Докажите, что если $A(t) \ne 0(t)$, $B(t) \ne 0(t)$, то $A(t)B(t) \ne 0(t)$.
  7. Докажите, что $(A(t)B(t))' = A'(t)B(t) + A(t)B'(t)$.
  8. Докажите, что $\int(A'(t)B(t) + A(t)B'(t)) = A(t)B(t) - A(0)B(0)$.
  9. Найдите производящую функцию для последовательности $0 \cdot 1, 1 \cdot 2, 2 \cdot 3, 3 \cdot 4, \ldots, (n - 1) \cdot n, \ldots$.
  10. Найдите производящую функцию для последовательности $1^2, 2^2, 3^2, \ldots, n^2, \ldots$.
  11. Последовательность $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$
  12. Последовательность $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$
  13. Последовательность $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$
  14. Последовательность $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$
  15. Последовательность $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$
  16. Производящая функция называется рациональной, если она представима в виде отношения двух многочленов. Для производящих функций каждой из следующих последовательностей выясните, является ли она рациональной, если да, приведите ее представление в таком виде. Восстановите рекуррентное соотношение для этих последовательностей. Последовательность $1, -2, 3, -4, 5, \ldots$.
  17. Последовательность $0, 1, 8, 27, 64, 125, \ldots, k^3,\ldots$
  18. Последовательность $1\cdot 2^0, 2\cdot 2^1, 3\cdot 2^2, \ldots (n + 1)\cdot 2^n, \ldots$
  19. Последовательность $1+1, 2+3, 4+9, \ldots, 2^n + 3^n, \ldots$
  20. Последовательность $1, 1, 4, 9, 25, \ldots, f_k^2,\ldots$ ($f_i$ --- числа Фибоначчи).
  21. Найдите производящую функцию для чисел "трибоначчи" $f_0=f_1=f_2=1$, $f_n = f_{n-1}+f_{n-2}+f_{n-3}$.
  22. Найдите производящую функцию для последовательности, заданной рекуррентностью $f_0=f_1=f_2=1$, $f_n = f_{n-1}-2f_{n-3}$.
  23. Пользуясь производящей функцией для чисел Фибоначчи, докажите утверждение, что $f_0+f_1+\ldots+f_n=f_{n+2}-1$.
  24. Пользуясь производящей функцией для чисел Фибоначчи, докажите утверждение, что $f_0+f_2+\ldots+f_{2n}=f_{2n+1}$.
  25. Пользуясь производящей функцией для чисел Фибоначчи, докажите утверждение, что $f_1+f_3+\ldots+f_{2n-1}=f_{2n}-1$.
  26. Пользуясь производящей функцией для чисел Фибоначчи, докажите утверждение, что $f_0^2+f_1^2+f_2^2+\ldots+f_n^2=f_nf_{n+1}$.
  27. Найдите производящую функцию для количества строк длины $n$ над алфавитом $\{0, 1\}$, не содержащих три нуля подряд.
  28. Найдите производящую функцию для количества строк длины $n$ над алфавитом $\{0, 1\}$, не содержащих подстроки 010.
  29. Найдите производящую функцию для количества строк длины $n$ над алфавитом $\{0, 1\}$, не содержащих подстроки 011.
  30. Обозначим за $a_n$ количество способов разменять $n$ рублей монетами по $1$, $2$ и $5$ рублей (порядок монет важен). Постройте производящую функцию для $a_n$.
  31. То же самое, что в предыдущем задании, но порядок монет не важен.
  32. Можно заметить, что производящая функция последовательности $a_n = n^m$ будет иметь вид $\frac {P_m(s)}{(1-s)^{m+1}}$. Выведите рекуррентное соотношение для коэффициентов многочленов $P_{m, k}$.
  33. Оказывается, что коэффициенты $P_{m,k}$ также являются количеством некоторых комбинаторных объектов. Вскройте архивы домашних заданий по комбинаторике за первый семестр и вспомните, каких.
  34. Последовательность задана рекуррентным соотношением $a_0=a_1=1$, $a_n = 6a_{n-1}-8a_{n-2}$. Оцените асимптотическое поведение $a_n$ при $n\to+\infty$.
  35. Последовательность задана рекуррентным соотношением $a_0=a_1=1$, $a_n = 6a_{n-2}-a_{n-1}$. Оцените асимптотическое поведение $a_n$ при $n\to+\infty$.
  36. Последовательность задана рекуррентным соотношением $a_0=a_1=1$, $a_n = 6a_{n-1}-9a_{n-2}$. Оцените асимптотическое поведение $a_n$ при $n\to+\infty$.
  37. Последовательность задана рекуррентным соотношением $a_0=a_1=1$, $a_n = 2a_{n-1}-2a_{n-2}$. Оцените асимптотическое поведение $a_n$ при $n\to+\infty$.
  38. Пусть рациональная производящая функция имеет вид $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)}$
  39. Докажите, что если последовательность $a_n$ допускает представление в виде $a_n = \sum_i p_i(n)q_i^n$, где $p_i(n)$ - полиномы, и все $q_i$ различны, то такое представление единственно с точностью до порядка слагаемых.
  40. Из производящей функции чисел Каталана $C(t) = \frac {1 - \sqrt{1-4t}} {2t}$ покажите, что $C_n = \frac {1}{n+1} {2n \choose n}$.
  41. Путь Моцкина - путь, начинающийся в точке $(0, 0)$, составленный из векторов $(1, 1)$, $(1, 0)$, $(1, -1)$, не опускающийся ниже оси $OX$ и заканчивающийся в точке $(n, 0)$. Напишите рекуррентное соотношение для числа путей Моцкина, найдите производящую функцию для числа таких путей. Указание: в этом и нескольких следующих заданиях напишите рекуррентное соотношение, похожее на соотношение для чисел Каталана.
  42. Рассмотрим множество путей на прямой, начинающихся в 0, состоящих из шагов длины 1 вправо или влево. Будем называть такой путь блужданием. Найдите рекуррентную формулу и производящую функцию для числа блужданий из $n$ шагов, оканчивающихся в 0.
  43. Найдите рекуррентную формулу и производящую функцию для числа блужданий из $n$ шагов, оканчивающихся в фиксированной точке $N > 0$.
  44. Найдите рекуррентную формулу и производящую функцию для числа блужданий из $n$ шагов, оканчивающихся в фиксированной точке $N > 0$ и не заходящих в отрицательную полупрямую.
  45. Произведением Адамара двух производящих функций $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)$ рациональна.
  46. Найдите произведение Адамара $\frac{1}{1-t}$ и $\frac{1}{1-2t}$.
  47. Найдите произведение Адамара $\frac{1}{1-2t}$ и $\frac{1}{1-3t}$.
  48. Найдите произведение Адамара $\frac{1}{1+3t-t^2}$ и $\frac{1}{1-2t}$.
  49. Найдите произведение Адамара $\frac{1}{(1-3t)^2}$ и $\frac{1}{(1-2t)^2}$.
  50. Найдите произведение Адамара $\frac{t}{1-3t+2t^2}$ и $\frac{2-4t}{1-4t+3t^2}$.
  51. Найдите производящую функцию для последовательности гармонических чисел $H_n = 1+1/2+\ldots+1/n$.
  52. Пусть $g_n$ задано рекуррентным соотношением: $g_0=1$, для $n>0$ выполнено $g_n=g_{n-1}+2g_{n-2}+\ldots+ng_{0}$. Найдите явную формулу для $g_n$. Найдите производящую функцию для $g_n$.
  53. Один эксцентричный коллекционер покрытий при помощи домино $2 \times x$-прямоугольника платит 4 доллара за каждую вертикально расположенную костяшку и 1 доллар — за горизонтальную. Сколько покрытий будут оценены по этому способу ровно в $n$ долларов (для всех возможных $x$)? Найдите производящую функцию для числа таких покрытий.
  54. Найдите производящую функцию для замощений прямоугольника $2\times n$ доминошками и единичными клетками.
  55. Найдите производящую функцию для замощений прямоугольника $2\times n$ уголками (квадратами $2\times 2$ с вырезанной одной клеткой) и единичными клетками.
  56. Найдите производящую функцию для замощений трехмерной колонны $2 \times 2 \times n$ кирпичами $2 \times 1\times 1$.
  57. Обозначим как $F_n$ число Фибоначчи с номером $n$ ($F_0 = 1$, $F_1 = 1$, $F_k = F_{k - 1} + F_{k - 2}$). Чему равна сумма $\sum_{\substack{m > 0, \, k_i > 0 \\ k_1+k_2+\ldots+k_m=n}} F_{k_1}F_{k_2}\cdots F_{k_m}?$
  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$ - семейство комбинаторных объектов. Пусть $M = MSet(A)$, а $P = Set(A)$. Докажите, что $M(t) = P(t)M(t^2)$.
  61. Пусть $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$.
  62. Докажите, что $\frac{1}{1-z}=\prod\limits_{j=0}^\infty(1+z^{2^j})$.
  63. Обозначим за $B$ множество всех конечных подмножеств $A$, в которых все элементы имеют различный вес. Выведите производящую функцию $B(t)$.
  64. Определим множество "неориентированных последовательностей" $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)}$
  65. Зафиксируем числа $k$ и $t$. Найдите производящую функцию для числа сочетаний из $n$ по $k$, где любые два выбранных числа отличаются как минимум на $t$. Исследуя ПФ, найдите количество таких сочетаний.
  66. Зафиксируем числа $k$ и $t$. Найдите производящую функцию для числа сочетаний из $n$ по $k$, где разница между любыми соседними выбранными числами не больше $t$. Исследуя ПФ, найдите количество таких сочетаний.
  67. Обозначим как $W$ множество всех слов над алфавитом $\{a, b\}$. Объясните равенство $W=Seq\{a\}\times Seq(\{b\}\times Seq\{a\})$. Проверьте равенство производящих функций.
  68. Обозначим как $W^{e}$ множество слов над алфавитом $\{a, b\}$, где все отрезки подряд идущих букв $a$ имеют четную длину. Представьте $W^{e}$ как конструируемый комбинаторный объект. Найдите производящую функцию для $W^{e}$.
  69. Обозначим как $W^{(k)}$ множество слов над алфавитом $\{a, b\}$, не содержащих $k$ букв $a$ подряд. Представьте $W^{(k)}$ как конструируемый комбинаторный объект. Найдите производящую функцию для $W^{(k)}$.
  70. Постройте производящую функцию для строк над алфавитом $\{a, b\}$, содержащих заданную строку $s$ длины $k$ как подпоследовательность. Сделайте вывод об асимптотическом количестве таких строк.
  71. Постройте производящую функцию для строк над алфавитом $\{a, b\}$, в которых нет более $k$ подряд идущих букв $a$ или $b$.
  72. На лекции мы доказали, что если язык регулярный, то производящая функция его слов является рациональной. Докажите или опровергните обратное утверждение: если производящая функция слов языка является рациональной, то язык регулярный.
  73. Постройте производящую функцию для строк над алфавитом $\{0, 1\}$, в которых число нулей делится на 3.
  74. Постройте производящую функцию для строк над алфавитом $\{0, 1\}$, задающие числа в двоичной системе счисления, которые делятся на 3.
  75. Постройте производящую функцию для строк над алфавитом $\{a, b\}$, удовлетворяющих регулярному выражению $(ab|a)^* | (ab|b)^*$
  76. Найдите производящую функцию для строк, содержащих заданный паттерн $p$ как подстроку.
  77. Рассмотрим бесконечную случайную строку из $0$ и $1$. Докажите, что матожидание позиции первого вхождения строки $p$ длины $k$ равно $2^k c(\frac 12)$, где $c(z)$ - автокорреляционный многочлен. Указание: можно использовать формулу $EX = \sum\limits_{n=0}^{\infty} P(X > n)$.
  78. Обозначим как $P^T$ множество разбиений на слагаемые, где порядок слагаемых не важен, а слагаемые выбраны из множества $T$. Осознайте, что $P^T = MSet(Seq_T(Z))$. Найдите производящую функцию для $P^T$.
  79. Постройте производящие функции для разбиений на различные слагаемые и на нечетные слагаемые. Покажите, что они совпадают.
  80. Постройте производящую функцию для разбиений на не больше, чем $k$ положительных слагаемых.
  81. Индекс Хирша. Докажите, что $\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}$.