278
правок
Изменения
Нет описания правки
# Постройте производящую функцию для разбиений на не больше, чем $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$, а в предыдущем пункте нет?
# Обобщите два предыдущих задания. Как выглядят экспоненциальные производящие функции для разбиений на (не)четное число подмножеств, каждое из которых содержит (не)четное число элементов? (Необходимо дать четыре ответа для всех комбинаций)
# Найдите экспоненциальную производящую функцию числа строк из 0 и 1, в которых четное число единиц.
# Найдите экспоненциальную производящую функцию числа строк из букв a..z, в которых каждая гласная буква (aeiou) встречается нечетное число раз.
# Из вида ЭПФ, найдите явную формулу числа строк из предыдущего задания.
# Постройте экспоненциальную производящую функцию для перестановок, состоящих из четных циклов
# Постройте экспоненциальную производящую функцию для перестановок, состоящих из нечетных циклов.
# Докажите, что для четного $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$ через производящую функцию $A(z, u)$.
# Напишите ЭПФ от двух переменных для числа функций из $n$-элементного множества в $m$-элементное.
# Напишите ЭПФ от двух переменных для числа инъекций из $n$-элементного множества в $m$-элементное.
# Напишите ЭПФ от двух переменных для числа сюрьекций из $n$-элементного множества в $m$-элементное.
# Найдите среднюю степень корня в случайном дереве Кэли из $n$ вершин.
# Возрастающе-убывающей перестановкой называется перестановка, которая поочередно возрастает и убывает: $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^k$, где $d$ пробегает все делители $n$ . Найдите ПФД для $\sigma_1(n)$
# Найдите ПФД для $\sigma_k(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$.
# Функция Мангольдта $\Lambda_n$ равна $\ln p$, если $n = p^k$ для некоторого $k \ge 1$, и 0 иначе. Найдите ПФД для последовательности $\Lambda_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$ для некоторого $k > 1$. Выведите формулу для количества апериодичных строк для произвольного $n$. Указание: используйте формулу обращения Мебиуса.
# Найдите ПФД для последовательности $a_n = $ количество упорядоченных разбиений числа $n$ на (не обязательно простые) $k$ множителей, множитель 1 разрешен.
# Найдите ПФД для последовательности $a_n = $ количество упорядоченных разбиений числа $n$ на $\ge 0$ (не обязательно простых) множителей, множитель 1 запрещен.
# Найдите ПФД для последовательности $a_n = 2^{\omega(n)}$, где $\omega(n)$ - количество различных простых делителей $n$.
# Найдите ПФД для последовательности $a_n = 3^{\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)$ определено.
# Покажите, что следующие три свойства множества $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$ — перечислимые множества, если и только если его можно представить в виде симметрической разности трёх перечислимых множеств.
# Покажите, что существует множество, которое можно представить в виде симметрической разности трёх перечислимых множеств, но нельзя представить в виде симметрической разности двух перечислимых множеств
