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

2018-03-31T21:08:54Z

212.1.243.206:

# Формальный степенной ряд $\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$.
# Формальный степенной ряд $(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}$.
# Формальный степенной ряд $\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}$.
# Пусть $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)$.
# Будем называть нулем степенной ряд $0(s) = 0 + 0s + 0s^2 + \ldots$. Докажите, что $A(s) \ne 0(s)$, $B(s) \ne 0(s)$, то $A(s)B(s) \ne 0(s)$.
# Докажите, что $(A(s)B(s))' = A'(s)B(s) + A(s)B'(s)$.
# Докажите, что $\int(A'(s)B(s) + A(s)B'(s)) = A(s)B(s) - A(0)B(0)$.
# Найдите производящую функцию для последовательности $0 \cdot 1, 1 \cdot 2, 2 \cdot 3, 3 \cdot 4, \ldots, (n - 1) \cdot n, \ldots$.
# Найдите производящую функцию для последовательности $1^2, 2^2, 3^2, \ldots, n^2, \ldots$.
# Последовательность $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}$
# Последовательность $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$
# Последовательность $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$
# Последовательность $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$
# Последовательность $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$
# Пользуясь производящей функцией для чисел Фибоначчи, докажите утверждение, что $f_0+f_1+\ldots+f_n=f_{n+2}-1$.
# Пользуясь производящей функцией для чисел Фибоначчи, докажите утверждение, что $f_0+f_2+\ldots+f_{2n}=f_{2n+1}$.
# Найдите производящую функцию для замощений прямоугольника $2\times n$ доминошками и единичными клетками.
# Найдите производящую функцию для замощений прямоугольника $2\times n$ уголками (квадратами $2\times 2$ с вырезанной одной клеткой) и единичными клетками.
# Пользуясь производящей функцией для чисел Фибоначчи, докажите утверждение, что $f_1+f_3+\ldots+f_{2n-1}=f_{2n}-1$.
# Пользуясь производящей функцией для чисел Фибоначчи, докажите утверждение, что $f_0^2+f_1^2+f_2^2+\ldots+f_n^2=f_nf_{n+1}$.
# Найдите производящую функцию для чисел "трибоначчи" $f_0=f_1=f_2=1$, $f_n = f_{n-1}+f_{n-2}+f_{n-3}$.
# Найдите производящую функцию для последовательности, заданной рекуррентностью $f_0=f_1=f_2=1$, $f_n = f_{n-1}-2f_{n-3}$.
# Производящая функция называется рациональной, если она представима в виде отношения двух многочленов. Для производящих функций каждой из следующих последовательностей выясните, является ли она рациональной, если да, приведите ее представление в таком виде. Последовательность $1, -2, 3, -4, 5, \ldots$.
# Последовательность $2, -6, 12, \ldots, (-1)^k(k+1)(k+2),\ldots$
# Последовательность $0, 1, 4, 9, 16, 25, \ldots, k^2,\ldots$
# Последовательность $0, 1, 8, 27, 64, 125, \ldots, k^3,\ldots$
# Последовательность $0, 1, 2^s, 3^s, 4^s, 5^s, \ldots, k^s,\ldots$
# Последовательность $1, -4, 9, -16, \ldots, (-1)^k(k+1)^2,\ldots$
# Последовательность $1, 1, 4, 9, 25, \ldots, F_k^2,\ldots$
# Найдите производящую функцию для чисел Каталана.
# Путь Моцкина - путь, начинающийся в точке $(0, 0)$, составленный из векторов $(1, 1)$, $(1, 0)$, $(1, -1)$, не опускающийся ниже оси $OX$ и заканчивающийся в точке $(n, 0)$. Напишите рекуррентное соотношение для числа путей Моцкина, найдите производящую функцию для числа таких путей.
# Рассмотрим множество путей на прямой, начинающихся в 0, состоящих из шагов длины 1 вправо или влево. Будем называть такой путь блужданием. Найдите рекуррентную формулу и производящую функцию для числа блужданий из $n$ шагов, оканчивающихся в 0.
# Найдите рекуррентную формулу и производящую функцию для числа блужданий из $n$ шагов, оканчивающихся в 0 и не заходящих в отрицательную полупрямую.
# Найдите рекуррентную формулу и производящую функцию для числа блужданий из $n$ шагов, оканчивающихся в фиксированной точке $N > 0$.
# Найдите рекуррентную формулу и производящую функцию для числа блужданий из $n$ шагов, оканчивающихся в фиксированной точке $N > 0$ и не заходящих в отрицательную полупрямую.
# Найдите производящую функцию для последовательности, заданной рекуррентным соотношением $a_0 = 2$, $a_n = a_{n-1}^2$.
# Найдите производящую функцию для последовательности, заданной рекуррентным соотношением $a_0 = 2$, $a_n = a_{n-1}^3$.
# Найдите производящую функцию для последовательности, заданной рекуррентным соотношением $a_0=a_1= 2$, $a_n = a_{n-1}\cdot a_{n - 2}$.
# Последовательность задана рекуррентным соотношением $a_0=a_1=1$, $a_n = 5a_{n-1}-6a_{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 = 4a_{n-1}-4a_{n-2}$. Оцените асимптотическое поведение $a_n$ при $n\to+\infty$.
# Петя заинтересовался, что будет, если последовательность, заданная линейным рекуррентным соотношением, имеет производящую фукнцию, в знаменателе которой стоит $Q(t)=(1-ct)(1+ct)$, ведь тогда асимптотическое поведение членов на четных и нечетных позициях разное. Разберитесь.
# Последовательность задана рекуррентным соотношением $a_0=a_1=1$, $a_n = 2a_{n-1}-2a_{n-2}$. Оцените асимптотическое поведение $a_n$ при $n\to+\infty$.
# Докажите, что если последовательность $a_n$ допускает представление в виде $a_n = \sum_i p_i(n)q_i^n$, где $p_i(n)$ - полиномы, и все $q_i$ различны, то такое представление единственно с точностью до порядка слагаемых.
# Используя результат из предыдушего задания, докажите, что формальный степенной ряд $\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$ не представим в виде отношения двух полиномов.
# Произведением Адамара двух производящих функций $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-x}$ и $\frac{1}{1-2x}$.
# Найдите произведение Адамара $\frac{1}{1-2x}$ и $\frac{1}{1-3x}$.
# Найдите произведение Адамара $\frac{1}{1+3x-x^2}$ и $\frac{1}{1-2x}$.
# Найдите произведение Адамара $\frac{1}{1-2x-x^2}$ и $\frac{1}{1-2x}$.
# Пусть $A$ - семейство комбинаторных объектов. Пусть $M = MSet(A)$, а $P = Set(A)$. Докажите, что $M(t) = P(t)M(t^2)$.
# Пусть $A$ - семейство комбинаторных объектов с производящей функцией $A(t)$. Обозначим как $Seq^k(A)$ множество последовательностей длины $k$, каждый элемент которого является последовательностью из $k$ объектов. Найдите производящую функцию для $Seq^k(A)$.
# Пусть $A$ - семейство комбинаторных объектов с производящей функцией $A(t)$. Обозначим как $Seq^{\le k}(A)$ множество последовательностей длины $k$, каждый элемент которого является последовательностью из не более чем $k$ объектов. Найдите производящую функцию для $Seq^{\le k}(A)$.
# Пусть $A$ - семейство комбинаторных объектов с производящей функцией $A(t)$. Обозначим как $Seq^{\ge k}(A)$ множество последовательностей длины $k$, каждый элемент которого является последовательностью из не менее чем $k$ объектов. Найдите производящую функцию для $Seq^{\ge k}(A)$.
# Пусть $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$.
# Обозначим как $P^T$ множество разбиений на слагаемые, где порядок слагаемых не важен, а слагаемые выбраны из множества $T$. Осознайте, что $P^T = MSet(Seq_T(Z))$. Найдите производяющую функцию для $P^T$.
# Индекс Хирша. Докажите, что $\prod\limits_{n=1}^\infty\frac{1}{1-z^n}=\sum\limits_{n\ge 0}\frac{z^{n^2}}{((1-z)\cdots(1-z^n))^2}$.
# Докажите, что $\frac{1}{1-z}=\prod\limits_{j=0}^\infty(1+z^{2^j})$.
# Найдите производящую функцию для слов над $m$-буквенным алфавитом (вес каждой буквы равен 1, слова равен его длине).
# Обозначим как $W$ множество слов над алфавитом $\{a, b\}$. Осознайте, что $W=Seq\{a\}\times Seq(\{b\}\times Seq\{a\})$. Проверьте равенство для производящих функций.
# Обозначим как $W^{(k)}$ множество слов над алфавитом $\{a, b\}$, не содержащих $k$ букв $a$ подряд. Запишите $W^{(k)}$ через $Seq_T$ и $\times$. Найдите производящую функцию для $W^{(k)}$.
# Обобщите задание 60 на произвольный алфавит.
# Обобщите задание 61 на произвольный алфавит.
# Неявное задание КО. Пусть $A$, $B$ и $X$ - семейства комбинаторных объектов, причем $B \cap X = \varnothing$, $A = B \cup X$. Пусть производящие функции для $A$ и $B$ - $A(t)$ и $B(t)$, соответственно. Найдите производящую функцию $X(t)$.
# Неявное задание КО 2. Пусть $A$, $B$ и $X$ - семейства комбинаторных объектов, причем $A = B \times X$. Пусть производящие функции для $A$ и $B$ - $A(t)$ и $B(t)$, соответственно. Найдите производящую функцию $X(t)$.
# Неявное задание КО 3. Пусть $A$ и $X$ - семейства комбинаторных объектов, причем $A = Seq(X)$. Пусть производящая функция для $A$ - $A(t)$. Найдите производящую функцию $X(t)$.
# Неявное задание КО 4. Пусть $A$ и $X$ - семейства комбинаторных объектов, причем $A = MSet(X)$. Пусть производящая функция для $A$ - $A(t)$. Найдите производящую функцию $X(t)$.
# Экспоненциальная производящая функция для целочисленной последовательности называется функцией Гурвица. Докажите, что сумма, произведение, интеграл и производная функции Гурвица является функцией Гурвица.
# Докажите, что результат подстановки функции Гурвица в функцию Гурвица является функцией Гурвица
# Опишите класс помеченных объектов $seq(cyc(Z))$. Найдите его экспоненциальную производящую функцию.
# Будем обозначать $seq_T$, $cyc_T$, $set_T$ соответственно последовательности, циклы и множества, размер которых принадлежит множеству $T$. Опишите класс помеченных объектов $set(cyc_{\ge 1}(Z))$. Найдите его экспоненциальную производящую функцию.
# Опишите класс помеченных объектов $set(cyc_{1, 2}(Z))$. Найдите его экспоненциальную производящую функцию.
# Сюрьекции на $r$-элементное множество. Осознайте, что $seq_{=r}(set_{\ge 1}(Z))$ задаёт сюрьекции на $r$-элементное множество. Найдите экспоненциальную производящую функцию.
# Разбиения на $r$ множеств. Осознайте, что $set_{=r}(set_{\ge 1}(Z))$ задаёт разбиения на $r$-элементное множество. Найдите экспоненциальную производящую функцию. Что стоит при $z^n$?
# Гиперболический синус $\mathrm{sh}\,z$ равен $\frac{1}{2}(e^{z}-e^{-z})$. Гиперболический косинус $\mathrm{ch}\,z$ равен $\frac{1}{2}(e^{z}+e^{-z})$. Рассмотрим разбиения $n$-элементного множества на непустые подмножества. Для произвольных подмножеств экспоненциальная производящая функция равна $e^{e^z-1}$. Докажите, что для разбиений на нечетное число подмножеств экспоненциальная производящая функция равна $\mathrm{sh}(e^z-1)$.
# Докажите, что для разбиений на четное число подмножеств экспоненциальная производящая функция равна $\mathrm{ch}(e^z-1)$.
# Докажите, что для разбиений на произвольное число подмножеств, каждое из которых содержит нечетное число элементов, экспоненциальная производящая функция равна $e^{\mathrm{sh}\,z}$.
# Докажите, что для разбиений на произвольное число подмножеств, каждое из которых содержит четное число элементов, экспоненциальная производящая функция равна $e^{\mathrm{ch}\,z-1}$. Почему здесь в показателе степени есть $-1$, а в предыдущем задании нет?
# Обобщите четыре предыдущих задания. Как выглядят экспоненциальные производящие функции для разбиений на (не)четное число подмножеств, каждое из которых содержит (не)четное число элементов? (Необходимо дать четыре ответа для всех комбинаций)
# Докажите, что объединение перечислимых языков перичислимо.
# Докажите, что пересечение перечислимых языков перичислимо.
# Докажите, что конкатенация перечислимых языков перичислима.
# Докажите, что замыкание Клини перечислимого языка перичислимо.
# Докажите, что декартово произведение перечислимых языков перичислимо.
# Докажите, что проекция перечислимого языка пар на каждую из осей перечислима.
# Пусть $A \subset \Sigma^*$. Функция $f:A \to \Sigma^*$ называется вычислимой, если существует программа, которая по входу $x \in A$ выдает $f(x)$, а на входах не из $A$ зависает. Приведите пример невычислимой функции.
# Докажите, что функция вычислима тогда и только тогда, когда ее график перечислим.
# Докажите, что образ перечислимого множества под действием вычислимой функции перечислим.
# Докажите, что прообраз перечислимого множества под действием вычислимой функции перечислим.
# В этой и последующих задачах вместо разрешимых и перечислимых языков рассматриваются разрешимые и перечислимые множества натуральных чисел. Это на самом деле одно и то же, достаточно установить естественную биекцию между натуральными числами и словами в градуированном лексикографическом порядке. Теорема об униформизации. Пусть $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)$ определено.

Викиконспекты - Вклад участника [ru]

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