нет. Учебное пособие в оронеж 2011 фгбоу впо Воронежский государственный технический университет
 Скачать 0.65 Mb.
|
1.5. Производящие функции1.5.1. Общие сведения о производящих функцияхДля решения комбинаторных задач могут быть использованы методы математического анализа. Основой этого служит метод производящих функций. Этот метод позволяет достичь изучения свойств последовательностей. Он применяется для перечисления комбинаторных чисел и для установления комбинаторных тождеств. Исходным пунктом этого метода является последовательность комбинаторных чисел {ak} и последовательность базисных функций . Рассмотрим формальный ряд В частности, если последовательность конечна, т.е. , то ряд представляет собой многочлен. При определенных ограничениях, ряд будет сходиться и тогда, в некоторой области он будет задавать функцию Функция F(x) называется производящей функцией для заданной последовательности комбинаторных чисел {ak} относительно заданной базисной последовательности функций . Наиболее часто в качестве базисной рассматривается последовательность , (k = 0,1,..). Получающиеся при этом производящие функции называются обычными. Т.е. обычные производящие функции имеют вид: В комбинаторном анализе используются также экспоненциальные производящие функции . Для производящих функций по аналогии со сходящимися рядами определяются операции сложения, умножения, дифференцирования, интегрирования и т.д. при этом xявляется действительной или комплексной переменной. При выполнении условий сходимости производящие функции являются аналитическими. Рассмотрим ряд примеров. 1.5.2. Производящая функция для биноминальных коэффициентовПолучим производящую функцию для конечной последовательности чисел, представляющих собой различное число сочетаний изn элементов -– . Известно, что и Эти равенства являются частными случаями более общей формулы, дающей разложение для . Запишем в виде Раскроем скобки в правой части этого равенства, причем будем записывать все множители в том порядке, в котором они нам встретятся. Например, запишем в виде: а - в виде: Видно, что в верхнюю формулу входят все размещения с повторениями, составленные из букв и по две буквы в каждом размещении, а в нижнюю формулу - размещения с повторениями из тех же букв, но состоящие из трех букв каждое. То же самое и в общем случае — после раскрытия скобок в формуле мы получим всевозможные размещения с повторениями букв и , состоящие из элементов. Приведем подобные члены. Подобными будут члены, содержащие одинаковое количество букв (тогда и букв в них будет поровну). Найдем, сколько будет членов, в которые входит букв и, соответственно, букв . Эти члены являются перестановками с повторениями, составленными из букв и букв . Поэтому их число равно Отсюда вытекает, что после приведения подобных членов выражение войдет с коэффициентом . Итак, мы доказали, что Это равенство принято называть формулой бинома Ньютона. Если положить в этом равенстве , то получим Мы видим, что является производящей функцией для чисел . С помощью этой производящей функции можно сравнительно просто доказать многие свойства чисел . Пусть , (k=0,1,…,n) Тогда В данном случае в качестве производящей функции выступает бином Ньютона . Используя заданную производящую функцию, докажем тождество: Для этого возьмем тождество Они эквивалентны следующему Сравнивая коэффициенты при xn, получим 1.5.3. Производящая функция для чисел ФибоначчиЧисла Фибоначчи – это элементы числовой последовательности, в которой каждый последующий элемент равен сумме двух предыдущих. Т.е. последовательность чисел Фибоначчи задается рекуррентным уравнением: Воспользуемся понятием производящей функции для выражения общего члена чисел Фибоначчи. Возьмем в качестве последовательности базисных функций . Ряд сходится при и определяет производящую функцию Помножив данное выражение на x и на , получим: Сложив эти два выражения имеем: Следовательно . Отсюда получается явный вид производящей функции Корни знаменателя определяются из уравнения Разложим F(x) на элементарные дроби, т.е. Т.е. получим Рассмотрим сумму бесконечно убывающих геометрических прогрессий При Следовательно Отсюда |