Изменения
Нет описания правки
# Последовательность задана рекуррентным соотношением $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(st) = \frac {P(st)}{Q(st)}$, где единственный минимальный по модулю корень $Q(st)$ равен $1 / \beta$ и имеет кратность $k$. Тогда $a_n \approx C \beta^k n n^{k-1}$. Покажите, что $C = k \frac {(-\beta)^n 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}$.
# Найдите произведение Адамара $\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)$ определено.
