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

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

Введение

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

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

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

Цели:

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

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

Задачи:

1. Познакомится с литературой по данному вопросу.

2. Выделить два различных случая:

a. Одна из двух переменных формальная.

b. Обе переменные 0 формальные.

3. Нахождение производящих функций для последовательностей многочленов Фибоначчи и Люка.

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

5. Рассмотрение других способов задания производящих функций.

l обозначить исследуемую проблему и ее актуальность;

l определить цель курсовой работы и задачи, которые необходимо решить для достижения поставленной цели;

l дать краткую аннотацию содержания курсовой работы.

1. Многочлены

1.1 Задача о числе счастливых билетов

Троллейбусный (трамвайный) билет имеет номер, состоящий из шести цифр. Билет считается счастливым, если сумма первых трёх цифр равна сумме последних трёх, например, 024321. Чему равно N - число счастливых билетов? Количество счастливых билетов можно разделить на 28 классов. В каждом классе - билеты с суммой первых трёх цифр, равной . Обозначим - число трёхзначных номеров с суммой цифр, равной . Тогда в классе счастливых билетов.

Для вычисления , рассмотрим следующие многочлены:

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

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

Заметим справедливость следующих равенств:



.

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

Заметим справедливость следующих равенств:

Доказательство.

Нетрудно заметить, что

-

При возведении в третью степень получаем:

Можно заметить, что

(так как каждому билету с суммой цифр i, можно поставить в соответствие билет с суммой цифр

Причём коэффициент при равен числу счастливых билетов.



И тогда коэффициент при равен

Ответ: число счастливых билетов равно

1.2 Формула Бинома Ньютона

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

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

Докажите тождества.

1)

Подставляем в соотношение и получаем верное равенство.

2)

Подставляем в соотношение и получаем верное равенство.

3)

Подставляем в соотношение и получаем верное равенство.

Подставляем в соотношение и получаем верное равенство.

2. Производящие функции и действия над ними

2.1 Определение производящей функции

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

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

Определнение. Суммой двух производящих функций

Определение. Произведением двух производящих функций А и В называется производящая функция



Оаределение. Пусть и две производяцие функцмм. Причём В(0) = 0. Подстановкой проиводяцией функцией В в функцию А называется производящая функция вида

А(+(

Если, например. , то

А(

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

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

Интегралом этой функции называется функция

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

.

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

.

.

.

2.2 Элементарные производящие функции

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

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

где - произвольное число.

Коэффициент при в этой записи называется числом сочетаний из по n и обозначается или.

ln

Между введенными функциями имеются соотношения, которые также связаны с комбинаторными тождествами. Которые мы примем без доказательства.

1. .

2. .

3. .

4. .

5. .

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

Пример 1. Последовательность

Найти производящую функцию.

Тогда имеем: А=1: . Наша производящая функция имеет вид:

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

.

Ответ;

Наша произв. функция имеет вид:

2.4 Решение рекуррентных соотношений соотношений с помощью производящей функции

Задание 1. Найдите общий член последовательности, заданной рекуррентно:

1). .

Решение.

.

.

Находим неизвестные , решая квадратное уравнение.

иначе:

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

При n=0 при n=1 Все результаты удовлетворяют начальным условиям.

2).

Решение.

).

.

Находим неизвестные , решая квадратное уравнение. Данное уравнение является формулой сокращенного умножения

Получаем:

Тогда: .

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

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

1. a) Рассмотрим производящую функцию для последовательности

1, 1, 1,…. Производящая функция для неё имеет вид:

Найдём короткую запись для данной производящей функции.

Решение.

1 способ. Умножим на :

2 способ. Заметим, что:

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

Обратная задача

2. Дана производящая функция Найдите последовательность соответствующую данной производящей функции.

Решение.

1 способ.

Воспользуемся формулой (1)

Воспользуемся формулой:

Последовательность 1, 1, 1, …

3. Для какой последовательности является производящей функция:

а)

Решение.

Последовательность: 1, -1, 1, -1,…

б)

Воспользуемся результатами предыдущей задачи.

Последовательность: 1, 2, 3,…

2.6 Числа Фибоначчи и Люка

ньютон формула многочлены фибоначчи

Последовательность чисел Фибоначчи определяется соотношением, при . Ее члены 0, 1, 1, 2, 3, 5, 8,…,Выведем производящую функцию для этой последовательности.

Определяющее соотношение для последовательности означает, что ее производящая функция удовлетворяет соотношению

Рассмотрим отдельно числитель.

; ;

Рассмотрим отдельно знаменатель.

Решим полученное уравнение относительно переменной x и найдём неизвестные . Получим систему уравнений.

;

Тогда мы имеем следующие решения

и

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



Докажите, что числа Люка связаны с числами Фибоначчи соотношениями:

1.

2.

3.

4.

5.

Найд1м производящую функцию последовательности чисел Люка.

Определяющее соотношение для последовательности означает, что ее производящая функция

Рассмотрим производящую функцию

Рассмотрим отдельно числитель.

.

Рассмотрим отдельно знаменатель.

Решим полученное уравнение относительно переменной x и найдём неизвестные . Получим систему уравнений.

;

Тогда мы имеем следующие решения

и

Так как имеем две пары решении, то необходимо найти

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

1

3. Обобщённые биномиальные коэффициенты

3.1 Определение обобщённых биномиальных коэффициентов и их производящая функция

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

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

Дана производящая функция . Найдите последовательность соответствующую данной производящей функции.

Решение.

2 способ.

Воспользуемся формулой:

Из условия задачи следует, что

если n- четное число.

если n - нечётное число.

В итоге:

3). Для какой последовательности является производящей функция:

а)

2 способ. Воспользуемся формулой (2).

если n- четное число.

если n- нечётное число.

В итоге:

Последовательность 1, -1, 1, -1,…

б)

2 способ. Воспользуемся формулой (2).



Последовательность 1, 2, 3, 4,….

1. Докажем, что для всех неотрицательных чисел выполняется равенство:

а)

Доказательство.

б) Вычислите производящую функцию для последовательности где m - число неотрицательное,

n- натуральное.

Воспользуемся формулой (2).

2. Пусть- числа решения уравнения

.

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

а) Докажите равенство:

Покажем, что



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

То есть, коэффициент при равен ,

б) Найдите формулу для

Решение.

Воспользуемся формулой (2).

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

N -- это представление n в виде суммы положительных целых чисел, называемых частями.

Решение.

Рассмотрим функцию

Коэффициент при , -это число неотрицательных целых решения уравнения

где m, k - фиксированные натуральные числа.

Рассмотрим

Коэффициент при равен

То есть, число решений уравнения находится по формуле

3.3 Задача о размене

Сколькими способами можно разменять сумму в рублей, монетами достоинством 1 и 2 рубля? Эту задачу можно сформулировать иначе: сколько неотрицательных целых решений имеет уравнение

.

Рассмотрим функцию:

Коэффициент при -это число неотрицательных целых решения уравнения

.

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

И, например, рассчитаем сколькими способами можно разменять сумму в 100 рублей.

Ответ: 51 способ.

4. Другие виды производящих функций

4.1 Последовательности с двумя индексами

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

Треугольник Паскаля.

Треугольник Паскаля изображён ниже.

Элементы этого треугольника перечисляют пути, идущие из его вершины в соответствующую клетку. Пути имеют вид ломанных, состоящих из векторов единичной длины двух видов: идущих влево - вниз и идущих вправо - вниз.

Числа, стоящие в треугольнике Паскаля - биномиальные коэффициенты.

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

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

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

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

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

4.2 Многочлены Фибоначчи и Люка

Найдём производящую функцию последовательности многочленов Фибоначчи.

Определение. Многочлены Фибоначчизадаются при помощи начальных условий и рекуррентного соотношения

Вычислим многочлены Фибоначчи.

Найдите производящие функции последовательности многочленов Фибоначчи.

Найдём производящие функции последовательности многочленов Люка.

Многочлены Люка определяются равенствами

Вычислим многочлены чисел Люка.

Найдём производящие функции последовательности многочленов Люка.



4.3 Экспоненциальные производящие функции

Зафиксируем произвольную последовательность Каждой последовательности мы можем сопоставить производящую функцию,



определённую последовательностью Если в последовательности отсутствуют нулевые элементы, то такое сопоставление взаимно-однозначно. Мы пользовались обычными производящими функциями, отвечающими последовательности В зависимости от преследуемых целей пользу могут принести и другие последовательности. Чаще всего используется последовательность ..

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

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

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

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

Коэффициент произведения вычисляется по формуле:

Особое отличие экспоненциальных производящих функций от обычных наблюдается при интегрировании и дифференцировании. Интегрирование или дифференцирование экспоненциальной производящей функции приводит к сдвигу последовательности её коэффициентов без изменения их величин:

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

Теперь можно выписать экспоненциальную производящую функцию для треугольника Паскаля:



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

...