Русская Википедия:Производящая функция последовательности

Шаблон:Другие значения Производя́щая фу́нкция после́довательности — алгебраическое понятие, которое позволяет работать с разными комбинаторными объектами аналитическими методами. Они дают гибкий способ описывать соотношения в комбинаторике, а иногда помогают вывести явные формулы для числа комбинаторных объектов определённого типа.

Если дана последовательность <math>\{ a_n \}</math> чисел <math>a_0, a_1, a_2, a_3, \ldots</math>, то из них можно построить формальный степенной ряд

<math>A(t)=\sum_{n=0}^\infty a_n t^n=a_0+a_1t+a_2t^2+a_3t^3+\dotsb</math>,

который называется производящей функцией <math>A(t)</math> этой последовательности.

Близким понятием является экспоненциальная производящая функция последовательности <math>\{a_n\}</math> — степенной ряд

<math>A(t)=\sum_{n=0}^\infty \frac{a_n t^n}{n!}=a_0+a_1t+\frac{a_2}{2}t^2+\frac{a_3}{6}t^3+\dotsb</math>,

у которого коэффициент перед <math>a_n</math> поделён на факториал числа <math>n</math>.

Замечания

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

<math>\sum_{n=0}^\infty (3^n)^n x^n</math> и <math>\sum_{n=0}^\infty (2^n)^n x^n</math>

имеют радиус сходимости ноль, то есть расходятся во всех точках, кроме нуля, а в нуле оба равны 1, то есть как функции они совпадают; тем не менее, как формальные ряды они различаются.

Свойства

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

Произведение производящих функций <math>A(x)=\sum_{n=0}^\infty a_n x^n</math> и <math>B(x)=\sum_{n=0}^\infty b_n x^n</math> последовательностей <math>\{a_n\}</math> и <math>\{b_n\}</math> является производящей функцией свёртки <math>c_n = \sum_{k=0}^n a_k b_{n-k}</math> этих последовательностей:

<math>A(x)B(x)=\sum_{n=0}^\infty c_n x^n.</math>

Если <math>A(x)=\sum_{n=0}^\infty a_n \frac{x^n}{n!}</math> и <math>B(x)=\sum_{n=0}^\infty b_n \frac{x^n}{n!}</math> — экспоненциальные производящие функции последовательностей <math>\{a_n\}</math> и <math>\{b_n\}</math>, то их произведение <math>A(x)\cdot B(x)=\sum_{n=0}^\infty c_n \frac{x^n}{n!}</math> является экспоненциальной производящей функцией последовательности <math>c_n = \sum_{k=0}^n {n\choose k} a_k b_{n-k}</math>.

Примеры использования

В комбинаторике

Число композиций

Пусть <math>B_m^n</math> — это количество композиций неотрицательного целого числа n длины m, то есть, представлений n в виде <math>n=k_1+k_2+\cdots+k_m</math>, где <math>\{k_i\}</math> — неотрицательные целые числа. Число <math>B_m^n</math> также является числом сочетаний с повторениями из m по n, то есть, количество выборок n возможно повторяющих элементов из множества <math>\{ 1, 2, \dots, m\}</math> (при этом каждый член <math>k_i</math> в композиции можно трактовать как количество элементов i в выборке).

При фиксированном m производящей функцией последовательности <math>B_m^0, B_m^1, \dots</math> является:

<math>\sum_{n=0}^\infty B_m^n x^n=(1+x+x^2+\cdots)^m=(1-x)^{-m}.</math>

Поэтому число <math>B_m^n</math> может быть найдено как коэффициент при <math>x^n</math> в разложении <math>(1-x)^{-m}</math> по степеням x. Для этого можно воспользоваться определением биномиальных коэффициентов или же непосредственно взять n раз производную в нуле:

<math>B_m^n = (-1)^n {-m\choose n} = \frac{m(m+1)\cdots(m+n-1)}{n!} = {m+n-1 \choose n}.</math>

Число связных графов

Обозначим через <math>a_n</math> число всех графов с вершинами <math>\{1,\dots,n\}</math> и через <math>c_n</math> число всех связных графов с этими вершинами.

Заметим, что <math>a_n=2^{\binom n 2}</math>. В частности легко посчитать первые члены этой последовательности

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

<math>a(x)=a_1\cdot x+\tfrac12\cdot a_2\cdot x^2+\dots+\tfrac1{n!}\cdot a_n\cdot x^n+\dots</math>

<math>c(x)=c_1\cdot x+\tfrac12\cdot c_2\cdot x^2+\dots+\tfrac1{n!}\cdot c_n\cdot x^n+\dots</math>

Оба ряда расходятся при <math>x\ne 0</math>, тем не менее их можно рассматривать как формальные степенные ряды и для этих рядов выполняется следующее соотношение:

из которого следует простое рекуррентное соотношение для <math>c_n</math>, позволяющее быстро найти первые члены этой последовательности^[1]

В теории вероятностей

Если <math>X</math> — положительная целочисленная случайная величина (частный случай дискретной), имеющая распределение вероятностей

<math>\mathbb{P}(X=j) = p_j,\; j=0,1,...;\quad \sum\limits_{j=0}^{\infty} p_j = 1</math>

то её математическое ожидание может быть выражено через производящую функцию последовательности <math>\{p_i\}</math>

<math>P(s)=\sum_{k=0}^\infty\;p_k s^k, </math>

как значение первой производной в единице: <math>M[X] = P'(1)</math> (стоит отметить, что ряд для P(s) сходится, по крайней мере, при <math>|s|\le 1</math>). Действительно,

<math>P'(s)=\sum_{k=1}^\infty{k p_k s^{k-1}}.</math>

При подстановке <math>s=1</math> получим величину <math>P'(1)=\sum_{k=1}^\infty{k p_k}</math>, которая по определению является математическим ожиданием дискретной случайной величины. Если этот ряд расходится, то <math>\lim_{s\to 1}P'(s)=\infty</math> — а <math>X</math> имеет бесконечное математическое ожидание, <math>P'(1)=M[X]=\infty</math>

Теперь возьмём производящую функцию <math>Q(s)</math> последовательности «хвостов» распределения <math>\{q_k\}</math>

<math>q_k=\mathbb{P}(X>k)=\sum_{j=k+1}^\infty{p_j};\quad Q(s)=\sum_{k=0}^\infty\;q_k s^k.</math>

Эта производящая функция связана с определённой ранее функцией <math>P(s)</math> свойством: <math>Q(s)=\frac{1-P(s)}{1-s}</math> при <math>|s|<1</math>. Из этого по теореме о среднем следует, что математическое ожидание равно просто значению этой функции в единице:

Дифференцируя <math>P'(s)=\sum_{k=1}^\infty{k p_k s^{k-1}}</math> и используя соотношение <math>P'(s)=Q(s)-(1-s)Q'(s)</math>, получим:

Чтобы получить дисперсию <math>D[X]</math>, к этому выражению надо прибавить <math>M[X]-M^2[X]</math>, что приводит к следующим формулам для вычисления дисперсии:

<math>D[X]=P(1)+P'(1)-P'^2(1)=2Q'(1)+Q(1)-Q^2(1)</math>.

В случае бесконечной дисперсии <math>\lim_{s\to 1}P(s)=\infty</math>.

Вариации и обобщения

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

Производящая функция Дирихле последовательности <math>\{a_n\}</math> — это формальный ряд Дирихле

<math>\sum_{n=1}^\infty \frac{a_n}{n^s}</math>.

Производящей функцией Дирихле последовательности единиц 1,1,… является дзета-функция Римана:
<math>\zeta(s) = \sum_{n=1}^\infty \frac{1}{n^s}.</math>

Если <math>\alpha(s)=\sum_{n=1}^\infty \frac{a_n}{n^s}</math> и <math>\beta(s)=\sum_{n=1}^\infty \frac{b_n}{n^s}</math> — производящие функции Дирихле последовательностей <math>\{a_n\}</math> и <math>\{b_n\}</math>, то их произведение <math>\alpha(s)\cdot \beta(s)=\sum_{n=0}^\infty \frac{c_n}{n^s}</math> является производящей функцией Дирихле свёртки Дирихле — последовательности <math>c_n = \sum_{d\mid n} a_d b_{n/d}</math>.

История

Метод производящих функций был разработан Эйлером в 1750-х годах; классическим примером служит пентагональная теорема Эйлера.

Примечания

Шаблон:Примечания

Литература

Ссылки

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

↑ Шаблон:Книга

[1] Шаблон:Книга

[1]

Партнерские ресурсы
Криптовалюты	Обмен криптовалют - www.bestchange.ru Криптовалютная биржа CoinEx Криптовалютная биржа Binance HIVE OS - операционная система для майнинга e4pool - Мультивалютный пул для майнинга.
Магазины	AliExpress — глобальная виртуальная (в Интернете) торговая площадка, предоставляющая возможность покупать товары производителей из КНР; computeruniverse.net - Интернет-магазин компьютеров(Промо код 5 Евро на первую покупку:FWWC3ZKQ);
Хостинг	DigitalOcean - американский провайдер облачных инфраструктур, с главным офисом в Нью-Йорке и с центрами обработки данных по всему миру;
Разное	Викиум - Онлайн-тренажер для мозга Like Центр - Центр поддержки и развития предпринимательства. Gamersbay - лучший магазин по бустингу для World of Warcraft. Ноотропы OmniMind N°1 - Усиливает мозговую активность. Повышает мотивацию. Улучшает память. Санкт-Петербургская школа телевидения - это федеральная сеть образовательных центров, которая имеет филиалы в 37 городах России. Lingualeo.com — интерактивный онлайн-сервис для изучения и практики английского языка в увлекательной игровой форме. Junyschool (Джунискул) – международная школа программирования и дизайна для детей и подростков от 5 до 17 лет, где ученики осваивают компьютерную грамотность, развивают алгоритмическое и креативное мышление, изучают основы программирования и компьютерной графики, создают собственные проекты: игры, сайты, программы, приложения, анимации, 3D-модели, монтируют видео. Умназия - Интерактивные онлайн-курсы и тренажеры для развития мышления детей 6-13 лет SkillBox - это один из лидеров российского рынка онлайн-образования. Среди партнеров Skillbox ведущий разработчик сервисного дизайна AIC, медиа-компания Yoola, первое и самое крупное русскоязычное аналитическое агентство Tagline, онлайн-школа дизайна и иллюстрации Bang! Bang! Education, оператор PR-рынка PACO, студия рисования Draw&Go, агентство performance-маркетинга Ingate, scrum-студия Sibirix, имидж-лаборатория Персона. «Нетология» — это университет по подготовке и дополнительному обучению специалистов в области интернет-маркетинга, управления проектами и продуктами, дизайна, Data Science и разработки. В рамках Нетологии студенты получают ценные теоретические знания от лучших экспертов Рунета, выполняют практические задания на отработку полученных навыков, общаются с экспертами и единомышленниками. Познакомиться со всеми продуктами подробнее можно на сайте https://netology.ru, линейка курсов и профессий постоянно обновляется. StudyBay Brazil – это онлайн биржа для португалоговорящих студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт. Автор24 — самая большая в России площадка по написанию учебных работ: контрольные и курсовые работы, дипломы, рефераты, решение задач, отчеты по практике, а так же любой другой вид работы. Сервис сотрудничает с более 70 000 авторов. Более 1 000 000 работ уже выполнено. StudyBay – это онлайн биржа для англоязычных студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт.