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

25

Размещено на http://www.allbest.ru/

Министерство Образования Российской Федерации

Благовещенский Государственный Педагогический Университет

Кафедра алгебры и геометрии

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

Курсовая работа

Выполнил: Попов А.В.

Проверил: Федорищев Б.Г.

Благовещенск 2003

План

1. Введение

2. Основная часть

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

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

2.3 Простейшие производящие функции

2.4 Производящие функции числа основных комбинаторных объектов

3. Заключение

4. Список литературы

1. Введение

Общепризнано, что метод производящих функций является наиболее эффективные средством решения перечислительных комбинаторных задач. В самом деле, в таких задачах речь идет о нахождении числа тех или иных конфигураций из элементов некоторого конечного множества. При этом мощность множества представляем собой основной параметр задачи. Тем самым решение перечислительной задачи естественным образом оказывается связанным с изучением свойств числовых последовательностей. Основная идея производящих функций состоит в сопоставлении каждой числовой последовательности функции действительного (или комплексного) переменного, причем отношения между последовательностями отражаются в отношениях между функциями. К функциям же применимы аналитические методы исследования, которые часто оказываются проще и более удобны, чем комбинаторные методы непосредственного оперирования с числовыми последовательностями; поэтому такой подход часто приводит к изящным результатам, в то время как прямое решение повлекло бы за собой громоздкие вычисления.

2. Основная часть

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

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

a0,a1,a2,…

называют степенной ряд вида

Часто бывает удобно вместо ряда (1.2) рассматривать ряд вида

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

Числа an и называются коэффициентами ряда (1.2) и ряда (1.3) соответственно.

Мы будем считать, что a0,a1,a2,… являются действительными (или комплексными) числами, но, вообще говоря они могут быть элементами произвольной природы. Например, являться многочленами, функциями или в свою очередь быть степенными рядами.

Если ряды (1.2) и (1.3) являются сходящимися, то их суммы можно рассматривать как соответствующие производящие функции и используя операции над функциями можно получить полезную информацию о последовательности (1.1). Если же радиус сходимости этих рядов равен нулю, то оперировать с ними можно только рассматривая их как некоторые формальные объекты. Однако оперировать с такими объектами можно только в рамках некоторых формальных исчислений. Такими исчислениями являются алгебры формальных степенных рядов.

Будем считать, что степенные ряды

и

являются формальными объектами. Определим основные операции над этими формальными объектами.

Определение 1.2

(1) = и , если для любого n an=bn;

(2) +=,

=

(3) ()()=, где cn=

()()=, где dn=

Например, если

a*(x)=1-3x2+7x4-15x6+31x8-…

b*(x)=1+x+x2+x3+…

то коэффициент при x8 в a*(x)•b*(x) равен

=1-3+7-15+31=21

Обозначим через и соответственно множество всех степенных рядов вида (1.1) и вида (1.2), где . (Здесь через R мы обозначили множество действительных чисел.)

В дальнейшем при an=0 n>m ряд (1.2) будем отождествлять с многочленом

.

Заметим, что в этом случае сложение и умножение, определённое для степенных рядов совпадает со сложением и умножением обычных многочленов.

Легко проверить, что относительно сложения и умножения (введённых выше) и являются ассоциативно-коммуникативными кольцами. Рассмотрим некоторые простейшие свойства этих колец.

Теорема 1.1 Кольца и являются областью целостности (т.е. для любых и из и следует).

ДОКАЗАТЕЛЬСТВО. Доказательство дадим только для кольца т.к. для кольца оно полностью аналогичное.

Предположим, что и , другими словами существуют и такие, что и . Пусть

и .

Так как и, очевидно, , то и, следовательно, .

Введём в и операцию умножения на действительные числа.

Определение 1.3 Для любого

(1) ,

(2) .

Нетрудно проверить, что для любых и выполняются соотношения:

, ,

, ,

.

Таким образом, кольца и являются (линейными) алгебрами над полем действительных чисел.

Алгебру обычно называют алгеброй Коши, а алгебру - символическим исчислением Блиссара.

В дальнейшем, рассматривая степенные ряды как объекты и мы будем говорить о формальных степенных рядах.

Рассмотрим операцию подстановки одного степенного ряда в другой.

Пусть

 и

Рассмотрим выражение

Лемма 1.2 если , то выражение, стоящее в правой части равенства (1.5), является степенным рядом.

ДОКАЗАТЕЛЬСТВО. Очевидно,

, ,

и т.д.

Пусть

Покажем, что если , то для любого n

Проведём индукцию по n.

Шаг индукции: n=1.

Индуктивное предположение.

Покажем, что

В самом деле, так как

,

то при k<n в силу индуктивного предположения;

при k=n , поскольку в силу индуктивного предположения и по условию.

В силу (1.6) можно записать

Так как , n=1,2,…, то

Таким образом, выражение (1.5) действительно является степенным рядом.

Ряд (1.5) будем считать результатом подстановки степенного ряда в степенной ряд .

Аналогично проверяется, что если , то выражение

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

Вместо иногда будем писать или просто .

Нетрудно проверить выполнение следующих равенств

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

Покажем, что в кольцах и иногда выполнимо деление.

Определение 1.4 Ряд называется обратным ряду f, если

.

Мы обозначаем этот обратный ряд через . Как обычно для любого положительного целого числа n мы полагаем .

Теорема 1.3 Пусть и . Обратные элементы для f и f' существуют тогда и только тогда, когда .

ДОКАЗАТЕЛЬСТВО. Доказательство дадим только для кольца .

Необходимость этого условия из того, что если

,

то a0b0=1, откуда следует, что .

Достаточность. Покажем, что

(Здесь 1-x является рядом )

В самом деле согласно определению это произведение равно , где

Пусть . Рассмотрим ряд

.

Так как , то можно подставить ряд f(x) вместо x в (1.9). Очевидно, в результате мы получим равенство



Откуда в силу равенства имеем

,

т.е. ряд является обратным ряду .

Таким образом если f и g два ряда и , то можно считать, что

.

В алгебрах и можно ввести формальные дифференцирование и интегрирование положив

(1) ,

,

(2) ,

Легко проверить, что все элементарные свойства дифференцирования и интегрирования выполняются и для степенных рядов.

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

Экспоненциальным рядом называется ряд

exp

который обозначается также через ex .Логарифмическим рядом называется ряд

.

Если - действительное число, то биномиальным рядом называется ряд

.

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

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

Например, ранее мы показали

,

т.е.



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

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

Пример.

Тождество

справедливо как тождество между функциями и имеет смысл как утверждение между формальными степенными рядами. В самом деле, пусть

.

Так как , то определена подстановка ряда в ряд , но . Следовательно данное тождество верно и для формальных степенных рядов.

Тождество

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

2.3 Простейшие производящие функции

Для удобства вместо мы будем писать a(n). Напомним, что производящую функцию последовательности

a(0), a(1), a(1),…

мы обозначим через , а её экспоненциальную производящую функцию - через .

В приведённой ниже таблице (1) содержаться примеры некоторых простейших производящих функций, которые можно легко установить, разлагая соответствующую функцию в ряд Маклорена.

Рассмотрим наиболее часто встречающиеся операции над числовыми последовательностями и покажем какие операции над соответствующими производящими функциями соответствуют этим операциям.

Некоторые простейшие производящие функции (1)

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

Линейные операции

Если , то

Сдвиг начала

Если , то

Если , то

Изменение масштаба

Если , то

Подобие

Если , то

Свёртка

Если , то

Равенства (1.12) - (1.17) являются очевидными следствиями определений.

Пусть . Выразим через .

Очевидно, . Если - производящая функция для , то согласно (1.13) производящей функцией для является . Следовательно,

.

Откуда имеем

В качестве примера использования формул (1.12) - (1.18) рассмотрим несколько задач.

1. Вычислить сумму .

Пусть . Тогда

(см. (1.12) и таблицу 1), т.е.

.

Очевидно,

(сумма геометрической прогрессии).

Выполнив элементарные преобразования, получим

.

Подставив в (1.19), имеем

.

Таким образом,

.

Предположим, что

, тогда

(см. таблицу 1).

Положим . Очевидно, и .

В силу (1.14) и (1.20)

и .

Следовательно,

, т.е.

.

Вычислить сумму .

Известно, что

.

(Напомним, что , если .) Рассмотрим произведение

, где .

С другой стороны

.

Приравнивая коэффициенты при xm,получим

.

Таким образом .

Вычислить сумму .

Известно, что

, биномиальный ряд при и

.

Перемножая правые части данных равенств получим

.

С другой стороны

.

Следовательно,

.

Приравнивая коэффициенты при , получим

.

Вычислить сумму .

Обозначим

.

Тогда

.

(см. (1.15) и таблицу 1).

Следовательно,

.

Так как , то . Следовательно, .

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

.

Поскольку , если k>n, то

.

Таким образом,

.

2.4 Производящие функции числа основных комбинаторных объектов

Найдём производящие функции числа основных комбинаторных объектов.

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

Рассмотрим произведение конечного числа биномов

.

Очевидно,

Заметим, что каждому слагаемому коэффициента при можно сопоставить сочетание из множества по k.

Полагая в (1.21) , получим

.

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

С другой стороны мы знаем, что

.

Приравнивая коэффициенты при xk, получим уже известную нам формулу для подсчёта числа сочетаний из n элементов по k

.

В произведении каждый множитель является линейным двучленом, который благодаря наличию в нём слагаемых 1 и ekx, указывает на возможность наличия или отсутствия в каждом слагаемом при степенях x элемента ek. Это произведение порождает сочетания, так как коэффициент при xk в нём получается выбором единицы в n-k из n двучленных множителей и в k оставшихся после такого выбора множителях - членов вида eix всеми возможными путями. Эти коэффициенты по самому их определению задают сочетания из n по k. Каждый элемент в любом сочетании может появляться не более одного раза, ибо любой множитель состоит только из двух слагаемых.

Рассмотрим произведение в которое множителем входит квадратный трехчлен.



В данном случае каждому слагаемому коэффициента при можно сопоставить сочетание с повторениями из множества по k, причём элемент e1 имеет кратность не более двух (а именно 0,1,2), а кратность элементов e2,e3 не более единицы.

Полагая , получим

Как нетрудно видеть коэффициент при в (1.22) равен числу таких сочетаний и, следовательно, производящей функцией их числа является функция

.

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

алгебра кош степенный экспоненциальный ряд

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

Рассмотрим несколько примеров подсчёта числа сочетаний с повторениями.

Найти число решений в целых неотрицательных числах уравнения

. (1.23)

Ясно, что число таких решений равно числу сочетаний с повторениями из множества , причём кратностью элемента xi является любое целое неотрицательное число кратное коэффициенту при xi в уравнении (1.23).

Как мы знаем производящей функцией для последовательности a(n) числа таких сочетаний является

. (1.24)

Коэффициент при xn в этом ряде даст ответ на нашу задачу.

Найти число сочетаний с повторениями из n элементов по k без всяких ограничений на кратность элементов в данном сочетании (т.е. кратность каждого элемента может быть целым неотрицательным числом). Напомним, что выше это число мы обозначали как .

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

Тогда

(см. (1.10))

Положим в биномиальном ряде . Тогда

.

Следовательно,

(1.25)

Откуда . (Это хорошо известная формула для числа сочетаний с неограниченными повторениями.)

Найти число сочетаний с повторениями из n элементов по k, в которых каждый элемент встречается не менее r раз (т.е. кратность каждого элемента может быть одним из чисел r,r+1,r+2,…).

Очевидно, производящей функцией b(k) для числа сочетаний такого вида является функция

.

Пусть , тогда . Согласно (1.13)

Выше было установлено, что (см. (1.25)).

Следовательно,

Таким образом искомое число сочетаний равно 0, если и равно

, если .

Производящая функция числа выборок

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

Сначала рассмотрим наиболее простой случай выборок - размещения. Согласно биному Ньютона для любого натурального n мы имеем равенство

,

которое можно переписать в виде

Таким образом, функция является экспоненциальной производящей функцией числа размещений. Рассмотренный случай показывает, что для подсчёта числа упорядоченных наборов удобно пользоваться экспоненциальными степенными рядами.

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

В самом деле коэффициент равен а коэффициент при равен но, как мы знаем, этому числу равно число k-выборок из множества E, имеющих состав .

Пример. Найти число 3-выборок из множества в которые элемент может входить не более одного раза, элемент входит обязательно, но не более двух раз, а элемент либо не входит, либо входит два раза.

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

Число искомых выборок равно коэффициенту при , т.е. равно 6.

Для получения числа k-выборок с неограниченными повторениями (любой элемент может повторятся в данной k-выборке произвольное число раз) из множества, состоящего из n элементов, рассмотрим производящую функцию



Приходим к хорошо известному факту - число k-выборок из множества, состоящего из n элементов, равно nk.

Производящая функция числа беспорядков

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

Обозначим число всех беспорядков любого множества, состоящего из n элементов, через d(n). Как обычно множество всех подстановок множества E будем обозначать через SE. Пусть и

.

Очевидно, если , то . Нетрудно заметить, что , поэтому, так как для любых различных Q и Q', то

или .

Пусть

 (1.26)

- экспоненциальная производящая функция последовательности d(n).

Перемножая ряды (1.26) и получим

, т.е.

или .

Как мы знаем . Следовательно,

.

Приравнивая коэффициенты при xn, получим

или .

Вспоминая, что , мы можем записать

,

а это означает, что и отличаются друг от друга меньше чем на . Следовательно, является весьма хорошим приближением для d(n).

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

Разбиения. Производящие функции числа разбиений

Рассмотрим следующую задачу: сколькими способами можно представить данное натурально число n в виде суммы

, (1.27)

где - положительные целые числа.

Будем называть такое представление разбиением числа n на k частей. Возможны два случая:

две суммы вида (1.27), различающиеся порядком слагаемых считаются различными (такие разбиения принято называть композициями);

суммы вида (1.27), отличающиеся друг от друга только порядком слагаемых, не различаются (именно в этом случае принято говорить о разбиении).

Обозначим число композиций натурального числа n на k частей через ck(n). Нетрудно заметить, что ck(n) равно числу способов, которыми можно разместить k-1 чёрточек в n-1 промежутках между n единицами, т.е. . Найдём производящую функцию числа композиций натурального числа n на k частей. Будем считать, что ck(n)=0, если n<k. Очевидно,

.

Пусть . Тогда (см. 1.25). Так как

,

то, используя операцию сдвиг начала, получим

.

Если число частей не фиксировано, то число таких композиций равно

Положим c(0)=0. Найдём .

.

Если , то (см. таблицу 1) и поскольку

,

то .

Второй случай значительно сложнее и ставит ряд интересных задач. Будем обозначать через pk(n) число разбиений натурального числа n на k частей, а через p(n) - число разбиений n на произвольное число частей. Очевидно,

.

Положим , считая, что число 0 имеет единственное пустое разбиение.

Обозначим через число разбиений числа n на части, наибольшая из которых равна k, полагая =1.

Заметим, что существует взаимно-однозначное соответствие между множеством решений уравнения

(1.28)

в неотрицательных целых числах и множеством всех разбиений числа n на части, наибольшая из которых равна k. В самом деле, если является решением уравнения (1.28) в неотрицательных целых числах, то ему соответствует разбиение числа n, в котором слагаемое встречается раз и наоборот каждому такому разбиению соответствует решение уравнения (1.28) в неотрицательных целых числах.

Как и во многих разделах математики, привлечение геометрических соображений в теории разбиений делает многие доказательства более наглядными.

Пусть - разбиение числа п. Без потери общности можно считать что (напомним, что для нас не важен порядок слагаемых). Нарисуем массив из n точек, располагая их в k строчек так, чтобы i-я строчка содержала ai точек, и выравнивая все строчки слева (с.м. рис. 1). Эта диаграмма называется графом Феррера разбиения .

рис. 1

Каждому разбиению числа n на k частей поставим в соответствие разбиение этого числа, которое получается транспозицией графа Феррера исходного разбиения (т.е. перемены ролями строчек и столбцов). Полученное разбиение будем называть сопряженным для первоначального. Легко заметить, что такое соответствие является биекцией между разбиениями числа n на k частей и разбиениями n на части, наибольшее из которых равно k (см. рис. 1). Таким образом, верно следующее утверждение.

Теорема 1.4 Число разбиений натурального числа n на k частей равно числу разбиений n на части, наибольшая из которых равна k, т.е. .

Теорема 1.5 Пусть - производящая функция последовательности

Тогда

.

ДОКАЗАТЕЛЬСТВО. Для доказательства равенства

(1.29)

установим биекцию между множеством решений уравнения (1.28) в неотрицательных целых числах и множеством слагаемых вида xn, получающихся при раскрытии скобок в правой части (1.29) (без приведения подобных членов). Каждому решению уравнения (1.28) в неотрицательных целых числах поставим в соответствие слагаемое вида

,

которое получается, если из первой скобки выбрать , из второй - . ,…, из k-ой - . Легко проверить, что данное соответствие действительно является биекцией. Поскольку в свою очередь существует биекция между разбиениями числа n на части, наибольшая из которых равна k, и решениями уравнения (1.28) в неотрицательных целых числах, равенство (1.29) верно.

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

Теорему 1.4 можно существенно обобщить. Пусть H - некоторое множество натуральных чисел (т.е. ). Обозначим через и соответственно число разбиений числа n на части, которые принадлежат множеству H, и число таких разбиений, у которых каждая часть встречается не более k раз.

Теорема 1.7 Если , то справедливы равенства

,

.

Полагая в теореме 1.7 H=N, получим равенство

,

которое выполняется при .

Вспомним из курса математического анализа, что по определению

, если .

Заметим, что равенства в теореме 1.7 носят функциональный характер.

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

Теорема 1.8 (Эйлер) Число разбиений числа n на попарно различимые слагаемые равно числу разбиений числа n на нечётные слагаемые.

ДОКАЗАТЕЛЬСТВО. Очевидно, число разбиений числа n на попарно различимые слагаемые равно и в силу теоремы 1.7

.

Обозначим через Q множество нечётных натуральных чисел. Тогда в силу теоремы 1.7

,

то или

.

Поскольку представление функции степенным рядом единственно, то .

Аналогично доказывается следующее утверждение

Теорема 1.9 (Глайшер) Число разбиений числа n на части, которые не делятся на k+1 равно числу разбиений n, у которых каждая часть встречается не более k раз.

3. Заключение

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

4. Список литературы

1. В.Л. Матросов, В.А. Стеценко «Лекции по дискретной математике», М.: 1997 г.

2. Большой энциклопедический словарь «Математика» Научное издание «Большая Российская энциклопедия» 1998 г.

3. Э.З. Шувалова, Б.Г. Агафонов, Г.И. Богатырёв «Повторим математику» М.: Издание высшая школа, 1974 г.

Размещено на Allbest.ru