Решение рекуррентных соотношений. Т

Последовательность удовлетворяет следующему соотношению где - некоторые числа. При заданных значениях формула (1) полностью определяет последовательность; каждый ее элемент, начиная с к-го, является линейной комбинацией предыдущих к элементов с коэффициентами поэтому формулу (1) называют линейным рекуррентным соотношением к-го порядка. Если положить можно переписать в виде ИЛИ Решение линейных рекуррентных уравнений Поставим задачу - перейти от рекуррентного задания последовательности к формуле, выражающей зависимость общего члена последовательности хп от его номера п. Для решения этой задачи введем в рассмотрение: - производящую функцию последовательности - характеристический многочлен - многочлен Отметим следующую связь между многочленами: при. Докажем, что F(t) является дробно-рациональной функцией. Действительно, где коэффициенты Cm определяются по коэффициентам а^ и первым к членам последовательности Итак,) - многочлен степени не выше к- 1; поэтому F(t) = - правильная рациональная дробь. Дальнейший ход наших выкладок будет следующим: мы представим F(t) в виде суммы простейших дробей, запишем разложения простейших дробей по степеням переменной t, после чего по виду полученного ряда для F(t) будет ясен характер зависимости хп от п. Пусть характеристический многочлен /(А) имеет s различных (комплексных) корней: Aj кратности Г|, ..., Ха кратности rs: Как известно из алгебры, разложение правильной рациональной дроби со знаменателем g(t) на простейшие дроби имеет вид где некоторые константы. Применив биномиальное разложение, получим Таким образом, или, поскольку - многочлен от п степени (при фиксированном j)> где - некоторый многочлен степени не выше Мы доказали, что обший член последовательности, удовлетворяющей линейному рекуррентному соотношению fc-ro порядка, имеет вид где для число - корень кратности г, характеристического многочлена рекуррентного соотношения, Р*(я) - многочлен степени, не превосходящей г, - 1. Конкретный вид указанных многочленов определяется первыми к членами последовательности: В частности, если все корни характеристи- ческого многочлена - простые (т.е. кратности 1), то последовательность (ж„) представима в виде суммы геометрических прогрессий: где Ci - некоторые константы. Рассмотрим несколько примеров. Пример 1. Последовательность чисел Фибоначчи задается соотношениями Составим характеристическое уравнение: формула общего члена: Коэффициенты С\ и Cj определим из -начальных условий»: . Решив систему двухуравнений с двумя неизвестными, получим окончательный результат: Пример 2. Найдем все последовательности, удовлетворяющие условию Характеристическое уравнение А2 - 2А4- 1 =0 имеет двукратный корень: Au = 1, поэтому общий член последовательности имеет вид: где константы о и 6 определяются первыми двумя членами последовательности. Таким образом, (х„) - арифметическая прогрессия. Этот результат можно было предвидеть, заметив, что соотношение (3) является характеристическим для арифметической прогрессии: каждый член последовательности, начиная со второго, есть среднее арифметическое его соседних членов. ПримерЗ. Найдем последовательность (z„), задаваемую соотношениями Разложим характеристический многочлен на множители: Вид n-го члена последовательности:. Константы а, Ь, с найдем из системы уравнений Ответ: Упражнения Решение линейных рекуррентных уравнений Правило произведения 1. Из города А в город Б ведут 5 дорог, а из города Б в город В - 7 дорог. Сколько есть различных маршрутов из города А в В через Б? 2. В меню столовой 3 первых, 5 вторых и 3 третьих блюда. Сколькими способами можно выбрать обед из трех блюд (первое, второе и третье)? 3. Сколько есть двузначных чисел, не содержащих цифр 4. Сколько есть двузначных чисел, не содержащих цифр Номер автомашины состоит из трех букв латинского алфавита (содержащего 26 букв) и трех цифр. Сколько можно составить различных номеров автомашин? 6. У рояля 88 клавиш. Сколькими способами можно извлечь последовательно 6 звуков? 7. Сколько натуральных делителей имеет число 8. Сколько натуральных делителей имеет число 9. Сколько есть пятизначных чисел, 1) оканчивающихся двумя семерками? 2) начинающихся с двух одинаковых цифр? 3) в каждом из которых нет одинаковых цифр? 4) в каждом из которых соседние цифры различны? 5) делящихся на 4 и не содержащих цифр 6) в записи которых есть одинаковые цифры? 7) в записи которых есть хотя бы одна четная цифра? Решение линейных рекуррентных уравнений 10. Сколько есть перестановок цифр в которых 1) цифра 3 занимает третье место, а цифра 5 - пятое? 2) цифра 1 следует непосредственно за цифрой 0? 3) цифра 0 занимает одно из первых трех мест, а цифра 1 - одно из последних четырех мест? 4) цифра 0 занимает одно из первых пяти мест, а цифра 1 - одно из первых трех мест? 5) между цифрами 0 и 1 стоят ровно три цифры? 6) цифра 0 расположена левее цифры 1? 7) цифра 1 расположена между цифрами 0 и 2? 8) хотя бы одна из первых трех цифр делится на 3? 11. Сколькими способами можно рассадить за десятью партами 10 мальчиков и 10 девочек так, чтобы за каждой партой сидели а) мальчик слева, а девочка справа? б) мальчик и девочка? 12. Сколькими способами можно прочитать слово ПАРУС, двигаясь вправо или вниз по каждой из следующих таблиц? Сколькими способами можно расставить на шахматной доске 8 одинаковых ладей так, чтобы никакие две из них не били друг друга? 14. Сколькими способами можно расставить на шахматной доске 8 одинаковых ладей так, чтобы они били все поля? Сочетания 15. Вычислить: 16. Найти число подмножеств X множества обладающих следующими свойствами: 5) множество X состоит из трех четных и двух нечетных чисел; 17. На окружности последовательно отмечены точки Сколько существует 1) хорд с концами в отмеченных точках; 2) треугольников с вершинами в отмеченных точках; 3) выпуклых четырехугольников с вершинами в отмеченных точках; 4) треугольников с вершинами в отмеченных точках, не имеющих обших точек с прямой А2Ая; 5) треугольников с вершинами в отмеченных точках, имеющих общие точки с прямой AiA}? 18. На окружности отмечено п точек. Точки соединяются всевозможными хордами; известно, что никакие три из них не пересекаются в одной точке внутри круга. Найти: 1) число точек пересечения хорд внутри круга; 2) количество частей, на которые хорды делят круг. 19. На прямой I отмечено 8 точек, а на параллельной ей прямой m точек. Сколько существует 1) треугольников с вершинами в отмеченных точках; 2) выпуклых четырехугольников с вершинами в отмеченных точках? 20. Две команды играют в волейбол до 4 побед. Сколько существует разных вариантов изменения счета в игре по партиям? 21. Сколькими способами можно разложить 4 белых и 3 черных шара по 6 различным ящикам? 22. Решить предыдущую задачу при дополнительном условии: ни один яшик не должен быть пустым. 23. Сколькими способами можно разложить 20 одинаковых шаров по 5 различным яшикам так, чтобы 1) в каждом ящике оказалось не менее двух шаров; 2) в каждом ящике оказалось не более 5 шаров; 3) оказалось не более двух пустых яшиков? 24. Найти коэффициент при г100 в разложении многочлена Дан квадрат. Каждая его сторона разбита на п равных частей. Через точки деления проведены прямые, параллельные сторонам. Сколько существует 1) прямоугольников; 2) квадратов, ограниченных проведенными линиями? 26. В правлении банка 7 человек. Каково должна быть минимальное число замков от сейфа и как следует распределить ключи меж^у членами правления (каждый член правления может получить ключи от нескольких замков), чтобы любое большинство сейф могло открыть, а любое меньшинство - не могло? 27. Каким числом способов можно прочитать слово «абракадабра», двигаясь вправо или вниз по таблице (с. 76)? На клетчатой бумаге нарисован прямоугольник ABCD, стороны которого лежат на линиях сетки, причем длина отрезка AD в к раз больше длины отрезка АВ (к - натуральное число). Рассматриваются всевозможные пути, проходящие по линиям сетки и кратчайшим образом ведущие из А в С. Доказать, что среди этих путей в к раз больше тех, у которых первое звено лежит на AD, чем тех, у которых первое звено лежит на АВ. 29. Изучите поведение последовательности (о*), где ак = С* (при фиксированном п), с точки зрения возрастания-убывания. 30. Имеется карточная колода из 52 карт. Каким числом способов можно раздать по 13 карт четырем игрокам? Полиномиальная формула 31. Найти коэффициент при хк в разложении многочленов: Комбинаторные тождества 32. С помощью формулы бинома Ньютона Решение линейных рекуррентных уравнений доказать следующие тождества: 33. С помощью комбинаторных рассуждений доказать: Формула яключения-исключения 34. На кафедре лингвистики работают 13 человек, причем каждый из них знает хотя бы один иностранный язык. Десять человек знают английский язык, семеро немецкий, шестеро - французский. Пятеро знают английский и немецкий, четверо - английский и французский, трое - немецкий и французский. Сколько человек знают 1) все три языка; 2) ровно два языка; 3) только английский язык? 35. 1) Показать, что количество натуральных чисел, делящихся на п и не превосходящих положительного числа х, равно 2) Сколько есть чисел, не превосходящих и не делящихся ни на ни на, ни на 3) Сколько есть четырехзначных чисел, не делящихся ни на, ни на, ни на 4) Сколько есть чисел, не превосходящих и не делящихся ни на одно из чисел 5) Показать, что если п = 30т, то количество натуральных чисел, не превосходящих п и не делящихся ни на одно из чисел равно. 36. Пусть. Показать, что простых чисел в множестве не больше восьми. 37. На каждой стороне треугольника А ВС отмечено по п точек, разбивающих ее на п + 1 равных частей. Рассмотрим всевозможные треугольники с вершинами в отмеченных точках (по одной на каждой стороне). Сколько среди этих треугольников таких, у которых ни одна из сторон не параллельна стороне треугольника ABC? 38. Сколько существует б-значных номеров (первые цифры могут быть и нулями) с суммой цифр 27? 39. В кошельке лежит по 20 монет достоинством в рублей. Сколькими способами можно из этих 60 монет выбрать к монет (к ^ 60)? Задача о беспорядках и встречах 40. С помощью рекуррентных соотношений найти число беспорядков Dn для 42. Сколькими способами можно расставить на шахматной доске 8 одинаковых ладей так, чтобы никакие две из них не били друг друга и чтобы ни одна ладья не стояла на главной диагонали? 43. Сколькими способами можно раскрасить клетки шахматной доски 8 х 8 в 8 цветов так, чтобы клетки, имеющие обшую сторону, были бы окрашены в разные цвета и чтобы в каждом горизонтальном ряду встречались все 8 цветов? 44. Две колоды карт, содержащие по 52 карты, тщательно тасуются, после чего сравниваются карта за картой. Какова вероятность того, что не будет ни одной пары совпадающих карт? 45. Для числа перестановок п элементов с А: встречами Dn,k доказать тождества: Случайным образом выбирается перестановка чисел 1,2..., п. Пусть £ - количество элементов, остающихся на своих местах. Найти математическое ожидание и дисперсию случайной величины 47. Секретарше нужно отправить п различных писем по п различным адресам. Она подписывает конверты и случайным образом вкладывает письма в конверты. Сколько в среднем писем дойдет до своего адресата? Производящие функции Найти производящие функции следующих последовательностей: Пусть - последовательности, - соответствующие производящие функции. Выразить А(х) через В(х) при следующих соотношениях между последовательностями: Пусть an = С?Ък. Доказать, что bn = Рекуррентные соотношения 64. Последовательность (a„) удовлетворяет соотношению уравнение имеет два различных ненулевых корня х, и х2. Доказать, что имеет место тождество для некоторых С| и с2, однозначно определяемых Найти формулу общего члена последовательности: 66. Найти количество n-значных чисел, состоящих из цифр, в которых первая и последняя, а также любые две соседние цифры различны. 67. Сколько существует раскрасок вершин n-угольника, если соседние вершины должны быть разного цвета, а всего имеется к цветов? 68. Пусть n-й член последовательности задается формулой. Доказать, что для последовательности имеет место рекуррентное соотношение а, где 69. Найти а, если 70. Найти число двоичных последовательностей длины 11, не содержащих единиц ни в каких трех соседних позициях. 71. Найти обшие решения рекуррентных соотношений: 72. Найти ап по рекуррентным соотношениям и начальным условиям: 1) Каждая точка пересечения хорд однозначно задается (неупорядоченной) четверкой точек - концов этих хорд. Будем последовательно проводить хорды. Пусть kt - число точек пересечения t"-й хорды с ранее проведенными. Этими точками «-я хорда делится на fc, + 1 отрезков, каждый из которых, в свою очередь, делит одну «старую» часть разбиения круга на две «новые». Изначально имелась одна часть. После проведения всех N хорд количество частей равно Осталось заметить, что N = а обшее количество точек пересечения хорд Решение линейных рекуррентных уравнений (согласно первому пункту данной задачи). Интересен ответ к задаче при Он "гаков: Физик из известного анекдота на основании первых пяти результатов заявил бы, что общий ответ - 2я"а число 31 возникло в результате погрешности эксперимента. . Составьте отношение. Подсчитайте двумя способами сумму мощностей всех подмножеств п-элементного множества. 3 при нечетном при четном п. . Решение. Пусть U - множество последовательностей (составленных из шести неотрицательных целых чисел с суммой 27; а для каждого i множество Ai С U состоит из таких последовательностей, в которых Для решения -Заметим,что | а пересечение трех и большего числа множеств Ai пусто. 41. Используйте оценку остаточного члена ряда из признака Лейбница. Указание. Обозначим через о„ число двоичных последовательностей длины п, удовлетворяющих условию задачи. Найдите начальные условия и рекуррентное соотношение для последовательности (оп).

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

Введение

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

Идея производящих функций достаточно проста: сопоставим некоторой последовательности - дискретному объекту, степенной ряд g 0 + g 1 z + g 2 z 2 +… + g n z n +… - объект непрерывный, тем самым мы подключаем к решению задачи целый арсенал средств математического анализа. Обычно говорят, последовательность генерируется, порождается производящей функцией. Важно понимать, что это символьная конструкция, то есть вместо символа z может быть любой объект, для которого определены операции сложения и умножения.

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

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

В 50-х годах XVIII века Эйлер решал следующую задачу: какие грузы можно взвесить с помощью гирь в 2 0 , 2 1 , 2 2 ,..., 2 n грамм и сколькими способами? При решении этой задачи он использовал никому неизвестный на то время метод производящих функций , которому и посвящена данная статья. К этой задаче мы вернёмся немного позже, после того как разберёмся более подробно с устройством производящих функций.

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

Изучение этого мощного механизма позволяющего решать многие задачи, мы начнём с простенькой задачи: сколькими способами можно расположить в линию чёрные и белые шары, общее количество которых равно n?

Обозначим белый шар символом ○, чёрный - ●, T n - искомое количество расположений шаров. Символом Ø - обозначим нулевое количество шаров. Как и любое решение комбинаторной задачи начнём с тривиальных случаев:

Если n=1, то очевидно имеется 2 способа - взять либо белый шар ○, либо взять чёрный шар ●, таким образом, T 2 = 2.

Если n=2, то имеется 4 способа расположений: ○○, ○●, ●○, ●●.

Рассмотрим случай для n=3. Мы можем начать белым шаром и продолжить 4-мя комбинациями, описанными выше ○○○, ○○●, ○●○, ○●●, или же мы можем начать чёрным шаром и аналогично продолжить 4-мя шарами ●○○, ●○●, ●●○, ●●●.

В итоге количество шаров удвоилось, то есть T 3 = 2T 2 . Аналогично T 4 = 2T 3 , то есть, обобщая для всех n, получаем рекуррентное уравнение T n = 2T n-1 которое и является решением для данной задачи. Решение такого уравнения можно легко угадать - T n = 2 n (так как 2⋅2 n-1 = 2 n).

А что если у нас плохо с угадыванием? И что делать, если уравнение будет сложнее? А вообще причём здесь производящие функции?

«Просуммируем» все возможные комбинации расположений шаров:

G = Ø + ○ + ● + ○○ + ○● + ●○ + ●● + ○○○ + ○○● + ○●○ + ○●● + ●○○ + ●○● + ●●○ + ●●● +…

Вопрос о допустимости такой нелепой на первый взгляд суммы опустим. Будем складывать и умножать последовательности шаров. Со сложением всё понятно, но что значит умножить одну последовательность шаров на другую? Перемножив ○● на ●○ мы получим не что иное как ○●●○. Заметим, однако, что произведение шаров в отличие от произведения чисел не является коммутативным, так как ○●⋅●○ ≠ ●○⋅○●. Символ Ø - в произведении играет роль мультипликативной единицы, то есть Ø ⋅ ○○● = ○○● ⋅ Ø = ○○● и коммутирует с любой последовательностью шаров.

Производя с рядом G последовательность манипуляций, а именно вынося за скобки левый белый и чёрный шары

G = Ø + ○ (Ø + ○ + ● + ○○ + ○● + ●○ + ●● + ...) + ● (Ø + ○ + ● + ○○ + ○● + ●○ + ●● + ...) = Ø + ○G +●G

Получим уравнение G = Ø + ○G +●G.

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

Учитывая формулу суммы геометрической прогрессии , имеем

В этой сумме так же учтены все возможные варианты разбиения в точности по одному разу. Далее воспользуемся формулой бинома Ньютона: , где - число сочетаний из n по k. Тогда с учетом этого имеем:

Коэффициент при ○ k ● n-k равный числу сочетаний из n по k, показывает общее количество последовательностей из n шаров содержащих ○ шары в количеств k штук и ● шары в количестве n-k штук. Таким образом, общее количество расположений n шаров есть сумма по всем возможным значениям k. Как известно .

Эту формулу можно было получить непосредственно из заменив Ø на 1, а ○ и ● на z (в виду их равнозначности). Получим то есть коэффициент при z n равен 2 n .

Обсуждение метода

Так что же позволяет данному методу быть работоспособным при решении различных задач?

Алгоритм решения задачи можно описать примерно следующим образом: рассматривается некоторая бесконечная сумма, которая в конечном итоге представляет собой формальный степенной ряд G(z) = g 0 + g 1 z + g 2 z 2 +… + g n z n +… причем коэффициенты g k (не заданные в явном виде) - являются ключом к решению исходной задачи. То, что ряд является формальным, говорит о том, что z - является просто символом, то есть вместо него может быть любой объект: число, шар, кость домино и т.д. В отличие от степенных рядов в анализе формальным степенным рядам не придается числовых значений и, соответственно, нет смысла говорить о сходимости таких рядов для числовых аргументов.

G(z) = g 0 + g 1 z + g 2 z 2 +… + g n z n +… - называется производящей функцией для последовательности . Заметим, однако, что хотя G(z) - функция, это всё таки формальная запись, то есть мы не можем подставить вместо z любое значение z = z 0 , за исключением z = 0, так как G(0) = g 0 .

Затем производя различные преобразования с бесконечной суммой G(z) мы преобразуем её к замкнутому (компактному) виду. То есть у производящей функции есть 2 представления: бесконечное и замкнутое и, как правило, для решения задачи необходимо бесконечный вид преобразовать к замкнутому, а затем замкнутый вид разложить в степенной ряд, и тем самым получить значения для коэффициентов g k .

Отвечая на поставленный вначале вопрос можно сказать так: успех данного метода связан с возможностью записать производящую функцию в замкнутом виде. Так, например, производящая функция для последовательности <1, 1, 1, ..., 1> в бесконечном виде представляется как 1 + x + x 2 + x 3 + ..., а в замкнутом .

А теперь вооружившись знаниями, вернемся к задаче, которую решал Эйлер.

Итак, задача звучит следующим образом: какие грузы можно взвесить с помощью гирь в 2 0 , 2 1 , 2 2 ,..., 2 n грамм и сколькими способам?

Я не знаю, как долго Эйлер придумывал решение для этой задачи, но оно поражает своей неожиданностью. Посудите сами. Эйлер рассматривает произведение G(z) = (1+z)(1+z 2)(1+z 4)… которое после раскрытия скобок представляется в виде бесконечного ряда G(z) = 1 + g 1 z + g 2 z 2 + g 3 z 3 +….

Что же из себя представляют коэффициенты g k ? Каждый g k - это коэффициент при z k , а z k - получается как произведение каких-то одночленов z 2m , то есть g k - это в точности число разных представлений числа k в виде суммы некоторых из чисел 1, 2, 2 2 , 2 3 ,..., 2 m ,…. Другими словами g k - это число способов взвешивания груза в k грамм заданными гирями. Как раз то, что мы искали!

Следующий шаг Эйлера поражает не менее предыдущего. Он умножает обе части равенства на (1-z).

(1-z)G(z) = (1-z)(1+z)(1+z 2)(1+z 4)(1+z 8)…
(1-z)G(z) = (1-z2)(1+z 2)(1+z 4)(1+z 8)…
(1-z)G(z) = (1-z 4)(1+z 4)(1+z 8)…
(1-z)G(z) = 1

С одной стороны G(z) = 1 + g 1 z + g 2 z 2 + g 3 z 3 +… с другой стороны мы только что получили . Последнее равенство есть не что иное, как сумма геометрической прогрессии, которая равна . Сопоставляя эти два равенства, получаем g 1 = g 2 = g 3 =… = 1, то есть любой груз в k грамм можно взвесить гирями в 1, 2, 4, 8,… грамм притом единственным способом.

Решение рекуррентных соотношений

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

Начнем со всеми знакомой последовательностью чисел Фибоначчи. Каждый из нас знает её рекуррентный вид: F 0 = 0, F 1 = 1, F n = F n-1 + F n-2 , n ≥ 2. Однако не каждый знает вид этой формулы в замкнутом виде и это не удивительно, ведь она содержит иррациональное число(«золотое сечение») в своём составе.

Итак, имеем

F 0 = 0,
F 1 = 1,
F n = F n-1 + F n-2 , n ≥ 2

Умножим каждую строчку на z 0 , z 1 , ..., z n соответственно:

Z 0 ⋅ F 0 = 0,
z 1 ⋅ F 1 = z,
z n ⋅ F n = z n ⋅ F n-1 + z n ⋅ F n-2 , n ≥ 2

Просуммируем эти равенства:

Обозначим левую часть

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

Имеем следующее уравнение G(z) = z + z G(z) + z 2 G(z) решая которое относительно G(z) находим

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

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

Следующим шагом является нахождение коэффициентов a и b. Для этого умножим дроби на общий знаменатель:

Подставляя в это уравнение значение z = z 1 и z = z 2 , находим

Напоследок немного преобразуем выражение для производящей функции

Теперь каждая из дробей представляет собой сумму геометрической прогрессии.

По формуле находим

Но ведь мы искали G(z) в виде . Отсюда делаем вывод, что

Эту формулу можно переписать в другом виде не используя «золотое сечение»:

Что достаточно трудно было ожидать, учитывая красивое рекуррентное уравнение.

Давайте запишем общий алгоритм решения рекуррентных уравнений, используя производящие функции. Он записывается в 4 шага:

Причина, по которой данный метод работает, заключается в том, что единая функция G(z) представляет всю последовательность g n и это представление допускает многие преобразования.

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

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

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

Пусть G = G(z) – производящая функция. Производной этой функции называется функция . Дифференцирование, очевидно, линейная операция, поэтому для того, чтобы понять, как оно действует на производящих функциях, достаточно посмотреть на его действие, на степенях переменной. Имеем

Тем самым, действие дифференцирования на произвольной производящей функции
G (z) = g 0 + g 1 z + g 2 z 2 + g 3 z 3 +… дает G΄(z) = g 1 + 2g 2 z + 3g 3 z 2 + 4g 4 z 3 +….

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

Операция дифференцирования обратна операции интегрирования:

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

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

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

G 0 = 1,
g 1 = 1,
g n = g n-1 + 2g n-2 + (-1) n

Будем следовать вышеописанному алгоритму. Первое условие алгоритма выполнено. Умножим обе части всех равенств на z в соответствующей степени и просуммируем:

Z 0 ⋅ g 0 = 1,
z 1 ⋅ g 1 = z,
z n ⋅ g n = z n ⋅ g n-1 + 2z n ⋅ g n-2 + (-1) n ⋅ z n

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

Попытаемся выразить правую часть через G(z). Рассмотрим каждое слагаемое:

Составляем уравнение:

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

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

Собственно всё. Раскладываем каждое слагаемое в степенной ряд и получаем ответ:

С одной стороны мы искали G(z) в виде , с другой стороны .

Значит, .

Вместо заключения

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

Возводя в квадрат обе части этого равенства получим

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

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

Рекуррентным соотношением , рекуррентным уравнением или рекуррентной формулой называется соотношение вида , которое позволяет вычислять все члены последовательности
, если заданы ее первые k членов.

1. Формула
задает арифметическую прогрессию.

2. Формула
определяет геометрическую прогрессию.

3. Формула
задает последовательность чисел Фибоначчи .

В случае, когда рекуррентное соотношение линейно и однородно, т. е. выполняется соотношение вида

(p =const), последовательность
называется возвратной . Многочлен

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

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

Описание общего уравнения соотношения (1) имеет аналоги с описанием решения обыкновенного дифференциального уравнения с постоянными коэффициентами.

Теорема 1. 1. Пусть - корень характеристического многочлена (2). Тогда последовательность
, где c – произвольная константа, удовлетворяет соотношению (1).

2. Если
- простые корни характеристического многочлена (2), то общее решение рекуррентного соотношения (1) имеет вид , где
- произвольные константы.

3. Если - корень кратности
характеристического многочлена (2), то общее решение рекуррентного соотношения (1) имеет вид
, где - произвольные константы.

Зная общее решение рекуррентного уравнения (1), по начальным условиям,
можно найти неопределенные постоянные и те самым получить решение уравнения (1) с данными начальными условиями.

Пример 2. Найти последовательность
, удовлетворяющую рекуррентному соотношению
и начальным условиям
.

Корням характеристического многочлена
являются числа
. Следовательно, по теореме 3.1. общее решение имеет вид
. Используя начальные условия, получаем систему

решая которую, находим
и
. Таким образом,
.

Рассмотрим неоднородное линейное рекуррентное уравнение

Пусть
- общее решение однородного уравнения (1), а
- частное (конкретное) решение неоднородного уравнения (3). Тогда последовательность
образует общее решение уравнения (3), и тем самым справедлива.

Теорема 2. Общее решение неоднородного линейного рекуррентного уравнения представляется в виде суммы общего решения соответствующего однородного линейного рекуррентного уравнения и некоторого частного решения неоднородного уравнения.

Таким образом, в силу теоремы 1. задача нахождения общего решения рекуррентного уравнения (3) сводится к нахождению некоторого частного решения.

В отдельных случаях имеются общие рецепты нахождения общего решения.

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

Пусть
- многочлен степени r от переменной n , и число 1 не является характеристическим корнем. Тогда и частное решение следует искать в виде
. Подставляя многочлены в формулу (3), получаем

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

Пример. Найти решение уравнения

(4)

с начальным условием
.

Рассмотрим характеристический многочлен
. Так как
и правая часть
уравнения (3) равна n +1, то частное решение будем искать в виде
. Подставляя в уравнение (4), получаем . Приравнивая коэффициенты в левой и правой частях последнего равенства, получаем систему

откуда находим
. Таким образом, частное решение уравнения (4) имеет вид
. По теореме 3.1. общее решение однородного уравнения
задается формулой
, и по теореме 3.2. получаем общее решение уравнения (4):
. Из начального условия
находим
, т. е. . Таким образом,
.

Аннотация: Размещения без повторений. Перестановки. Сочетания. Рекуррентные соотношения. Другой метод доказательства. Процесс последовательных разбиений. Задача: "Затруднение мажордома".

Размещения без повторений

Имеется различных предметов. Сколько из них можно составить -расстановок? При этом две расстановки считаются различными, если они либо отличаются друг от друга хотя бы одним элементом, либо состоят из одних и тех же элементов, но расположенных в разном порядке. Такие расстановки называют размещениями без повторений , а их число обозначают . При составлении -размещений без повторений из предметов нам надо сделать выборов. На первом шагу можно выбрать любой из имеющихся предметов. Если этот выбор уже сделан, то на втором шагу приходится выбирать из оставшихся предметов. На - м шагу предметов. Поэтому по правилу произведения получаем, что число -размещений без повторения из предметов выражается следующим образом:

Перестановки

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

Сочетания

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

Формула для числа сочетаний получается из формулы для числа размещений. В самом деле, составим сначала все - сочетания из элементов, а потом переставим входящие в каждое сочетание элементы всеми возможными способами. При этом получается, что все -размещения из элементов, причем каждое только по одному разу. Но из каждого - сочетания можно сделать ! перестановок, а число этих сочетаний равно . Значит справедлива формула

Из этой формулы находим, что

Рекуррентные соотношения

При решении многих комбинаторных задач пользуются методом сведения данной задачи к задаче, касающейся меньшего числа предметов. Метод сведения к аналогичной задаче для меньшего числа предметов называется методом рекуррентных соотношений (от латинского "recurrere" - "возвращаться").

Понятие рекуррентных соотношений проиллюстрируем классической проблемой, которая была поставлена около 1202 года Леонардо из Пизы, известным как Фибоначчи. Важность чисел Фибоначчи для анализа комбинаторных алгоритмов делает этот пример весьма подходящим.

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

Пусть - число пар кроликов в популяции по прошествии месяцев, и пусть эта популяция состоит из пар приплода и "старых" пар, то есть . Таким образом, в очередном месяце произойдут следующие события: . Старая популяция в -й момент увеличится на число родившихся в момент времени . . Каждая старая пара в момент времени производит пару приплода в момент времени . В последующий месяц эта картина повторяется:

Объединяя эти равенства, получим следующее рекуррентное соотношение:

(7.1)

Выбор начальных условий для последовательности чисел Фибоначчи не важен; существенное свойство этой последовательности определяется рекуррентным соотношением. Будем предполагать (иногда ).

Рассмотрим эту задачу немного иначе .

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

Из условия задачи следует, что через месяц будет две пары кроликов. Через два месяца приплод даст только первая пара кроликов, и получится 3 пары. А еще через месяц приплод дадут и исходная пара кроликов, и пара кроликов, появившаяся два месяца тому назад. Поэтому всего будет 5 пар кроликов. Обозначим через количество пар кроликов по истечении месяцев с начала года. Ясно, что через месяцев будут эти пар и еще столько новорожденных пар кроликов, сколько было в конце месяца , то есть еще пар кроликов. Иными словами, имеет место рекуррентное соотношение

(7.2)

Так как, по условию, и , то последовательно находим

В частности, .

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

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

Чтобы установить эту связь , возьмем любую такую последовательность и сопоставим ей пару кроликов по следующему правилу: единицам соответствуют месяцы появления на свет одной из пар "предков" данной пары (включая и исходную), а нулями - все остальные месяцы. Например, последовательность 010010100010 устанавливает такую "генеалогию": сама пара появилась в конце 11-го месяца, ее родители - в конце 7-го месяца, "дед" - в конце 5-го месяца и "прадед" - в конце второго месяца. Исходная пара кроликов тогда зашифровывается последовательностью 000000000000.

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

Установленная связь показывает, что число -последовательностей, обладающих указанным свойством, равно .

Докажем теперь, что

(7.3)

Где , если нечетно, и , если четно. Иными словами, - целая часть числа (в дальнейшем будем обозначать целую часть числа через ; таким образом, ).

В самом деле, - это число всех - последовательностей из 0 и 1, в которых никакие две единицы не стоят рядом. Число же таких последовательностей, в которые входит ровно единиц и нулей, равно . Так как при этом должно выполняться

Рекуррентным соотношением (уравнением, рекуррентной формулой) называется соотношение вида

которое позволяет вычислить все члены последовательности a 0 ,a 1 , a 2 ,.., если заданы её первыеk членов.

k – порядок рекуррентного уравнения.

Примеры . 1)a n +1 = a n + d - арифметическая прогрессия.

2) a n +1 = q ∙ a n - геометрическая прогрессия.

3) a n +2 = a n + a n +1 - последовательность чисел Фибоначчи.

1.4.2. Решение линейного однородного рекуррентного уравнения

Вслучае, когда рекуррентное уравнение линейно и однородно, то есть выполняется соотношение вида

Последовательность a 0 , a 1 , a 2 ,.., удовлетворяющая данному уравнению называетсявозвратной .

Многочлен

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

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

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

Теорема 1 . Пусть - корень характеристического многочлена (2), тогда последовательность
, гдеc – производная константа, удовлетворяет уравнению (1).

Теорема 2 . Если
- простые корни характеристического многочлена (2), то общее решение рекуррентного уравнения (1) имеет вид:

где c 1 ,c 2 ,..,c k – произвольные константы.

Теорема 3 . Если - корень кратности (i = 1,2,..,s ) характеристического многочлена (2), то общее решение рекуррентного уравнения (1) имеет вид:

где c ij – произвольные константы.

Зная общее решение рекуррентного уравнения (1), по начальным условиям a 0 ,a 1 ,..,a k -1 , можно найти неопределенные постоянныеc ij , и тем самым получить частное уравнении (1) с данными условиями.

Пример . Найти последовательность {a n }, удовлетворяющую рекуррентному уравнению

Характеристический многочлен

1 (2).4.3. Решение линейного неоднородного рекуррентного уравнения

Рассмотрим линейное неоднородное рекуррентное уравнение

a n+k + p 1 a n+k-1 + … + p k a n = f(n), (n = 0, 1, 2,…) (3)

Пусть {b n } – общее решение однородного уравнения (1). {c n } – частное (конкретное) решение неоднородного уравнения (3).

Тогда последовательность {b n +c n } образует общее решение уравнения (3). Таким образом, справедлива теорема.

Теорема 4 . Общее решение линейного неоднородного рекуррентного уравнения представляется в виде суммы общего решения соответствующего линейного однородного рекуррентного уравнения и некоторого частного решении неоднородного уравнения.

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

1) Если f (n ) = β n , (гдеβ не является корнем характеристического уравнения), то частное решение следует искать в видеc n = C β n . Тогда, подставляя его в (3), получаем:

В результате, частное решение задаётся формулой

2) Пусть f (n ) –многочлен степениr от переменнойn , и число 1 не является характеристическим корнем. Тогда и частное решение следует искать в виде

Подставляя c n в (3) вместоa n , получаем

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

Пример . Найти решение рекуррентного уравнения

с начальным условием .

Решение. Рассмотрим характеристический многочлен данного рекуррентного уравнения

Его корень . Тогда по теореме 1 общее решение соответствующего однородного рекуррентного уравнения задаётся формулой , где – произвольная константа.

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