5
правок
Изменения
Операции над производящими функциями и пара примеров
<tex>=\dfrac{1}{1-x}\dfrac{1}{1-x^3}\dfrac{1}{1-x^5}\ldots=\prod\limits_{n=1}^\infty(1+x^{ 2n - 1})^{-1}</tex>
== Операции над производящими функциями ==
=== Умножение на скаляр ===
Умножение производящей функции на скаляр <tex>k</tex> увеличивает каждый производимый ей элемент в <tex>k</tex> раз:
<tex>\langle1, 0, 1, 0, 1, 0,...\rangle \xleftrightarrow{} 1 + x^2 + x ^4 + x^6 + ... = \frac{1}{1-x^2}</tex>
Умножение производящей функции на <tex>2</tex> даёт
<tex>\frac{2}{1 - x^2} = 2 + 2x^2 + 2x^4 + 2x^6 + ...</tex>
что производит следующую последовательность:
<tex>\langle2,0,2,0,2,0,...\rangle</tex>
Если <tex>\langle f_0,f_1,f_2,...\rangle \xleftrightarrow{} F(x), \text{тогда} \langle cf_0,cf_1,cf_2,...\rangle \xleftrightarrow{} c \cdot F(x)</tex>
=== Сложение производящих функций ===
Сложение производящих функций <tex>A \text{ и } B</tex> соответствует производящей функции <tex>C</tex>, такой что <tex>c_n = a_n + b_n</tex>
<tex>\langle f_0,f_1,f_2,... \xleftrightarrow{} F(x)</tex>
<tex>+ \langle g_0,g_1,g_2,... \rangle \xleftrightarrow{} G(x)</tex>
<tex>= \langle f_0+g_0,f_1+g_1,f_2+g_2,... \rangle \xleftrightarrow{} F(x) + G(x)</tex>
=== Сдвиг вправо ===
Пусть у нас есть производящая функция <tex>\langle 1,1,1,1,... \rangle \xleftrightarrow{} \frac{1}{1-x}</tex>
Мы можем сдвинуть её вправо, добавив <tex>k</tex> ведущих нулей:
<tex>\langle 0,0,...,0,1,1,1,... \rangle \xleftrightarrow{} x^k + x^{k+1} + x^{k+2} + x^{k+3} + ... = x^k \cdot (1 + x + x^2 + x^3 + ...) = \frac{x^k}{1-x}</tex>
То есть чтобы сдвинуть производящую функцию на <tex>k</tex> элементов в право, нужно умножить её на <tex>x^k</tex>
=== Дифференцирование производящей функции ===
Дифференцирование проиводящей функции сдвигае её элементы влево на одни элемент и умножает каждый элемент на его индекс:
<tex>\frac{d}{dx}(1 + x + x^2 + x^3+x^4 + ...) = \frac{d}{dx}\big(\frac{1}{1-x}\big)</tex>
<tex>\frac{d}{dx} + x\frac{d}{dx} + x^2 \frac{d}{dx} + x^3 \frac{d}{dx} + x^4 \frac{d}{dx} + ... = \frac{d}{dx}\big(\frac{1}{1-x}\big)</tex>
<tex>1 + 2x + 3x^2 + 4x^3 + ... = \frac{1}{(1-x)^2}</tex>
<tex>\langle 1,2,3,4,... \rangle \xleftrightarrow{} \frac{1}{(1-x)^2}</tex>
{{Задача
| about =
| definition = Найти производящую функцию для последовательности квадратов <tex>\langle 0,1,4,9,16,... \rangle</tex>
}}
Мы можем взять последовательность <tex>\langle 1,1,1,1,...\rangle</tex>,
давайте два раза продиффиренцируем производящую функцию для этой последовательности, чтобы получить желаемый результат. Проблема в том, что дифференцирование производит сдвиг в лeво, и в результате мы получим:
<tex>\frac{d}{dx}\frac{d}{dx}\langle 1,1,1,1,...\rangle = \langle4,9,16,...\rangle</tex>
Чтобы избежать потери первых двух элементов последовательности, мы можем применять сдвиг вправо после каждого дифференцирования:
<tex>\langle 1,1,1,1,...\rangle \xleftrightarrow{} \frac{1}{1-x}</tex>
<tex>\langle 1,2,3,4,...\rangle \xleftrightarrow{} \frac{d}{dx}\frac{1}{1-x} = \frac{1}{(1-x)^2} </tex>
<tex>\langle 0,1,2,3,...\rangle \xleftrightarrow{} x \cdot \frac{1}{(1-x)^2} = \frac{x}{(1-x)^2}</tex>
<tex>\langle 1,4,9,16,...\rangle \xleftrightarrow{} \frac{d}{dx}\frac{x}{(1-x)^2} = \frac{1+x}{(1-x)^3} </tex>
<tex>\langle 0,1,4,9,...\rangle \xleftrightarrow{} x \cdot \frac{1+x}{(1-x)^3} = \frac{x(1+x)}{(1-x)^3}</tex>
=== Произведение производящих функций ===
{{Утверждение
|statement = Пусть <tex>A \text{ и } B</tex> - классы
объектов, и <tex>A(x) \text{ и } B(x)</tex> - их производящие функции. Тогда классу <tex>C = A \times B \text{ соответствует производящая функция } C(x) = A(x)B(x).</tex>
|proof = Пусть <tex>c_n</tex> - число объектов размера <tex>n</tex> в декартовом произведении <tex>C = A \times B </tex>. Эти объекты полученны выбором объекта <tex>a \in A \text{ размера } k \leq n \text{ и объекта } b \in B \text{ размера } n-k</tex>.
Таким образом
<tex>c_n = \displaystyle\sum_{k = 0}^{n} a_k b_{n-k}.</tex>
Рассмотрим произведение производящих функций
<tex>A(x)B(x) = \Bigg(\displaystyle\sum_{k \geq 0}^{} a_k x^k\Bigg) \times \Bigg(\displaystyle\sum_{k \geq 0}^{} b_k x^k \Bigg).</tex>
<tex>A(x)B(x) = \displaystyle\sum_{n \geq 0}^{} \Bigg(\displaystyle\sum_{k \geq 0}^{n} a_k b_{n-k}\Bigg)x^n</tex>
}}
{{Задача
| about =
| definition = Дана шестигранная игральная кость, грани которой пронумерованный от <tex>1 \text{ до } 6</tex> и восьмигранная игральная кость, грани которой пронумерованны от <tex>1 \text{ до } 8</tex>. Мы кидаем кости и получаем сумму чисел, которые выпали на костях. Нужно найти число способов получить каждую сумму.
}}
Представим производящую функцию <tex>C(x) = \displaystyle_{n \geq 0}^{} c_n x^n</tex> как:
<tex>C(x) = (x+ x^2 + x^3 + x^4 + x^5 + x^6) \times (x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8)</tex>
первая часть учитывает все возможные исходы первой кости, а вторая часть учитывает исходы второй кости. Например, сумму <tex>5</tex> можно разбить на <tex>2</tex> с первой кости и <tex>3</tex> со второй. Такой исход учитывается умножением <tex>x^2</tex> из первой последовательности на <tex>x^3</tex> из второй.
<tex>C(x) = x^2 + 2x^3 + 3x^4 + 4x^5 + 5x^6 + 6x^7 + 6x^8 + 6x^9 + 5x^{10} + 4x^{11} + 3x^{12} + 2x^{13} + x^{14}</tex>
== Примеры решений задач методом производящих функций ==
* [[Нахождение количества разбиений числа на слагаемые|Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]
* Graham, Knuth, and Patashnik: Concrete Mathematics
* [https://math.mit.edu/~goemans/18310S15/generating-function-notes.pdf generation-function-notes]
* [http://www.math.cmu.edu/~lohp/docs/math/2011-228/mit-ocw-generating-func.pdf mit-ocw-generating-func]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
[[Категория: Подсчёт числа объектов]]
