244
правки
Изменения
Нет описания правки
# Постройте производящую функцию для разбиений на не больше, чем $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)$.
