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

Введение

Основы метода производящих функций были заложены еще в 1750-х годах в трудах Эйлера. Дальнейшее развитие этот метод получил в трудах Лапласа и Ньютона. В настоящее время производящие функции широко используются в самых разных, зачастую не очень связанных друг с другом, отраслях знаний.
В их число входят комбинаторика, теория вероятностей, теория графов, дискретная математика и другие.
Основная идея заключается в придании аналитического вида наборам данных конечных или бесконечных последовательностей и применения развитых средств математического анализа к изучению их свойств.
Наиболее эффективно метод производящих функций зарекомендовал себя при решении задач комбинаторики. Такие задачи связаны с поиском комбинаций из конечного множества элементов. В том же строю находятся и задачи раскраски графов, поиска деревьев графа. Число элементов множества определяет сложность задачи.
Решение задач перебора элементов множества связана с изучением свойств числовых последовательностей. Представление числовых последовательностей в виде аналитических функций действительного или мнимого аргумента лежит в основе метода производящих функций, что позволяет применить к ним мощный, хорошо отработанный аппарат функционального анализа. И решение задач зачастую оказывается более простым и изящным.
В теории вероятностей приходится иметь дело с некоторым конечным набором событий. И здесь метод производящих функций упрощает нахождение вероятностных характеристик, в первую очередь математического ожидания и дисперсии, а также облегчает доказательство ряда предельных теорем наряду с близким методом характеристических функций.
Целью работы является изучение метода производящих функций, определение областей применимости метода, определение свойств производящих функций и разработка примеров применения метода производящих функций в различных областях математики.
Работа состоит из введения, двух глав и заключения.
В первой главе приводятся теоретические основы метода производящих функций, даны определения производящих функций, исследованы области применения производящих функций, приводятся основные их свойства.
Во второй главе приводится таблица основных производящих функций, а также применение производящих функций в комбинаторике, выводе рекуррентных соотношений, использование производящих функций в теории вероятностей и теории графов.
 
Теоретические основы метода производящих функций

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

Существуют различные виды определения производящей функции, но наиболее общим является представление в виде степенного ряда некой формальной переменной:
G(z)=∑_(n=0)^∞▒〖g_n z^n 〗=g_0+g_1 z+g_2 z^2+g_3 z^3+⋯ (1.1)
Формальная переменная обозначается различными буквами z, x, s, t.
Коэффициенты ряда gn представляют собой члены последовательности {gn}.
В теории вероятностей коэффициенты ряда соответствуют вероятностям наступления событий.
В зависимости от обстоятельств формальная переменная может трактоваться как принимающая действительные, так и комплексные значения.
Наряду с определением производящей функции (1.1) применяется и, так называемая, экспоненциальная производящая функция
G(z)=∑_(n=0)^∞▒(g_n z^n)/n!=g_0+g_1 z+g_2/2 z^2+g_3/6 z^3+⋯ (1.2)
Такое представление позволяет трактовать ее как обобщенный ряд Тейлора. Зачастую это позволяет рассматривать ее как аналитическую функцию и изучать свойства последовательности на основе теории аналитических функций. Однако, в общем случае, это не является обязательным условием.
В теории вероятностей коэффициенты ряда представляют собой вероятности несовместных событий, и производящая функция может трактоваться как математическое ожидание функции формальной переменной
G(z)=E(z^r )=∑_(r=0)^∞▒〖p_r z^r 〗, (1.3)
где Е() – символ математического ожидания,
рr – функция вероятности переменной r.
Использование производящих функций упрощает решение комбинаторных задач, помогает в доказательстве тождеств, позволяет выводить рекуррентные соотношения, находить параметры вероятностных характеристик случайных процессов, решать задачи раскраски графов.

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

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

Умножение производящей функции на постоянный коэффициент и суммирование (вычитание) двух или большего числа производящих функций приводит к суммированию (вычитанию) соответствующих членов ряда, т.е. образует линейную комбинацию:
(1.4)

К производящей функции применима операция дифференцирования: (1.5)
Дифференцированием производящей функции ряда , получим ряд
, (1.6)
Это означает, что производящей функцией последовательности является функция с коэффициентами .
Если продифференцировать раз функцию , получим
.
После деления на получим производящую функцию для ряда
. (1.7)

Сдвиг членов последовательности на одну позицию вправо с вставкой нулевого элемента соответствует умножению производящей функции на t. Так если , то для производящей функции t∙A(t) соответствует ряд .
Используя это правило, можем найти, что производящей функцией последовательности (0, 1, 2, …, , …) является функция : с коэффициентами . (1.8)

Интегрированию производящей функции соответствует формула: (1.9)
Примером использования соотношения (1.9) может служить нахождение суммы . По известному соотношению для бинома Ньютона
. (1.10)
Числа называют биномиальными коэффициентами. При из (1.10) получим:
. (1.11)
Соотношение (1.11) по определению показывает, что функция является производящей для последовательности биномиальных коэффициентов .
Путем интегрирования левой части равенства (1.11), найдем