Метод производящих функций

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

История

Метод был разработан Эйлером в 1750-х годах.

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

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

<math>\sum_{n=0}^\infty a_n x^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>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>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>M[X]=P'(1)=Q(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>M[X(X-1)]=\sum{k(k-1)p_k}=P(1)=2Q'(1)</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=0}^\infty a_n \frac{x^n}{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)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>.

Литература

• Бронштейн Е. М. [www.pereplet.ru/nauka/Soros/pdf/0102_103.pdf Производящие функции] // Соросовский Образовательный Журнал. — 2001. — Т. 7, № 2. — С. 103—108.
• Воронин С., Кулагин А. [kvant.mccme.ru/1984/05/metod_proizvodyashchih_funkcij.htm Метод производящих функций] // Квант. — 1984. — № 5.
• Ландо С. К. [www.mccme.ru/ium/ancient/combs93.html Лекции по комбинаторике]. — МЦНМО, 1994.
• Ландо С. К. [school-collection.edu.ru/catalog/res/d62ef84c-a780-11dc-945c-d34917fee0be/view Лекции о производящих функциях]. — 3-е изд., испр.. — М.: МЦНМО, 2007. — 144 с. — ISBN 978-5-94057-042-4.
• В. Феллер. Глава XI. Целочисленные величины. Производящие функции // Введение в теорию вероятностей и её приложения = An introduction to probability theory and its applicatons / Пер. с англ. Р. Л. Добрушина, А. А. Юшкевича, С. А. Молчанова; С предисловием А. Н. Колмогорова; Под ред. Е. Б. Дынкина. — 2-е изд. — М.: Мир, 1964. — С. 270—272.
• Herbert S. Wilf. [www.math.upenn.edu/~wilf/DownldGF.html Generatingfunctionology]. — Academic Press, 1994. — ISBN 0-12-751956-4.

Ссылки

• [www.genfunc.ru/ Производящие функции]

Отрывок, характеризующий Метод производящих функций

– Куда же это ведут тебя, голубчик ты мой? – сказала она. – Девочку то, девочку то куда я дену, коли она не ихняя! – говорила баба.
– Qu'est ce qu'elle veut cette femme? [Чего ей нужно?] – спросил офицер.
Пьер был как пьяный. Восторженное состояние его еще усилилось при виде девочки, которую он спас.
– Ce qu'elle dit? – проговорил он. – Elle m'apporte ma fille que je viens de sauver des flammes, – проговорил он. – Adieu! [Чего ей нужно? Она несет дочь мою, которую я спас из огня. Прощай!] – и он, сам не зная, как вырвалась у него эта бесцельная ложь, решительным, торжественным шагом пошел между французами.
Разъезд французов был один из тех, которые были посланы по распоряжению Дюронеля по разным улицам Москвы для пресечения мародерства и в особенности для поимки поджигателей, которые, по общему, в тот день проявившемуся, мнению у французов высших чинов, были причиною пожаров. Объехав несколько улиц, разъезд забрал еще человек пять подозрительных русских, одного лавочника, двух семинаристов, мужика и дворового человека и нескольких мародеров. Но из всех подозрительных людей подозрительнее всех казался Пьер. Когда их всех привели на ночлег в большой дом на Зубовском валу, в котором была учреждена гауптвахта, то Пьера под строгим караулом поместили отдельно.


В Петербурге в это время в высших кругах, с большим жаром чем когда нибудь, шла сложная борьба партий Румянцева, французов, Марии Феодоровны, цесаревича и других, заглушаемая, как всегда, трубением придворных трутней. Но спокойная, роскошная, озабоченная только призраками, отражениями жизни, петербургская жизнь шла по старому; и из за хода этой жизни надо было делать большие усилия, чтобы сознавать опасность и то трудное положение, в котором находился русский народ. Те же были выходы, балы, тот же французский театр, те же интересы дворов, те же интересы службы и интриги. Только в самых высших кругах делались усилия для того, чтобы напоминать трудность настоящего положения. Рассказывалось шепотом о том, как противоположно одна другой поступили, в столь трудных обстоятельствах, обе императрицы. Императрица Мария Феодоровна, озабоченная благосостоянием подведомственных ей богоугодных и воспитательных учреждений, сделала распоряжение об отправке всех институтов в Казань, и вещи этих заведений уже были уложены. Императрица же Елизавета Алексеевна на вопрос о том, какие ей угодно сделать распоряжения, с свойственным ей русским патриотизмом изволила ответить, что о государственных учреждениях она не может делать распоряжений, так как это касается государя; о том же, что лично зависит от нее, она изволила сказать, что она последняя выедет из Петербурга.
У Анны Павловны 26 го августа, в самый день Бородинского сражения, был вечер, цветком которого должно было быть чтение письма преосвященного, написанного при посылке государю образа преподобного угодника Сергия. Письмо это почиталось образцом патриотического духовного красноречия. Прочесть его должен был сам князь Василий, славившийся своим искусством чтения. (Он же читывал и у императрицы.) Искусство чтения считалось в том, чтобы громко, певуче, между отчаянным завыванием и нежным ропотом переливать слова, совершенно независимо от их значения, так что совершенно случайно на одно слово попадало завывание, на другие – ропот. Чтение это, как и все вечера Анны Павловны, имело политическое значение. На этом вечере должно было быть несколько важных лиц, которых надо было устыдить за их поездки во французский театр и воодушевить к патриотическому настроению. Уже довольно много собралось народа, но Анна Павловна еще не видела в гостиной всех тех, кого нужно было, и потому, не приступая еще к чтению, заводила общие разговоры.
Новостью дня в этот день в Петербурге была болезнь графини Безуховой. Графиня несколько дней тому назад неожиданно заболела, пропустила несколько собраний, которых она была украшением, и слышно было, что она никого не принимает и что вместо знаменитых петербургских докторов, обыкновенно лечивших ее, она вверилась какому то итальянскому доктору, лечившему ее каким то новым и необыкновенным способом.
Все очень хорошо знали, что болезнь прелестной графини происходила от неудобства выходить замуж сразу за двух мужей и что лечение итальянца состояло в устранении этого неудобства; но в присутствии Анны Павловны не только никто не смел думать об этом, но как будто никто и не знал этого.
– On dit que la pauvre comtesse est tres mal. Le medecin dit que c'est l'angine pectorale. [Говорят, что бедная графиня очень плоха. Доктор сказал, что это грудная болезнь.]
– L'angine? Oh, c'est une maladie terrible! [Грудная болезнь? О, это ужасная болезнь!]
– On dit que les rivaux se sont reconcilies grace a l'angine… [Говорят, что соперники примирились благодаря этой болезни.]
Слово angine повторялось с большим удовольствием.
– Le vieux comte est touchant a ce qu'on dit. Il a pleure comme un enfant quand le medecin lui a dit que le cas etait dangereux. [Старый граф очень трогателен, говорят. Он заплакал, как дитя, когда доктор сказал, что случай опасный.]
– Oh, ce serait une perte terrible. C'est une femme ravissante. [О, это была бы большая потеря. Такая прелестная женщина.]
– Vous parlez de la pauvre comtesse, – сказала, подходя, Анна Павловна. – J'ai envoye savoir de ses nouvelles. On m'a dit qu'elle allait un peu mieux. Oh, sans doute, c'est la plus charmante femme du monde, – сказала Анна Павловна с улыбкой над своей восторженностью. – Nous appartenons a des camps differents, mais cela ne m'empeche pas de l'estimer, comme elle le merite. Elle est bien malheureuse, [Вы говорите про бедную графиню… Я посылала узнавать о ее здоровье. Мне сказали, что ей немного лучше. О, без сомнения, это прелестнейшая женщина в мире. Мы принадлежим к различным лагерям, но это не мешает мне уважать ее по ее заслугам. Она так несчастна.] – прибавила Анна Павловна.