5.1 Композиция экспоненциальных производящих функций

5.1 Композиция экспоненциальных производящих функций

модуль 5.1 шаг 5

Записать экспоненциальную производящую функцию \(H(z)\), описывающую количество способов разбить \(n\)-элементное множество на блоки размерами, большими или равными двух.

Решение

Darya Rodionova

Действительно, из предыдущего шага мы выяснили, чтобы разбить множество из \(n\) элементов на подмножества с числом элементов \(k \geqslant 1\), нам достаточно исключить первый член экспоненциального ряда, равный единице. А в этой задаче - исключаем ещё и второй член ряда. :)

Ответ

e^(e^z-1-z)

модуль 5.1 шаг 6

В комнате находятся \(n\) детей. Эти дети разбиваются на группы. В каждой группе одного ребенка ставят в центр круга, а вокруг него из оставшихся в группе детей образуют хоровод. При этом хоровод может состоять как из нескольких детей, так и из одного ребенка, соединившего руки. Записать экспоненциальную производящую функцию \(H(z)\), описывающую количество способов совершить эти действия.

Решение

Fulmenius

Воспользуемся законами суммы и композиции экспоненциальных производящих функций. Каким операциям над множествами соответствует наш выбор детей для хороводов? Сначала у нас есть структура множества из \(n\) элементов. Её производящая функция - \(F(z)=e^z\). Мы разбиваем это множество на подмножества, на каждом из которых задаём структуру множества из не менее чем двух элементов. Структура множества из не менее чем двух элементов задаётся ЭПФ \(H(z)=e^z−1−z\), а задание этой структуры на всевозможных блоках структуры \(F(z)\) соответствует композиции \(F(H(z))= e^{e^z-1-z}\)(сначала задаём структуру блоков \(F(z)\), потом на каждом блоке задаём структуру \(H(z)\). Наконец, на каждом из блоков структуры \(H(z)\) нам нужно задать структуру хоровода. Число хороводов на \(n\) - элементном множестве - \(\frac{n!}{n}=(n-1)!\). Соответствующая ЭПФ - это ряд для \(\ln(1-z)\). Подставляя

получаем искомый результат

Ответ

exp(1-2*z)

модуль 5.1 шаг 8

В колоде лежит \(n\) карт. Записать экспоненциальную производящую функцию \(H(z)\), позволяющую подсчитать количество способов разбить эти карты на группы чётного размера, в каждой группе образовать из карт упорядоченную стопку, а затем разложить полученные стопки в ряд.

Решение

Николай Доронин

Введем экспоненциальную производящую функцию для группы с учетом условия, что группа может быть четного размера \(F(z)=2!\frac{z^2}{2!}+4!\frac{z^4}{4!}+6!\frac{z^6}{6!}+...+(2n)!\frac{z^{2n}}{(2n)!}+...=z^2+z^4+z^6+...+z^{2n}+...=\frac{z^2}{1-z^2}\). Здесь коэффициент \(a_n\) показывает сколькими способами группу карт можно упорядочить в стопку.

Введем экспоненциальную производящую функцию для раскладки полученных стопок в ряд \(G(z)=1+1!\frac{z^1}{1!}+2!\frac{z^2}{2!}+3!\frac{z^3}{3!}+...+n!\frac{z^n}{n!}+...=1+z^1+z^2+z^3+...+z^n+...=\frac{1}{1-z}.\) Здесь коэффициент \(b_n\) показывает сколькими способами стопки можно упорядочить в ряд.

Тогда \(H(z)=\frac{1}{1-\frac{z^2}{1-z^2}}=\frac{1-z^2}{1-2z^2}\).

Ответ

1/(1-z^2/(1-z^2))

модуль 5.1 шаг 9

Найти количество способов разбить \(n\) людей на некоторое (заранее не фиксированное) количество линейно упорядоченных множеств (цепочек), а затем циклически упорядочить эти цепочки.

Указание: получить экспоненциальную производящую функцию \(H(z)\), описывающую количество способов совершить данные комбинаторные действия, а затем разложить ее в ряд по \(z^n/n!\).

Решение

Николай Доронин

Введем экспоненциальную производящую функцию для упорядоченных множеств(цепочек) \(F(z)=1!\frac{z^1}{1!}+2!\frac{z^2}{2!}+3!\frac{z^3}{3!}+4!\frac{z^4}{4!}+...+n!\frac{z^n}{n!}+...=z^1+z^2+z^3+z^4+...+z^n+...=\frac{z}{1-z}\). Коэффициенты \(a_n\) показывают сколькими способами можно упорядочить людей в цепочке.

Введем экспоненциальную производящую функцию для циклического упорядочивания цепочек. Коэффициенты показывают сколькими способами можно циклически упорядочить цепочки \(G(z)=1+(1-1)!\frac{z^1}{1!}+(2-1)!\frac{z^2}{2!}+(3-1)!\frac{z^3}{3!}+...+(n-1)!\frac{z^n}{n!}+...=1+\frac{z^1}{1}+\frac{z^2}{2}+\frac{z^3}{3}+...+\frac{z^n}{n}+...=1-\ln(1-z)\) - последнее преобразование производится с помощью разложения в ряд Маклорена \(\ln(1-x)=-x-\frac{x^2}{2}-\frac{x^3}{3}-\frac{x^4}{4}-...-\frac{x^n}{n}\).

Тогда \(H(z)=1=\ln(1-\frac{z}{1-z})=1-\ln{\left( \frac{1-2z}{1-z} \right)}=1-(\ln(1-2z)-\ln(1-z))=1-\ln(1-2z)+\ln(1-z)\) и снова применяя разложение в ряд Маклорена получаем - \(H(z)=1+2z+\frac{(2z)^2}{2}+\frac{(2z)^3}{3}+\frac{(2z)^4}{4}+...+\frac{(2z)^n}{n}-z-\frac{z^2}{2}-\frac{z^3}{3}-\frac{z^4}{4}...+\frac{z^n}{n}=1+z+\frac{(2^2-1)z^2}{2}+\frac{(2^3-1)z^3}{3}+\frac{(2^4-1)z^4}{4}+...+\frac{(2^n-1)z^n}{n}\)

откуда получаем \(c_n\frac{z^n}{n!}=\frac{(2^n-1)z^n}{n}=(2^n-1)(n-1)!\frac{z^n}{n!}\)

Ответ

(n-1)!*(2^n-1)

модуль 5.1 шаг 11

Подсчитать количество помеченных эйлеровых графов (то есть связных графов, у которых степень любой вершины есть четное число), построенных на \(n=7\) вершинах.

Указания:

1. Записать количество \(c_n\) графов (не обязательно связных), степень любой вершины которых является четным числом.
2. Записать для полученного количества таких графов экспоненциальную производящую функцию \(H(z)\).
3. Использовать экспоненциальную формулу, а также вытекающее из нее рекуррентное соотношение, связывающее коэффициенты \(a_n\) и \(c_n\) экспоненциальных производящих функций \(F(z)\) и \(H(z)\) соответственно, для подсчета количества \(a_n\) эйлеровых графов.

Решение

Пишите в комментариях

Ответ

26614

модуль 5.1 шаг 16

Из комбинаторных соображений определить вид полинома Белла \(B_{4,2}(a_1,a_2,a_3)\). Иными словами, записать явный вид полинома \(B_{4,2}\) как функции от трех переменных \(a_1\), \(a_2\), \(a_3\).

Пример вывода аналогичного полинома \(B_{4,3}(a_1,a_2)\) в Степик:

6*a_1^2*a_2

Пример комбинаторной интерпретации результата: разбить четырехэлементное множество на три блока можно шестью различными способами:

Каждое из этих разбиений имеет ровно два блока мощности один (отсюда \(a_1^2\)) и ровно один блок мощности \(2\) (отсюда сомножитель \(a_2\)). Как следствие,

Ответ

4*a_1*a_3+3*a_2^2