Производящие функции

Производящая функция

Производящей функцией последовательности ana_n называется функция

A(z)=a0+a1 z+a2 z2+⋯=∑n=0∞an znA(z) = a_0 + a_1 \, z + a_2 \, z^2 + \dotsb = \sum\limits_{n=0}^\oo a_n \, z^n

Производящая функция хранит всю информацию о последовательности. Более того, с помощью производящих функций можно находить конкретные формулы для элементов последовательности, анализировать асимптотику, раскладывать другие функции в ряд и так далее. Мы будем обращаться к ним бесчисленное количество раз.

По аналогии с многочленами, есть удобное обозначение коэффициентов. Пусть A(z)A(z) — производящая функция последовательности ana_n. Коэффициент при znz^n обозначается

[zn]A(z)   ⁣=def   ⁣an[z^n] A(z) \defeq a_n

Производящая функция является формальным рядом, так что мы можем использовать её в своих целях, не исследуя сходимость и конкретные значения zz. В таком случае, если последовательность обладает достаточной структурой и регулярностью, мы можем найти замкнутый вид её производящей функции. Например, производящая функция последовательности единиц

∑n=0∞zn=1+z+z2+⋯=SS=1+z(1+z+z2+⋯ )S=1+z SS=11−z\sum\limits_{n=0}^{\oo} z^n = 1 + z + z^2 + \dotsb = S \\ S = 1 + z(1 + z + z^2 + \dotsb) \\ S = 1 + z \, S \\ S = \frac{1}{1-z}

Свойства производящих функций

Здесь везде пусть A(z)A(z) — производящая функция последовательности ana_n и B(z)B(z) — производящая функция последовательности bnb_n.

Линейная комбинация производящих функций — производящая функция линейной комбинации последовательностей.

α A(z)+β B(z)=α ∑n=0∞an zn+β ∑n=0∞bn zn=∑n=0∞(α an+β bn) zn\alpha \, A(z) + \beta \, B(z) = \alpha \, \sum\limits_{n=0}^{\oo} a_n \, z^n + \beta \, \sum\limits_{n=0}^{\oo} b_n \, z^n = \sum\limits_{n=0}^{\oo} (\alpha \, a_n + \beta \, b_n) \, z^n

Откуда очевидно следует

[zn](α A(z)+β B(z))=α an+β bn[z^n] \bigl(\alpha \, A(z) + \beta \, B(z)\bigr) = \alpha \, a_n + \beta \, b_n

Сдвиг производящей функции на mm позиций вправо получается простым умножением на zmz^m

zm A(z)=∑n=0∞an zn+m=∑n=m∞an−m znz^m \, A(z) = \sum\limits_{n=0}^{\oo} a_n \, z^{n+m} = \sum\limits_{n=m}^{\oo} a_{n-m} \, z^n

Сдвиг влево на mm позиций происходит вычитанием первых mm членов и делением на zmz^m

A(z)−a0−a1 z−a2 z2−⋯−am−1 zm−1zm=∑n=0∞an+m zn=∑n=m∞an zn−m\frac{A(z) - a_0 - a_1 \, z - a_2 \, z^2 - \dotsm - a_{m-1} \, z^{m-1}}{z^m} = \sum\limits_{n=0}^{\oo} a_{n+m} \, z^{n} = \sum\limits_{n=m}^{\oo} a_n \, z^{n-m}

Умножение аргумента на константу даёт нам производящую функцию последовательности cn anc^n \, a_n

A(c z)=∑n=0∞cn an znA(c \, z) = \sum\limits_{n=0}^{\oo} c^n \, a_n \, z^n

Часто оказывается нужным добавить к коэффициентам множитель nn. Сделать это позволяет дифференцирование

A′(z)=∑n=0∞(n+1) an+1 znA'(z) = \sum\limits_{n=0}^{\oo} (n+1) \, a_{n+1} \, z^n

Обратная операция, интегрирование, дает способ поделить элементы последовательности на nn

∫0zA(t) dt=∑n=1∞1n an−1 zn\int\limits_0^z A(t) \, dt = \sum\limits_{n=1}^{\oo} \frac{1}{n} \, a_{n-1} \, z^n

Произведение производящих функций есть производящая функция свёртки последовательностей ana_n и bnb_n

A(z) B(z)=(a0+a1 z+a2 z2+⋯ ) (b0+b1 z+b2 z2+⋯ )==(a0 b0)+(a0 b1+a1 b0) z+(a0 b2+a1 b1+a2 b0) z2+⋯=∑n=0∞(∑k=0nak bn−k) znA(z) \, B(z) = (a_0 + a_1 \, z + a_2 \, z^2 + \dotsm) \, (b_0 + b_1 \, z + b_2 \, z^2 + \dotsm) = \\ = (a_0 \, b_0) + (a_0 \, b_1 + a_1 \, b_0) \, z + (a_0 \, b_2 + a_1 \, b_1 + a_2 \, b_0) \, z^2 + \dotsm = \sum\limits_{n=0}^{\oo} \left(\sum\limits_{k=0}^{\n} a_k \, b_{n-k}\right) \, z^n

Например, умножив производящую функцию последовательности ana_n на 1/(1−z)1/(1-z), получим производящую функцию последовательности частичных сумм исходной последовательности

11−z ∑n=0∞an zn=(1+z+z2+⋯ ) (a0+a1 z+a2 z2+⋯ )==a0+(a0+a1) z+(a0+a1+a2) z2+⋯=∑n=0∞(∑k=0nak)zn\frac{1}{1-z} \, \sum\limits_{n=0}^{\oo} a_n \, z^n = (1 + z + z^2 + \dotsm) \, (a_0 + a_1 \, z + a_2 \, z^2 + \dotsm) = \\ = a_0 + (a_0 + a_1) \, z + (a_0 + a_1 + a_2) \, z^2 + \dotsm = \sum\limits_{n=0}^{\oo} \left(\sum\limits_{k=0}^{n} a_k \right) z^n

Производящиме функции отлично раскрываются в совокупности с биномом Ньютона. Особый интерес для нас представляет случай отрицательного целого показателя. Используя определение биномиального коэффициента, можно получить формулу для сочетаний с повторениями

1(1−z)k=(1−z)−k=∑n=0∞(−kn) (−z)n=∑n=0∞(n+k−1k−1) zn\frac{1}{(1-z)^k} = (1-z)^{-k} = \sum\limits_{n=0}^{\oo} \binom{-k}{n} \, (-z)^n = \sum\limits_{n=0}^{\oo} \binom{n+k-1}{k-1} \, z^n

Частный случай при k=1k=1 даёт нам уже знакомую сумму бесконечной геометрической прогрессии

11−z=∑n=0∞zn=1+z+z2+z3+⋯\frac{1}{1-z} = \sum\limits_{n=0}^{\oo} z^n = 1 + z + z^2 + z^3 + \dotsb

Если возьмём интеграл, получим разложение натурального логарифма, оно же производящая функция последовательности 1/n1/n

∫0z11−t dt=ln⁡(11−t)∣0z=ln⁡(11−z)=∑n=1∞znn\int\limits_0^z \frac{1}{1-t} \, dt = \left. \ln \left( \frac{1}{1-t} \right) \right|_0^z = \ln \left( \frac{1}{1-z} \right) = \sum\limits_{n=1}^{\oo} \frac{z^n}{n}

Можем пойти в обратную сторону и продифференцировать

(∑n=0∞zn)′=∑n=1∞n zn−1=1(1−z)2\left( \sum\limits_{n=0}^{\oo} z^n \right)' = \sum\limits_{n=1}^{\oo} n \, z^{n-1} = \frac{1}{(1-z)^2}

Умножим на zz, получим производящую функцию натуральных чисел. Для удобства оставим начало суммирования в n=0n=0, так как сумма при этом не изменится

z ∑n=1∞n zn−1=∑n=0∞n zn=z(1−z)2z \, \sum\limits_{n=1}^{\oo} n \, z^{n-1} = \sum\limits_{n=0}^{\oo} n \, z^n = \frac{z}{(1-z)^2}

Проделаем то же самое ещё раз и получим производящую функцию последовательности n2n^2

z (∑n=0∞n zn)′=z ∑n=1∞n2 zn−1=∑n=1∞n2 zn=z (1+z)(1−z)3z \, \left( \sum\limits_{n=0}^{\oo} n \, z^n \right)' = z \, \sum\limits_{n=1}^{\oo} n^2 \, z^{n-1} = \sum\limits_{n=1}^{\oo} n^2 \, z^n = \frac{z \, (1+z)}{(1-z)^3}

Задача о домино

Рассмотрим одну интересную комбинаторную задачу. Сколькими способами можно замостить прямоугольник размером 2×n2 \times n костяшками домино размера 1×21 \times 2? Обозначим искомое количество способов как ana_n.

Для n=1n=1 способ только один (одна вертикальная доминошка), то есть a1=1a_1 = 1. Для n=2n=2 способа два (две вертикальные или две горизонтальные), a2=2a_2 = 2. Удобно также доопределить a0=1a_0 = 1 (пустой прямоугольник можно замостить одним способом — не класть ничего).

Далее нужно заметить, что количество способов замостить прямоугольник размера 2×n2 \times n получается из количества способов замостить прямоугольники поменьше. Мы можем положить одну костяшку вертикально, тогда останется замостить прямоугольник 2×(n−1)2 \times (n-1). Либо мы можем положить две костяшки горизонтально друг над другом, тогда останется прямоугольник 2×(n−2)2 \times (n-2). То есть

an=an−1+an−2a_n = a_{n-1} + a_{n-2}

Мы получили числа Фибоначчи с точностью до сдвига индексов. Теперь найдем производящую функцию A(z)=∑n=0∞anznA(z) = \sum\limits_{n=0}^{\oo} a_n z^n для этой последовательности. Умножим обе части рекуррентного соотношения на znz^n и просуммируем по всем n⩾2n \ge 2

∑n=2∞anzn=∑n=2∞an−1zn+∑n=2∞an−2zn\sum\limits_{n=2}^{\oo} a_n z^n = \sum\limits_{n=2}^{\oo} a_{n-1} z^n + \sum\limits_{n=2}^{\oo} a_{n-2} z^n

Выразим суммы через A(z)A(z). Левая часть равна A(z)−a0−a1 zA(z) - a_0 - a_1 \, z. Первая сумма справа равна z ∑n=2∞an−1 zn−1=z (A(z)−a0)z \, \sum\limits_{n=2}^{\oo} a_{n-1} \, z^{n-1} = z \, (A(z) - a_0). Вторая сумма справа равна z2 ∑n=2∞an−2 zn−2=z2 A(z)z^2 \, \sum\limits_{n=2}^{\oo} a_{n-2} \, z^{n-2} = z^2 \, A(z).

A(z)−1−z=z (A(z)−1)+z2 A(z)A(z)−1−z=z A(z)−z+z2 A(z)A(z) (1−z−z2)=1A(z) - 1 - z = z \, (A(z) - 1) + z^2 \, A(z) \\ A(z) - 1 - z = z \, A(z) - z + z^2 \, A(z) \\ A(z) \, (1 - z - z^2) = 1

Таким образом, мы получили замкнутое выражение для производящей функции чисел Фибоначчи

A(z)=11−z−z2A(z) = \frac{1}{1 - z - z^2}

Экспоненциальные производящие функции

Иногда производящая функция последовательности ana_n сложна и неудобна для работы, при этом связанная с ней последовательность an/n!a_n/n! имеет простую производящую функцию. Чтобы упростить себе жизнь, в таких случаях мы будем работать с an/n!a_n/n! и в самом конце выполним умножение на n!n!. Делать так приходится часто, поэтому введём отдельное определение.

Экспоненциальная производящая функция

Экспоненциальной производящей функцией (ЭПФ) называют степенной ряд вида

A^(z)=∑n=0∞an znn!\hat A (z) = \sum\limits_{n=0}^{\oo} a_n \, \frac{z^n}{n!}

Слово "экспоненциальная" употребляется здесь, так как функция eze^z будет ЭПФ для последовательности единиц.

Действия, которые мы проделывали с обычными производящими функциями будут давать немного другой результат.

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

Далее A^(z)\hat A(z) — ЭПФ последовательности ana_n, B^(z)\hat B(z) — ЭПФ последовательности bnb_n.

Умножение на zz даёт нам ЭПФ последовательности n an−1n \, a_{n-1}

z A^(z)=∑n=0∞an zn+1n!=∑n=1∞an−1 zn(n−1)!=∑n=1∞n an−1 znn!z \, \hat A(z) = \sum\limits_{n=0}^{\oo} a_n \, \frac{z^{n+1}}{n!} = \sum\limits_{n=1}^{\oo} a_{n-1} \, \frac{z^n}{(n-1)!} = \sum\limits_{n=1}^{\oo} n \, a_{n-1} \, \frac{z^n}{n!}

Дифференцирование здесь соответствует сдвигу влево

A^′(z)=∑n=0∞n anzn−1n!=∑n=1∞an zn−1(n−1)!=∑n=0∞an+1 znn!\hat A'(z) = \sum\limits_{n=0}^{\oo} n \, a_n \frac{z^{n-1}}{n!} = \sum\limits_{n=1}^{\oo} a_n \, \frac{z^{n-1}}{(n-1)!} = \sum\limits_{n=0}^{\oo} a_{n+1} \, \frac{z^n}{n!}

Интегрирование — напротив, соответствует сдвигу вправо

∫0zA^(t) dt=∑n=0∞an zn+1(n+1)!=∑n=1∞an−1 znn!\int\limits_0^z \hat A(t) \, dt = \sum\limits_{n=0}^{\oo} a_n \, \frac{z^{n+1}}{(n+1)!} = \sum\limits_{n=1}^{\oo} a_{n-1} \, \frac{z^n}{n!}

И самое интересное свойство, умножение ЭПФ

A^(z) B^(z)=∑n=0∞(∑k=0n(nk)ak bn−k)znn!\hat{A}(z) \, \hat{B}(z) = \sum\limits_{n=0}^{\oo} \left( \sum\limits_{k=0}^{n} \binom{n}{k} a_k \, b_{n-k} \right) \frac{z^n}{n!}

Последовательность, ЭПФ которой мы получили, называется биноминальной свёрткой.

Производящие функции Дирихле

На самом деле, возможны многие другие способы работы с последовательностями при помощи рядов. Здесь можно использовать, в принципе, любую систему "ядер" Кn(z)К_n(z), обладающих свойством

∑n=0∞an Kn(z)=0  ⟹  an=0\sum\limits_{n=0}^{\oo} a_n \, K_n(z) = 0 \implies a_n = 0

Для обычных производящих функций мы использовали ядра Kn(z)=znK_n(z) = z^n, для экспоненциальных производящих функций — Kn(z)=zn/n!K_n(z) = z^n/n!. Наиболее важная альтернатива производящим функциям и ЭПФ получается, если использовать ядра 1/nz1/n^z, они рассчитаны на последовательности, начинающиеся с n=1n=1, а не с n=0n=0. Своё название эта производящая функция получила в честь Густава Дирихле, внёсшего большой вклад в её изучение.

Производящая функция Дирихле

Производящая функция Дирихле (ПФД) — ряд вида

A~(z)=∑n=1∞annz\tilde A(z) = \sum\limits_{n=1}^{\oo} \frac{a_n}{n^z}

Наиболее интересным свойством производящих функций Дирихле является перемножение, оно даёт нам важный вид свёртки. Пусть A~(z)\tilde A(z) — ПФД последовательности ala_l, B~(z)\tilde B(z) — ПФД последовательности bmb_m, тогда

A~(z) B~(z)=∑l,m=1∞allz bmmz=∑n=1∞1nz ∑l,m=1∞al bm [l m=n]\tilde A(z) \, \tilde B(z) = \sum\limits_{l,m=1}^{\oo} \frac{a_l}{l^z} \, \frac{b_m}{m^z} = \sum\limits_{n=1}^{\oo} \frac{1}{n^z} \, \sum\limits_{l,m=1}^{\oo} a_l \, b_m \, [l \, m = n]

Получили ПФД свёртки делителей числа nn

∑d\nad bn/d\sum\limits_{d \divides n} a_d \, b_{n/d}

Ещё один интересный случай происходит, когда последовательность является мультипликативной функцией, то есть amn=am anпри m⊥na_{mn} = a_m \, a_n \quad \text{при}~ m \rprime n. В таких случаях, мы можем разложить ПФД в произведение по простым числам

A~(z)=∏p(1+appz+ap2p2z+ap3p3z+⋯ )\tilde A(z) = \prod\limits_p \left( 1 + \frac{a_p}{p^z} + \frac{a_{p^2}}{p^{2z}} + \frac{a_{p^3}}{p^{3z}} + \dotsm \right)

Дзета-функция Римана

Дзета-функция Римана

Наиболее распространённым частным случаем ПФД является Дзета-функция Римана — ПФД для последовательности единиц. Здесь накладывается условие Re⁡z>1\Re z > 1

ζ(z)=∑n=1∞1nz\zeta(z) = \sum\limits_{n=1}^{\oo} \frac{1}{n^z}

Удивительная связь дзета-функции с простыми числами устанавливается через произведение Эйлера. Чтобы вывести его, снова обратимся к сумме бесконечной геометрической прогрессии:

∑n=0∞xn=1+x+x2+⋯=11−x\sum\limits_{n=0}^{\oo} x^n = 1 + x + x^2 + \dotsb = \frac{1}{1-x}

Применим эту формулу для одного простого числа pp. Пусть x=p−zx = p^{-z}. Тогда сумма обратных степеней этого простого числа равна:

∑n=0∞1(pk)z=1+1pz+1p2z+⋯=11−p−z\sum\limits_{n=0}^\oo \frac{1}{(p^k)^z} = 1 + \frac{1}{p^z} + \frac{1}{p^{2z}} + \dotsb = \frac{1}{1 - p^{-z}}

Теперь рассмотрим произведение таких выражений по всем простым числам pp:

∏p11−p−z=(1+12z+14z+⋯ ) (1+13z+19z+⋯ ) (1+15z+125z+⋯ )⋯\prod\limits_p \frac{1}{1 - p^{-z}} = \left( 1 + \frac{1}{2^z} + \frac{1}{4^z} + \dotsb \right) \, \left( 1 + \frac{1}{3^z} + \frac{1}{9^z} + \dotsb \right) \, \left( 1 + \frac{1}{5^z} + \frac{1}{25^z} + \dotsb \right) \cdots

Раскрывая скобки в этом бесконечном произведении, мы будем перемножать слагаемые вида p−kzp^{-kz}. В силу основной теоремы арифметики, каждое натуральное число nn единственным образом представляется в виде произведения простых множителей.

Следовательно, в результате раскрытия скобок мы получим сумму обратных степеней n−zn^{-z} для всех натуральных чисел nn, причем ровно по одному разу. Таким образом, бесконечное произведение превращается в ряд Дирихле:

∏p(1−p−z)−1=∑n=1∞1nz=ζ(z)\prod\limits_p (1 - p^{-z})^{-1} = \sum\limits_{n=1}^\oo \frac{1}{n^z} = \zeta(z)

Упражнения

    1

    Найдите производящую функцию для последовательности n(n+1)/2={0,1,3,6,10,… }n(n+1)/2 = \{0, 1, 3, 6, 10, \dots\}

    2

    Пусть d(n)d(n) — функция, равная количеству делителей числа nn. Докажите, что производящая функция Дирихле для этой последовательности равна квадрату дзета-функции Римана:

    ∑n=1∞d(n)ns=ζ2(s)\sum\limits_{n=1}^{\oo} \frac{d(n)}{n^s} = \zeta^2(s)
    3

    Используя производящие функции, найдите явную формулу для nn-го члена последовательности, заданной соотношением:

    an=5an−1−6an−2при n⩾2a0=1, a1=0a_n = 5a_{n-1} - 6a_{n-2} \quad \text{при}~ n \ge 2 \\ a_0 = 1, \, a_1 = 0
    4

    Беспорядком называется перестановка длины nn без неподвижных точек (ни один элемент не остался на своем месте). Обозначим число беспорядков DnD_n. Докажите, используя ЭПФ, что:

    Dn=n!∑k=0n(−1)kk!≈n!eD_n = n! \sum\limits_{k=0}^{n} \frac{(-1)^k}{k!} \approx \frac{n!}{e}
    5

    Докажите теорему Эйлера: Количество разбиений числа nn на нечетные слагаемые равно количеству разбиений числа nn на различные слагаемые.

    6

    Рассмотрим функцию Мангольдта Λ(n)\Lambda(n), которая равна ln⁡p\ln p, если n=pkn = p^k (степень простого числа), и 00 в противном случае. Докажите, что ряд Дирихле для этой функции связан с логарифмической производной дзета-функции:

    ∑n=1∞Λ(n)ns=−ζ′(s)ζ(s)\sum\limits_{n=1}^{\oo} \frac{\Lambda(n)}{n^s} = - \frac{\zeta'(s)}{\zeta(s)}