Список заданий по ДМ 2к 2021 весна — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
 
(не показано 17 промежуточных версий 6 участников)
Строка 32: Строка 32:
 
# Можно заметить, что производящая функция последовательности $a_n = n^m$ будет иметь вид $\frac {P_m(s)}{(1-s)^{m+1}}$. Выведите рекуррентное соотношение для коэффициентов многочленов $P_{m, k}$.
 
# Можно заметить, что производящая функция последовательности $a_n = n^m$ будет иметь вид $\frac {P_m(s)}{(1-s)^{m+1}}$. Выведите рекуррентное соотношение для коэффициентов многочленов $P_{m, k}$.
 
# Оказывается, что коэффициенты $P_{m,k}$ также являются количеством некоторых комбинаторных объектов. Вскройте архивы домашних заданий по комбинаторике за первый семестр и вспомните, каких.
 
# Оказывается, что коэффициенты $P_{m,k}$ также являются количеством некоторых комбинаторных объектов. Вскройте архивы домашних заданий по комбинаторике за первый семестр и вспомните, каких.
 +
# Последовательность задана рекуррентным соотношением $a_0=a_1=1$, $a_n = 6a_{n-1}-8a_{n-2}$. Оцените асимптотическое поведение $a_n$ при $n\to+\infty$.
 +
# Последовательность задана рекуррентным соотношением $a_0=a_1=1$, $a_n = 6a_{n-2}-a_{n-1}$. Оцените асимптотическое поведение $a_n$ при $n\to+\infty$.
 +
# Последовательность задана рекуррентным соотношением $a_0=a_1=1$, $a_n = 6a_{n-1}-9a_{n-2}$. Оцените асимптотическое поведение $a_n$ при $n\to+\infty$.
 +
# Последовательность задана рекуррентным соотношением $a_0=a_1=1$, $a_n = 2a_{n-1}-2a_{n-2}$. Оцените асимптотическое поведение $a_n$ при $n\to+\infty$.
 +
# Пусть рациональная производящая функция имеет вид $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)}$
 +
# Докажите, что если последовательность $a_n$ допускает представление в виде $a_n = \sum_i p_i(n)q_i^n$, где $p_i(n)$ - полиномы, и все $q_i$ различны, то такое представление единственно с точностью до порядка слагаемых.
 +
# Из производящей функции чисел Каталана $C(t) = \frac {1 - \sqrt{1-4t}} {2t}$ покажите, что $C_n = \frac {1}{n+1} {2n \choose n}$.
 +
# Путь Моцкина - путь, начинающийся в точке $(0, 0)$, составленный из векторов $(1, 1)$, $(1, 0)$, $(1, -1)$, не опускающийся ниже оси $OX$ и заканчивающийся в точке $(n, 0)$. Напишите рекуррентное соотношение для числа путей Моцкина, найдите производящую функцию для числа таких путей. Указание: в этом и нескольких следующих заданиях напишите рекуррентное соотношение, похожее на соотношение для чисел Каталана.
 +
# Рассмотрим множество путей на прямой, начинающихся в 0, состоящих из шагов длины 1 вправо или влево. Будем называть такой путь блужданием. Найдите рекуррентную формулу и производящую функцию для числа блужданий из $n$ шагов, оканчивающихся в 0.
 +
# Найдите рекуррентную формулу и производящую функцию для числа блужданий из $n$ шагов, оканчивающихся в фиксированной точке $N > 0$.
 +
# Найдите рекуррентную формулу и производящую функцию для числа блужданий из $n$ шагов, оканчивающихся в фиксированной точке $N > 0$ и не заходящих в отрицательную полупрямую.
 +
# Произведением Адамара двух производящих функций $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)$ рациональна.
 +
# Найдите произведение Адамара $\frac{1}{1-t}$ и $\frac{1}{1-2t}$.
 +
# Найдите произведение Адамара $\frac{1}{1-2t}$ и $\frac{1}{1-3t}$.
 +
# Найдите произведение Адамара $\frac{1}{1+3t-t^2}$ и $\frac{1}{1-2t}$.
 +
# Найдите произведение Адамара $\frac{1}{(1-3t)^2}$ и $\frac{1}{(1-2t)^2}$.
 +
# Найдите произведение Адамара $\frac{t}{1-3t+2t^2}$ и $\frac{2-4t}{1-4t+3t^2}$.
 +
# Найдите производящую функцию для последовательности гармонических чисел $H_n = 1+1/2+\ldots+1/n$.
 +
# Пусть $g_n$ задано рекуррентным соотношением: $g_0=1$, для $n>0$ выполнено $g_n=g_{n-1}+2g_{n-2}+\ldots+ng_{0}$. Найдите явную формулу для $g_n$. Найдите производящую функцию для $g_n$.
 +
# Один эксцентричный коллекционер покрытий при помощи домино $2 \times x$-прямоугольника платит 4 доллара за каждую вертикально расположенную костяшку и 1 доллар — за горизонтальную. Сколько покрытий будут оценены по этому способу ровно в $n$ долларов (для всех возможных $x$)? Найдите производящую функцию для числа таких покрытий.
 +
# Найдите производящую функцию для замощений прямоугольника $2\times n$ доминошками и единичными клетками.
 +
# Найдите производящую функцию для замощений прямоугольника $2\times n$ уголками (квадратами $2\times 2$ с вырезанной одной клеткой) и единичными клетками.
 +
# Найдите производящую функцию для замощений трехмерной колонны $2 \times 2 \times n$ кирпичами $2 \times 1\times 1$.
 +
# Обозначим как $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}?$
 +
# Неявное задание КО. (а) Пусть $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)$.
 +
# Неявное задание КО 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$ - функция Мёбиуса.
 +
# Пусть $A$ - семейство комбинаторных объектов. Пусть $M = MSet(A)$, а $P = Set(A)$. Докажите, что $M(t) = P(t)M(t^2)$.
 +
# Пусть $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$.
 +
# Докажите, что $\frac{1}{1-z}=\prod\limits_{j=0}^\infty(1+z^{2^j})$.
 +
# Обозначим за $B$ множество всех конечных подмножеств $A$, в которых все элементы имеют различный вес. Выведите производящую функцию $B(t)$.
 +
# Определим множество "неориентированных последовательностей" $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)}$
 +
# Зафиксируем числа $k$ и $t$. Найдите производящую функцию для числа сочетаний из $n$ по $k$, где любые два выбранных числа отличаются как минимум на $t$. Исследуя ПФ, найдите количество таких сочетаний.
 +
# Зафиксируем числа $k$ и $t$. Найдите производящую функцию для числа сочетаний из $n$ по $k$, где разница между любыми соседними выбранными числами не больше $t$. Исследуя ПФ, найдите количество таких сочетаний.
 +
# Обозначим как $W$ множество всех слов над алфавитом $\{a, b\}$. Объясните равенство $W=Seq\{a\}\times Seq(\{b\}\times Seq\{a\})$. Проверьте равенство производящих функций.
 +
# Обозначим как $W^{e}$ множество слов над алфавитом $\{a, b\}$, где все отрезки подряд идущих букв $a$ имеют четную длину. Представьте $W^{e}$ как конструируемый комбинаторный объект. Найдите производящую функцию для $W^{e}$.
 +
# Обозначим как $W^{(k)}$ множество слов над алфавитом $\{a, b\}$, не содержащих $k$ букв $a$ подряд. Представьте $W^{(k)}$ как конструируемый комбинаторный объект. Найдите производящую функцию для $W^{(k)}$.
 +
# Постройте производящую функцию для строк над алфавитом $\{a, b\}$, содержащих заданную строку $s$ длины $k$ как подпоследовательность. Сделайте вывод об асимптотическом количестве таких строк.
 +
# Постройте производящую функцию для строк над алфавитом $\{a, b\}$, в которых нет более $k$ подряд идущих букв $a$ или $b$.
 +
# На лекции мы доказали, что если язык регулярный, то производящая функция его слов является рациональной. Докажите или опровергните обратное утверждение: если производящая функция слов языка является рациональной, то язык регулярный.
 +
# Постройте производящую функцию для строк над алфавитом $\{0, 1\}$, в которых число нулей делится на 3.
 +
# Постройте производящую функцию для строк над алфавитом $\{0, 1\}$, задающие числа в двоичной системе счисления, которые делятся на 3.
 +
# Постройте производящую функцию для строк над алфавитом $\{a, b\}$, удовлетворяющих регулярному выражению $(ab|a)^* | (ab|b)^*$
 +
# Найдите производящую функцию для строк, содержащих заданный паттерн $p$ как подстроку.
 +
# Рассмотрим бесконечную случайную строку из $0$ и $1$. Докажите, что матожидание позиции первого вхождения строки $p$ длины $k$ равно $2^k c(\frac 12)$, где $c(z)$ - автокорреляционный многочлен. Указание: можно использовать формулу $EX = \sum\limits_{n=0}^{\infty} P(X > n)$.
 +
# Обозначим как $P^T$ множество разбиений на слагаемые, где порядок слагаемых не важен, а слагаемые выбраны из множества $T$. Осознайте, что $P^T = MSet(Seq_T(Z))$. Найдите производящую функцию для $P^T$.
 +
# Постройте производящие функции для разбиений на различные слагаемые и на нечетные слагаемые. Покажите, что они совпадают.
 +
# Постройте производящую функцию для разбиений на не больше, чем $k$ положительных слагаемых.
 +
# Индекс Хирша. Докажите, что $\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}$.
 +
# Будем обозначать $Seq_T$, $Cyc_T$, $Set_T$ соответственно последовательности, циклы и множества, размер которых принадлежит множеству $T$. Опишите класс помеченных объектов $Set(Cyc_{> 1}(Z))$. Найдите его экспоненциальную производящую функцию.
 +
# Для производящей функции из прошлого задания найдите явную формулу и асимптотическое поведение количества объектов веса $n$.
 +
# Опишите класс помеченных объектов $Set(Cyc_{1, 2}(Z))$. Найдите его экспоненциальную производящую функцию.
 +
# Сюрьекции на $r$-элементное множество. Осознайте, что $Seq_{=r}(Set_{\ge 1}(Z))$ задаёт сюрьекции на $r$-элементное множество. Найдите экспоненциальную производящую функцию.
 +
# Разбиения на $r$ множеств. Осознайте, что $Set_{=r}(Set_{\ge 1}(Z))$ задаёт разбиения на $r$ множеств. Найдите экспоненциальную производящую функцию. Что стоит при $z^n$?
 +
# Числа Белла. Число Белла $b_n$ равно числу разбиений $n$-элементного множества на подмножества (число подмножеств не фиксировано). Докажите, что экспоненциальная производящая функция для чисел Белла равна $e^{e^z-1}$.
 +
# Гиперболический синус $\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)$.
 +
# Докажите, что для разбиений на произвольное число подмножеств, каждое из которых содержит нечетное число элементов, экспоненциальная производящая функция равна $e^{\mathrm{sh}\,z}$.
 +
# Докажите, что для разбиений на произвольное число подмножеств, каждое из которых содержит четное число элементов, экспоненциальная производящая функция равна $e^{\mathrm{ch}\,z-1}$. Почему здесь в показателе степени есть $-1$, а в предыдущем задании нет?
 +
# Обобщите четыре предыдущих задания. Как выглядят экспоненциальные производящие функции для разбиений на (не)четное число подмножеств, каждое из которых содержит (не)четное число элементов? (Необходимо дать четыре ответа для всех комбинаций)
 +
# Постройте экспоненциальную производящую функцию для перестановок, состоящих из четных циклов
 +
# Постройте экспоненциальную производящую функцию для перестановок, состоящих из нечетных циклов.
 +
# Докажите, что для четного $n$ количество перестановок, в которых все циклы четные, и количество перестановок, в которых все циклы нечетные, совпадают.
 +
# "Произведение с коробочкой": Обозначим $C = A^{\square} \times B$, как множество упорядоченных пар объектов из $A$ и $B$ со всеми возможными нумерациями, где атом с номером $1$ принадлежит первому элементу пары. Выведите формулу для $c_n$.
 +
# Докажите, что если $C = A^{\square} \times B$, то $C'(z) = A'(z) \cdot B(z)$.
 +
# Комбинаторный объект "двоичная куча". Рассмотрим помеченные двоичные деревья, где каждая вершина имеет двух детей, левого и правого (любое из этих поддеревьев может быть пустым), а также число в родителе вершины меньше числа в самой вершине (так, вершина с номером 1 --- всегда корень). Используя комбинаторную конструкцию "произведение с коробочкой", составьте и решите уравнение на экспоненциальную производящую функцию для двоичных куч.
 +
# Обозначим за $G(t)$ экспоненциальную производящую функцию всех помеченных графов. Чему равно $g_n$? Выразите производящую функцию связных помеченных графов, используя $G(t)$.
 +
# Найдите среднее число слагаемых, равных 1, в случайном упорядоченном разбиении числа $n$ на положительные слагаемые.
 +
# Найдите среднее число слагаемых, равных $k$, в случайном упорядоченном разбиении числа $n$ на положительные слагаемые.
 +
# Рассмотрим комбинаторный объект "строки из 0 и 1, без двух 1 подряд". Представьте его как конструируемый комбинаторный объект, найдите его ПФ от двух переменных ($A_{n, m}$ равно количеству строк из $n$ единиц и $m$ нулей.)
 +
# Найдите среднее количество нулей в таких строках длины $n$.
 +
# Рассмотрим производящую функцию для непомеченных деревьев с порядком на детях, заданную уравнением $T(z) = \frac {z} {1 - T(z)}$. Введем производящую функцию $G(z)$, равную сумме $d+1$ по всем таким деревьям (где $d$ - степень корня). Докажите, что $G(z) = \frac {T(z)}{z} - 1$.
 +
# Найдите точное выражение для средней степени корня в деревьях из прошлого задания. Найдите предел при $n \to \infty$.
 +
# Используя формулу обращения Лагранжа, найдите количество $k$-ичных деревьев с $n$ вершинами (каждая вершина 0 или $k$ детей).
 +
# Используя формулу обращения Лагранжа, найдите количество корневых лесов, состоящих из $k$ непомеченных деревьев с порядком на детях.
 +
# Напишите ЭПФ от двух переменных для числа функций из $n$-элементного множества в $m$-элементное.
 +
# Напишите ЭПФ от двух переменных для числа инъекций из $n$-элементного множества в $m$-элементное.
 +
# Напишите ЭПФ от двух переменных для числа сюрьекций из $n$-элементного множества в $m$-элементное.
 +
# Чему равен коэффициент при $u^mz^n$ в выражении $\ln(1+z)/(1-uz)$?
 +
# Возрастающе-убывающей перестановкой называется перестановка, которая поочередно возрастает и убывает: $x_1 < x_2 > x_3 < x_4 \ldots$. Обозначим количество возрастающе-убывающих перестановок размера $n$ как $a_n$. Докажите, что экспоненциальной производящей функцией для последовательности $a_n$ является $(1+\sin t)/\cos t$.
 +
# Производящая функция Ньютона. Для последовательности $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$?
 +
# Найдите ЭПФ для чисел Эйлера I рода
 +
# Найдите ЭПФ для чисел Эйлера II рода
 +
# При решении задач этой серии можно при выражении использовать $\zeta(s)$. Обозначим как $\sigma_k(n)$ сумму по всем $d|n$ значений $d^k$. Найдите ПФД для $\sigma_1(n)$
 +
# Найдите ПФД для $\sigma_k(n)$.
 +
# Найдите ПФД для последовательности $a_n = \sqrt{n}$.
 +
# Найдите ПФД для последовательности $a_n$, где $a_n = 1$ если $n$ квадрат целого числа, $a_n = 0$ иначе.
 +
# Найдите ПФД для последовательности $a_n$, где $a_n = 1$ если $n$ свободно от квадратов, $a_n = 0$ иначе.
 +
# Зная ПФД для последовательности $a_n$, найдите ПФД для последовательности $a_n \cdot \ln n$.
 +
# Докажите, что если $f(n)$  - мультипликативная функция, то $g(n) = \sum\limits_{d | n} f(d)$ тоже мультипликативна.
 +
# Докажите, что свертка Дирихле двух мультипликативных функций мультипликативна.
 +
# Докажите, что обратная по Дирихле функция к мультипликативной функции мультипликативна.
 +
# Используя ПФД, докажите, что $\sum\limits_{d | n}\varphi(d) = n$
 +
# Используя ПФД, докажите, что $\sum\limits_{d | n}\sigma_1(d)\varphi(n/d) = n \sigma_0(n)$.
 +
# Назовем функцию полностью мультипликативной, если $f(ab) = f(a)f(b)$ для любых $a$ и $b$. Какие значения $f(n)$ достаточно задать, чтобы определить $f$ на всех положительных натуральных числах?
 +
# Найдите ПФД для функции $\lambda(n) = (-1)^k$, где $k$ - количество простых делителей $n$ (с учетом кратности). Чему равна $\sum\limits_{d | n} \lambda(d)$?
 +
# Рассмотрим строки из 0 и 1. Скажем, что строка $s$ периодичная, если ее можно представить как $k$ копий одной строки $p$: $s = p^k$. Выведите формулу для количества апериодичных строк для произвольного $n$. Указание: используйте формулу обращения Мебиуса.
 +
# Найдите ПФД для последовательности $a_n = $ количество упорядоченных разбиений числа $n$ на (не обязательно простые) $k$ множителей, множитель 1 разрешен.
 +
# Найдите ПФД для последовательности $a_n = $ количество упорядоченных разбиений числа $n$ на $\ge 0$ (не обязательно простых) множителей, множитель 1 запрещен.
 +
# Найдите ПФД для последовательности $a_n = 2^{\omega(n)}$, где $\omega(n)$ - количество различных простых делителей $n$.
 +
# Докажите, что объединение перечислимых языков перeчислимо, используя перечислители (не выполняйте сведение к полуразрешителю).
 +
# Докажите, что пересечение перечислимых языков перeчислимо, используя перечислители.
 +
# Докажите, что конкатенация перечислимых языков перeчислима.
 +
# Докажите, что замыкание Клини перечислимого языка перeчислимо.
 +
# Докажите, что декартово произведение перечислимых языков перeчислимо.
 +
# Докажите, что проекция перечислимого языка пар на каждую из осей перечислима.
 +
# Пусть $A \subset \Sigma^*$. Функция $f:A \to \Sigma^*$ называется вычислимой, если существует программа, которая по входу $x \in A$ выдает $f(x)$, а на входах не из $A$ зависает. Приведите пример невычислимой функции.
 +
# Графиком функции $f$ называется множество пар $(x, f(x))$ для тех $x$, на которых $f$ определена. Докажите, что функция вычислима тогда и только тогда, когда ее график перечислим.
 +
# Докажите, что образ перечислимого множества под действием вычислимой функции перечислим.
 +
# Докажите, что прообраз перечислимого множества под действием вычислимой функции перечислим.
 +
# В этой и последующих задачах вместо разрешимых и перечислимых языков рассматриваются разрешимые и перечислимые множества натуральных чисел. Это на самом деле одно и то же, достаточно установить естественную биекцию между натуральными числами и словами в градуированном лексикографическом порядке. Теорема об униформизации. Пусть $F$ — перечислимое множество пар натуральных чисел. Докажите. что существует вычислимая функция $f$, определённая на тех и только тех $x$, для которых найдётся $y$, при котором $\langle x,y\rangle \in F$, причём значение $f(x)$ является одним из таких $y$
 +
# Даны два перечислимых множества $X$ и $Y$. Докажите, что найдутся два непересекающихся перечислимых множества $X'$ и $Y'$, таких что $X' \subset X$, $Y' \subset Y$, $X' \cup Y' = X \cup Y$.
 +
# Докажите, что если перечислимое множество перечислимо в возрастающем порядке, то оно является разрешимым.
 +
# Докажите, что любое бесконечное перечислимое множество содержит бесконечное разрешимое подмножество.
 +
# Покажите, что для всякой вычислимой функции $f$ существует вычислимая функция, являющаяся «псевдообратной» к $f$ в следующем смысле: область определения $g$ совпадает с областью значений $f$, и при этом $f(g(f(x))) = f(x)$ для всех $x$, при которых $f(x)$ определено.
 +
# Докажите, что если $A$ неперечислимо и $A \le_m B$, то $B$ неперечислимо.
 +
# Пусть $A$ перечислимо и $\mathbb{N} \setminus A \le_m A$. Что можно сказать про $A$?
 +
# Пусть $A$ перечислимо и $A \le_m \mathbb{N} \setminus A$. Что можно сказать про $A$?
 +
# Пусть дана функция $f : A \to \mathbb{N}$. Ее продолжением на множество $B \supset A$ называется функция $g:B \to \mathbb{N}$, что если $x\in A$, то $g(x) = f(x)$. Докажите, что существует вычислимая функция $f$, у которой не существует всюду определенного вычислимого продолжения.
 +
# Два перечислимых множества $A$ и $B$, где $A \cap B = \varnothing$ называются неотделимыми, если не сущестует разрешимых множеств $X$ и $Y$, таких что $A \subset X$, $B \subset Y$, $X \cap Y = \varnothing$. Покажите, что существуют неотделимые множества. Указание: рассмотрите множества пар $\langle p, x\rangle$, где $p$ - программа, возвращающая целое число, для некоторого условия.
 +
# Обобщите определение неотделимых множеств на счетное семейство множеств. Докажите, что существует счетное семейство неотделимых множеств.
 +
# Докажите, что множество программ, допускающих заданное конечное множество слов $x_1, \ldots, x_n$, перечислимо, но не разрешимо.
 +
# Докажите, что множество программ, допускающих бесконечное множество слов не разрешимо.
 +
# Докажите, что множество программ, зависающих на любом входе, не разрешимо.
 +
# Докажите, что множество программ, останавливающихся на своём собственном исходном коде, перечислимо, но не разрешимо.
 +
# Покажите, что следующие три свойства множества $X$ равносильны: (1) $X$ можно представить в виде $A \setminus B,$ где $A$ — перечислимое множество, а $B$ — его перечислимое подмножество; (2) $X$ можно представить в виде $A \setminus B$, где $A$ и $B$ — перечислимые множества; (3) $X$ можно представить в виде симметрической разности двух перечислимых множеств.
 +
# Покажите, что множество $X$ можно представить в виде $A\setminus (B \setminus C)$, где $A \supset B \supset C$ — перечислимые множества, если и только если его можно представить в виде симметрической разности трёх перечислимых множеств.
 +
# Покажите, что существует множество, которое можно представить в виде симметрической разности трёх перечислимых множеств, но нельзя представить в виде симметрической разности двух перечислимых множеств
 +
# Язык ограниченной задачи останова (bounded halting) $BH = \{ (p, t) | p$ завершается на пустом входе за $t$ шагов $\}$. Докажите, что $BH$ разрешим.
 +
# Докажите, что существует разрешимое множество пар, проекция которого на одну из осей не является разрешимой.
 +
# Докажите, что существует разрешимое множество пар, проекция которого на каждую из осей не является разрешимой.
 +
# Некоторое множество $S$ натуральных чисел разрешимо. Разложим все числа из $S$ на простые множители и составим множество $D$ всех простых чисел, встречающихся в этих разложениях. Можно ли утверждать, что множество $D$ перечислимо?
 +
# Некоторое множество $S$ натуральных чисел разрешимо. Разложим все числа из $S$ на простые множители и составим множество $D$ всех простых чисел, встречающихся в этих разложениях. Можно ли утверждать, что множество $D$ разрешимо?
 +
# Множество $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)\}$ является разрешимым?
 +
# В предыдущем задании можно ли утверждать, что $B$ перечислимо, если $A$ перечислимо?
 +
# Используя теорему о рекурсии, докажите, что язык программ, которые останавливаются на пустом вводе, является неразрешимым. Является ли этот язык перечислимым?
 +
# Используя теорему о рекурсии, докажите, что язык программ, которые не останавливаются на пустом вводе, является неразрешимым. Является ли этот язык перечислимым?
 +
# Используя теорему о рекурсии, докажите, что язык программ, которые допускают бесконечное число слов, является неразрешимым.
 +
# Используя теорему о рекурсии, докажите, что язык программ, которые допускают свой собственный исходный код, является неразрешимым.
 +
# Докажите, что существуют две различные программы $p$ и $q$, такие что программа $p$ печатает текст программы $q$, а программа $q$ печатает текст программы $p$.
 +
# Докажите, что существует бесконечная последовательность различных программ $p_i$, такая что $p_1$ печатает пустую строку, а $p_i$ печатает текст программы $p_{i-1}$.
 +
# Докажите, что существует бесконечная последовательность различных программ $p_i$, такая что $p_i$ печатает текст программы $p_{i+1}$.
 +
# Докажите, что для любого конечного $n$ существует последовательность программ $p_1, p_2, \ldots, p_n$, что $p_i$ печатает текст $p_{i+1}$, а $p_n$ печатает текст $p_1$.
 +
# Докажите, что язык программ, для которых не существует более короткой программы, которая на любом входе ведёт себя так же, является неразрешимым.
 +
# Докажите, что язык программ, для которых не существует программы такой же длины, которая на любом входе ведёт себя так же, является либо конечным, либо неразрешимым.
 +
# Busy Beaver. Функция $BB(n)$ возвращает длину максимальной строки, которую программа длины $n$ может вывести на пустом входе и завершиться. Докажите, что $BB$ является невычислимой.
 +
# Докажите, что для любой всюду определенной вычислимой функции $f$ найдется значение $n$, для которого $BB(n) > f(n)$.
 +
# Докажите, что для любой всюду определенной вычислимой функции $f$ найдется бесконечно много значений $n$, для которых $BB(n) > f(n)$.
 +
# Колмогоровская сложность. $K(s)$ это длина минимальной программы, которая на пустом входе выводит строку $s$ и завершается. Докажите, что $K$ является невычислимой.
 +
# Пусть для любой строки $s$ выполнено $K(s) \ge f(s)$, где $f$ — всюду определенная вычислимая функция. Докажите, что найдется константа $C$, такая что $f(s) \le C$ для любой $s$.
 +
# Специальное задание: выберите нетривиальный язык программирования и напишите на нём программу, которая выводит свой собственный код. Не используйте код из интернета, напишите сами. Языки программирования всех студентов в рамках одной группы должны быть различны.
 +
# Специальное задание: выберите нетривиальный язык программирования и напишите на нём программы, которые демонстрируют решение одного из заданий 172-175. В рамках одной группы пара (язык программирования - номер задания) должна быть уникальной. Выберите язык программирования, отличный от предыдущего задания.

Текущая версия на 15:56, 7 мая 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}$.
  82. Будем обозначать $Seq_T$, $Cyc_T$, $Set_T$ соответственно последовательности, циклы и множества, размер которых принадлежит множеству $T$. Опишите класс помеченных объектов $Set(Cyc_{> 1}(Z))$. Найдите его экспоненциальную производящую функцию.
  83. Для производящей функции из прошлого задания найдите явную формулу и асимптотическое поведение количества объектов веса $n$.
  84. Опишите класс помеченных объектов $Set(Cyc_{1, 2}(Z))$. Найдите его экспоненциальную производящую функцию.
  85. Сюрьекции на $r$-элементное множество. Осознайте, что $Seq_{=r}(Set_{\ge 1}(Z))$ задаёт сюрьекции на $r$-элементное множество. Найдите экспоненциальную производящую функцию.
  86. Разбиения на $r$ множеств. Осознайте, что $Set_{=r}(Set_{\ge 1}(Z))$ задаёт разбиения на $r$ множеств. Найдите экспоненциальную производящую функцию. Что стоит при $z^n$?
  87. Числа Белла. Число Белла $b_n$ равно числу разбиений $n$-элементного множества на подмножества (число подмножеств не фиксировано). Докажите, что экспоненциальная производящая функция для чисел Белла равна $e^{e^z-1}$.
  88. Гиперболический синус $\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)$.
  89. Докажите, что для разбиений на четное число подмножеств экспоненциальная производящая функция равна $\mathrm{ch}(e^z-1)$.
  90. Докажите, что для разбиений на произвольное число подмножеств, каждое из которых содержит нечетное число элементов, экспоненциальная производящая функция равна $e^{\mathrm{sh}\,z}$.
  91. Докажите, что для разбиений на произвольное число подмножеств, каждое из которых содержит четное число элементов, экспоненциальная производящая функция равна $e^{\mathrm{ch}\,z-1}$. Почему здесь в показателе степени есть $-1$, а в предыдущем задании нет?
  92. Обобщите четыре предыдущих задания. Как выглядят экспоненциальные производящие функции для разбиений на (не)четное число подмножеств, каждое из которых содержит (не)четное число элементов? (Необходимо дать четыре ответа для всех комбинаций)
  93. Постройте экспоненциальную производящую функцию для перестановок, состоящих из четных циклов
  94. Постройте экспоненциальную производящую функцию для перестановок, состоящих из нечетных циклов.
  95. Докажите, что для четного $n$ количество перестановок, в которых все циклы четные, и количество перестановок, в которых все циклы нечетные, совпадают.
  96. "Произведение с коробочкой": Обозначим $C = A^{\square} \times B$, как множество упорядоченных пар объектов из $A$ и $B$ со всеми возможными нумерациями, где атом с номером $1$ принадлежит первому элементу пары. Выведите формулу для $c_n$.
  97. Докажите, что если $C = A^{\square} \times B$, то $C'(z) = A'(z) \cdot B(z)$.
  98. Комбинаторный объект "двоичная куча". Рассмотрим помеченные двоичные деревья, где каждая вершина имеет двух детей, левого и правого (любое из этих поддеревьев может быть пустым), а также число в родителе вершины меньше числа в самой вершине (так, вершина с номером 1 --- всегда корень). Используя комбинаторную конструкцию "произведение с коробочкой", составьте и решите уравнение на экспоненциальную производящую функцию для двоичных куч.
  99. Обозначим за $G(t)$ экспоненциальную производящую функцию всех помеченных графов. Чему равно $g_n$? Выразите производящую функцию связных помеченных графов, используя $G(t)$.
  100. Найдите среднее число слагаемых, равных 1, в случайном упорядоченном разбиении числа $n$ на положительные слагаемые.
  101. Найдите среднее число слагаемых, равных $k$, в случайном упорядоченном разбиении числа $n$ на положительные слагаемые.
  102. Рассмотрим комбинаторный объект "строки из 0 и 1, без двух 1 подряд". Представьте его как конструируемый комбинаторный объект, найдите его ПФ от двух переменных ($A_{n, m}$ равно количеству строк из $n$ единиц и $m$ нулей.)
  103. Найдите среднее количество нулей в таких строках длины $n$.
  104. Рассмотрим производящую функцию для непомеченных деревьев с порядком на детях, заданную уравнением $T(z) = \frac {z} {1 - T(z)}$. Введем производящую функцию $G(z)$, равную сумме $d+1$ по всем таким деревьям (где $d$ - степень корня). Докажите, что $G(z) = \frac {T(z)}{z} - 1$.
  105. Найдите точное выражение для средней степени корня в деревьях из прошлого задания. Найдите предел при $n \to \infty$.
  106. Используя формулу обращения Лагранжа, найдите количество $k$-ичных деревьев с $n$ вершинами (каждая вершина 0 или $k$ детей).
  107. Используя формулу обращения Лагранжа, найдите количество корневых лесов, состоящих из $k$ непомеченных деревьев с порядком на детях.
  108. Напишите ЭПФ от двух переменных для числа функций из $n$-элементного множества в $m$-элементное.
  109. Напишите ЭПФ от двух переменных для числа инъекций из $n$-элементного множества в $m$-элементное.
  110. Напишите ЭПФ от двух переменных для числа сюрьекций из $n$-элементного множества в $m$-элементное.
  111. Чему равен коэффициент при $u^mz^n$ в выражении $\ln(1+z)/(1-uz)$?
  112. Возрастающе-убывающей перестановкой называется перестановка, которая поочередно возрастает и убывает: $x_1 < x_2 > x_3 < x_4 \ldots$. Обозначим количество возрастающе-убывающих перестановок размера $n$ как $a_n$. Докажите, что экспоненциальной производящей функцией для последовательности $a_n$ является $(1+\sin t)/\cos t$.
  113. Производящая функция Ньютона. Для последовательности $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$?
  114. Найдите ЭПФ для чисел Эйлера I рода
  115. Найдите ЭПФ для чисел Эйлера II рода
  116. При решении задач этой серии можно при выражении использовать $\zeta(s)$. Обозначим как $\sigma_k(n)$ сумму по всем $d|n$ значений $d^k$. Найдите ПФД для $\sigma_1(n)$
  117. Найдите ПФД для $\sigma_k(n)$.
  118. Найдите ПФД для последовательности $a_n = \sqrt{n}$.
  119. Найдите ПФД для последовательности $a_n$, где $a_n = 1$ если $n$ квадрат целого числа, $a_n = 0$ иначе.
  120. Найдите ПФД для последовательности $a_n$, где $a_n = 1$ если $n$ свободно от квадратов, $a_n = 0$ иначе.
  121. Зная ПФД для последовательности $a_n$, найдите ПФД для последовательности $a_n \cdot \ln n$.
  122. Докажите, что если $f(n)$ - мультипликативная функция, то $g(n) = \sum\limits_{d | n} f(d)$ тоже мультипликативна.
  123. Докажите, что свертка Дирихле двух мультипликативных функций мультипликативна.
  124. Докажите, что обратная по Дирихле функция к мультипликативной функции мультипликативна.
  125. Используя ПФД, докажите, что $\sum\limits_{d | n}\varphi(d) = n$
  126. Используя ПФД, докажите, что $\sum\limits_{d | n}\sigma_1(d)\varphi(n/d) = n \sigma_0(n)$.
  127. Назовем функцию полностью мультипликативной, если $f(ab) = f(a)f(b)$ для любых $a$ и $b$. Какие значения $f(n)$ достаточно задать, чтобы определить $f$ на всех положительных натуральных числах?
  128. Найдите ПФД для функции $\lambda(n) = (-1)^k$, где $k$ - количество простых делителей $n$ (с учетом кратности). Чему равна $\sum\limits_{d | n} \lambda(d)$?
  129. Рассмотрим строки из 0 и 1. Скажем, что строка $s$ периодичная, если ее можно представить как $k$ копий одной строки $p$: $s = p^k$. Выведите формулу для количества апериодичных строк для произвольного $n$. Указание: используйте формулу обращения Мебиуса.
  130. Найдите ПФД для последовательности $a_n = $ количество упорядоченных разбиений числа $n$ на (не обязательно простые) $k$ множителей, множитель 1 разрешен.
  131. Найдите ПФД для последовательности $a_n = $ количество упорядоченных разбиений числа $n$ на $\ge 0$ (не обязательно простых) множителей, множитель 1 запрещен.
  132. Найдите ПФД для последовательности $a_n = 2^{\omega(n)}$, где $\omega(n)$ - количество различных простых делителей $n$.
  133. Докажите, что объединение перечислимых языков перeчислимо, используя перечислители (не выполняйте сведение к полуразрешителю).
  134. Докажите, что пересечение перечислимых языков перeчислимо, используя перечислители.
  135. Докажите, что конкатенация перечислимых языков перeчислима.
  136. Докажите, что замыкание Клини перечислимого языка перeчислимо.
  137. Докажите, что декартово произведение перечислимых языков перeчислимо.
  138. Докажите, что проекция перечислимого языка пар на каждую из осей перечислима.
  139. Пусть $A \subset \Sigma^*$. Функция $f:A \to \Sigma^*$ называется вычислимой, если существует программа, которая по входу $x \in A$ выдает $f(x)$, а на входах не из $A$ зависает. Приведите пример невычислимой функции.
  140. Графиком функции $f$ называется множество пар $(x, f(x))$ для тех $x$, на которых $f$ определена. Докажите, что функция вычислима тогда и только тогда, когда ее график перечислим.
  141. Докажите, что образ перечислимого множества под действием вычислимой функции перечислим.
  142. Докажите, что прообраз перечислимого множества под действием вычислимой функции перечислим.
  143. В этой и последующих задачах вместо разрешимых и перечислимых языков рассматриваются разрешимые и перечислимые множества натуральных чисел. Это на самом деле одно и то же, достаточно установить естественную биекцию между натуральными числами и словами в градуированном лексикографическом порядке. Теорема об униформизации. Пусть $F$ — перечислимое множество пар натуральных чисел. Докажите. что существует вычислимая функция $f$, определённая на тех и только тех $x$, для которых найдётся $y$, при котором $\langle x,y\rangle \in F$, причём значение $f(x)$ является одним из таких $y$
  144. Даны два перечислимых множества $X$ и $Y$. Докажите, что найдутся два непересекающихся перечислимых множества $X'$ и $Y'$, таких что $X' \subset X$, $Y' \subset Y$, $X' \cup Y' = X \cup Y$.
  145. Докажите, что если перечислимое множество перечислимо в возрастающем порядке, то оно является разрешимым.
  146. Докажите, что любое бесконечное перечислимое множество содержит бесконечное разрешимое подмножество.
  147. Покажите, что для всякой вычислимой функции $f$ существует вычислимая функция, являющаяся «псевдообратной» к $f$ в следующем смысле: область определения $g$ совпадает с областью значений $f$, и при этом $f(g(f(x))) = f(x)$ для всех $x$, при которых $f(x)$ определено.
  148. Докажите, что если $A$ неперечислимо и $A \le_m B$, то $B$ неперечислимо.
  149. Пусть $A$ перечислимо и $\mathbb{N} \setminus A \le_m A$. Что можно сказать про $A$?
  150. Пусть $A$ перечислимо и $A \le_m \mathbb{N} \setminus A$. Что можно сказать про $A$?
  151. Пусть дана функция $f : A \to \mathbb{N}$. Ее продолжением на множество $B \supset A$ называется функция $g:B \to \mathbb{N}$, что если $x\in A$, то $g(x) = f(x)$. Докажите, что существует вычислимая функция $f$, у которой не существует всюду определенного вычислимого продолжения.
  152. Два перечислимых множества $A$ и $B$, где $A \cap B = \varnothing$ называются неотделимыми, если не сущестует разрешимых множеств $X$ и $Y$, таких что $A \subset X$, $B \subset Y$, $X \cap Y = \varnothing$. Покажите, что существуют неотделимые множества. Указание: рассмотрите множества пар $\langle p, x\rangle$, где $p$ - программа, возвращающая целое число, для некоторого условия.
  153. Обобщите определение неотделимых множеств на счетное семейство множеств. Докажите, что существует счетное семейство неотделимых множеств.
  154. Докажите, что множество программ, допускающих заданное конечное множество слов $x_1, \ldots, x_n$, перечислимо, но не разрешимо.
  155. Докажите, что множество программ, допускающих бесконечное множество слов не разрешимо.
  156. Докажите, что множество программ, зависающих на любом входе, не разрешимо.
  157. Докажите, что множество программ, останавливающихся на своём собственном исходном коде, перечислимо, но не разрешимо.
  158. Покажите, что следующие три свойства множества $X$ равносильны: (1) $X$ можно представить в виде $A \setminus B,$ где $A$ — перечислимое множество, а $B$ — его перечислимое подмножество; (2) $X$ можно представить в виде $A \setminus B$, где $A$ и $B$ — перечислимые множества; (3) $X$ можно представить в виде симметрической разности двух перечислимых множеств.
  159. Покажите, что множество $X$ можно представить в виде $A\setminus (B \setminus C)$, где $A \supset B \supset C$ — перечислимые множества, если и только если его можно представить в виде симметрической разности трёх перечислимых множеств.
  160. Покажите, что существует множество, которое можно представить в виде симметрической разности трёх перечислимых множеств, но нельзя представить в виде симметрической разности двух перечислимых множеств
  161. Язык ограниченной задачи останова (bounded halting) $BH = \{ (p, t) | p$ завершается на пустом входе за $t$ шагов $\}$. Докажите, что $BH$ разрешим.
  162. Докажите, что существует разрешимое множество пар, проекция которого на одну из осей не является разрешимой.
  163. Докажите, что существует разрешимое множество пар, проекция которого на каждую из осей не является разрешимой.
  164. Некоторое множество $S$ натуральных чисел разрешимо. Разложим все числа из $S$ на простые множители и составим множество $D$ всех простых чисел, встречающихся в этих разложениях. Можно ли утверждать, что множество $D$ перечислимо?
  165. Некоторое множество $S$ натуральных чисел разрешимо. Разложим все числа из $S$ на простые множители и составим множество $D$ всех простых чисел, встречающихся в этих разложениях. Можно ли утверждать, что множество $D$ разрешимо?
  166. Множество $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)\}$ является разрешимым?
  167. В предыдущем задании можно ли утверждать, что $B$ перечислимо, если $A$ перечислимо?
  168. Используя теорему о рекурсии, докажите, что язык программ, которые останавливаются на пустом вводе, является неразрешимым. Является ли этот язык перечислимым?
  169. Используя теорему о рекурсии, докажите, что язык программ, которые не останавливаются на пустом вводе, является неразрешимым. Является ли этот язык перечислимым?
  170. Используя теорему о рекурсии, докажите, что язык программ, которые допускают бесконечное число слов, является неразрешимым.
  171. Используя теорему о рекурсии, докажите, что язык программ, которые допускают свой собственный исходный код, является неразрешимым.
  172. Докажите, что существуют две различные программы $p$ и $q$, такие что программа $p$ печатает текст программы $q$, а программа $q$ печатает текст программы $p$.
  173. Докажите, что существует бесконечная последовательность различных программ $p_i$, такая что $p_1$ печатает пустую строку, а $p_i$ печатает текст программы $p_{i-1}$.
  174. Докажите, что существует бесконечная последовательность различных программ $p_i$, такая что $p_i$ печатает текст программы $p_{i+1}$.
  175. Докажите, что для любого конечного $n$ существует последовательность программ $p_1, p_2, \ldots, p_n$, что $p_i$ печатает текст $p_{i+1}$, а $p_n$ печатает текст $p_1$.
  176. Докажите, что язык программ, для которых не существует более короткой программы, которая на любом входе ведёт себя так же, является неразрешимым.
  177. Докажите, что язык программ, для которых не существует программы такой же длины, которая на любом входе ведёт себя так же, является либо конечным, либо неразрешимым.
  178. Busy Beaver. Функция $BB(n)$ возвращает длину максимальной строки, которую программа длины $n$ может вывести на пустом входе и завершиться. Докажите, что $BB$ является невычислимой.
  179. Докажите, что для любой всюду определенной вычислимой функции $f$ найдется значение $n$, для которого $BB(n) > f(n)$.
  180. Докажите, что для любой всюду определенной вычислимой функции $f$ найдется бесконечно много значений $n$, для которых $BB(n) > f(n)$.
  181. Колмогоровская сложность. $K(s)$ это длина минимальной программы, которая на пустом входе выводит строку $s$ и завершается. Докажите, что $K$ является невычислимой.
  182. Пусть для любой строки $s$ выполнено $K(s) \ge f(s)$, где $f$ — всюду определенная вычислимая функция. Докажите, что найдется константа $C$, такая что $f(s) \le C$ для любой $s$.
  183. Специальное задание: выберите нетривиальный язык программирования и напишите на нём программу, которая выводит свой собственный код. Не используйте код из интернета, напишите сами. Языки программирования всех студентов в рамках одной группы должны быть различны.
  184. Специальное задание: выберите нетривиальный язык программирования и напишите на нём программы, которые демонстрируют решение одного из заданий 172-175. В рамках одной группы пара (язык программирования - номер задания) должна быть уникальной. Выберите язык программирования, отличный от предыдущего задания.