Рекуррентные соотношения и производящие функции: Производящие функции — туда и обратно / Хабр

Содержание

Конкретная математика. Основание информатики

Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики: Пер. с англ. —М.: Мир, 1998. —703 с.

Название этой оригинальной как по содержанию, так и по форме книги знаменитых американских математиков можно расшифровать как КОНтинуальная и дисКРЕТНАЯ математика. Прообразом книги послужил раздел «Математическое введение» первого тома фундаментальной монографии Д. Кнута «Искусство программирования для ЭВМ» (М.: Мир, 1976). Ее назначение — дать читателю технику оперирования с дискретными объектами, аналогичную технике для непрерывных объектов. Название книги можно понимать и буквально — обучение общим методам ведется на многочисленных конкретных примерах и упражнениях разной степени сложности.

Все упражнения снабжены ответами.

При переводе на русский язык учтены исправления авторов 1998 года.

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

От Фибоначчи до Эрдёша
Предисловие
К русскому изданию
Значения обозначений
1. Возвратные задачи
1.2 ЗАДАЧА О РАЗРЕЗАНИИ ПИЦЦЫ
1.3 ЗАДАЧА ИОСИФА ФЛАВИЯ
Упражнения
Контрольные работы
2. Исчисление сумм
2.2 СУММЫ И РЕКУРРЕНТНОСТИ
2.3 ПРЕОБРАЗОВАНИЕ СУММ
2.4 КРАТНЫЕ СУММЫ
2.5 ОБЩИЕ МЕТОДЫ СУММИРОВАНИЯ
2.6. ИСЧИСЛЕНИЕ КОНЕЧНОГО И БЕСКОНЕЧНОГО
2.7 БЕСКОНЕЧНЫЕ СУММЫ
Упражнения
3. Целочисленные функции
3.2 ПОЛ/ПОТОЛОК: ПРИМЕНЕНИЯ
3.3 ПОЛ/ПОТОЛОК: РЕКУРРЕНТНОСТИ

3.4 «MOD»: БИНАРНАЯ ОПЕРАЦИЯ
3.

5 ПОЛ/ПОТОЛОК: СУММЫ
Упражнения
4. Элементы теории чисел
4.2 ПРОСТЫЕ ЧИСЛА
4.3 ПРОСТЫЕ ПРИМЕРЫ
4.4 ФАКТОРИАЛЬНЫЕ ФАКТЫ
4.5 ВЗАИМНАЯ ПРОСТОТА
4.6 ОТНОШЕНИЕ СРАВНИМОСТИ
4.7 НЕЗАВИСИМЫЕ ОСТАТКИ
4.8 ДОПОЛНИТЕЛЬНЫЕ ПРИМЕРЫ
4.9 ФИ- И МЮ-ФУНКЦИИ
Упражнения
5. Биномиальные коэффициенты
5.2 НЕОБХОДИМЫЕ НАВЫКИ
5.3 СПЕЦИАЛЬНЫЕ ПРИЕМЫ
5.4 ПРОИЗВОДЯЩИЕ ФУНКЦИИ
5.5 ГИПЕРГЕОМЕТРИЧЕСКИЕ ФУНКЦИИ
5.6 ГИПЕРГЕОМЕТРИЧЕСКИЕ ПРЕОБРАЗОВАНИЯ
5.7 ЧАСТИЧНЫЕ ГИПЕРГЕОМЕТРИЧЕСКИЕ СУММЫ
5.8 МЕХАНИЧЕСКОЕ СУММИРОВАНИЕ
Упражнения
6. Специальные числа
6.2 ЧИСЛА ЭЙЛЕРА
6.3 ГАРМОНИЧЕСКИЕ ЧИСЛА
6.4 ГАРМОНИЧЕСКОЕ СУММИРОВАНИЕ
6.5 ЧИСЛА БЕРНУЛЛИ
6.6 ЧИСЛА ФИБОНАЧЧИ
6.7 КОНТИНУАНТЫ
Упражнения
7. Производящие функции
7.2 ОСНОВНЫЕ МАНЕВРЫ
7.3 РЕШЕНИЕ РЕКУРРЕНТНЫХ СООТНОШЕНИЙ
7.4 СПЕЦИАЛЬНЫЕ ПРОИЗВОДЯЩИЕ ФУНКЦИИ
7.5 СВЕРТКИ
7.6 ЭКСПОНЕНЦИАЛЬНЫЕ ПРОИЗВОДЯЩИЕ ФУНКЦИИ
7.7 ПРОИЗВОДЯЩИЕ ФУНКЦИИ ДИРИХЛЕ
Упражнения
8.

Дискретная вероятность
8.2 МАТЕМАТИЧЕСКОЕ ОЖИДАНИЕ И ДИСПЕРСИЯ
8.3 ПРОИЗВОДЯЩИЕ ФУНКЦИИ СЛУЧАЙНЫХ ВЕЛИЧИН
8.4 БРОСАНИЕ МОНЕТЫ
8.5 ХЕШИРОВАНИЕ
Упражнения
9. Асимптотика
9.1 ИЕРАРХИЯ
9.2 СИМВОЛ «О»
9.3 ОПЕРАЦИИ С «О»
9.4 ДВА АСИМПТОТИЧЕСКИХ ПРИЕМА
9.5 ФОРМУЛА СУММИРОВАНИЯ ЭЙЛЕРА
9.6 ЗАВЕРШАЮЩЕЕ СУММИРОВАНИЕ
Упражнения
А. Ответы к упражнениям

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

Рассмотрим последовательность элементов , первые элементов которой известны.

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

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

Например, рекуррентное соотношение , , задает Последовательность чисел Фибоначчи: 1, 1, 2, 3, 5, 8,…

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

Рассмотрим последовательность элементов . — известные начальные значения последовательности элементов, удовлетворяющих линейному неоднородному рекуррентному соотношению (1):

, (1)

— известные действительные числа.

Тогда (2) – линейное однородное рекуррентное соотношение, соответствующее (1):

. (2)

Определение. Характеристическим Уравнением, соответствующим (2), называется уравнение вида

. (3)

Корни уравнения (3) называются характеристическими числами рекуррентного соотношения (1).

Теорема 13.1. (О структуре общего решения линейного неоднородного рекуррентного соотношения (1)). Пусть общее решение линейного однородного рекуррентного соотношения (2), — Любое частное решение линейного неоднородного рекуррентного соотношения (1). Тогда — общее решение линейного неоднородного рекуррентного соотношения (1).

Теорема 13.2. (О структуре общего решения линейного однородного рекуррентного соотношения

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

Общее решение рекуррентного соотношения (2) при и действительных корнях уравнения (3) и имеет вид

при ,

при =.

Пример. Выведем формулу Бине для вычисления последовательности чисел Фибоначчи.

Решение. ,

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

Составим характеристическое уравнение и найдем характеристические числа и . Характеристическое уравнение имеет два различных корня кратности 1, значит, . Тогда общее решение , где и произвольные постоянные (, ). Используем заданные значения , составим систему из двух уравнений с двумя неизвестными:

Решением системы является пара чисел и . Таким образом, .□

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

Замечание. Часто рассматривается последовательность .

Например, для последовательности чисел Фибоначчи 0, 1, 1, 2, 3, 5, … рекуррентное соотношение записывается в виде , .

Задачи и упражнения.

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

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

13.3. Составьте рекуррентное соотношение последовательности квадратов натуральных чисел.

14. Понятие производящей функции.

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

. (1)

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

. (2)

Формально составим функциональный ряд, используя элементы (1) и (2):

. (3)

Будем считать ряд (3) сходящимся абсолютно на Или в некоторой области комплексной плоскости. Функция Является суммой ряда (3).

Определение. Сумма ряда (3) называется Производящей функцией для заданной последовательности чисел (1) по заданной последовательности функций (2).

Чаще других используются степенные функции Или . Поэтому ряд (3), как правило, является степенным.

Например. Положим в формуле бинома Ньютона . Тогда

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

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

Решение. Используем последовательность функций действительной переменной Умножим рекуррентное соотношение на и просуммируем по :

. (4)

По допущению все ряды абсолютно сходятся на R.

Подставив суммы в (4), получим , тогда .□

Задачи и упражнения.

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

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

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

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

< Предыдущая

генерирующих функций | Brilliant Math & Science Wiki

Содержание

Обычные производящие функции
Решение однородных линейных рекуррентных соотношений
Решение неоднородных линейных рекуррентных соотношений
Увеличение и уменьшение показателей производящей функции 9n\) без придания вообще никакого значения $x$ является идеей производящей функции. Производящая функция кодирует количество объектов с помощью формальных степенных рядов, которые представляют собой полиномы с (возможно) бесконечным числом членов (целых степеней).

Примечание. Термин «формальный» используется потому, что это алгебраическое, а не аналитическое понятие.
В приведенном выше примере мы могли бы просто подсчитать количество способов получения $ 10 $ путем проверки. Однако производящие функции невероятно полезны, если полиномы могут быть выражены в более компактной форме (например, с использованием суммы геометрического ряда), а затем умножение может привести к сокращению и упрощению вычислений. 92 \), следовательно, мы можем вычислить его напрямую, не считая каждого члена в отдельности. $_\квадрат$
Сколько решений в целых неотрицательных числах имеет уравнение $a + b + c = 20$?
Сначала мы рассмотрим более общий вопрос о нахождении числа решений в неотрицательных целых числах уравнения $a + b + c = n $. Поскольку значение $a$ может быть любым неотрицательным целым числом $0,1,2,3, \ldots, i , \ldots $ (см. примечание ниже), мы можем представить это как производящую функцию 9я + \cdots. \]
Следовательно, при $n=20 $ ответ равен $ { 22 \выбрать 2 } $. Это согласуется с тем, что мы знаем из метода звезд и полос. $_\квадрат$
Примечание. Может показаться запутанным, почему мы допускаем, что $a$ может быть любым неотрицательным целым числом, даже большим, чем $n$, что явно не приведет к решению. Подумайте, что произойдет, если мы допустим $a = n+1$ или $a = n+2$ или любое большее целое число: в конечном произведении полиномов показатели степени этих членов будут больше, чем $n ,$, поэтому они не будут вносить вклад в нужный нам член, который имеет показатель степени $n.$
У Коди есть 4 вида луковиц:
- Количество луковиц $\color{Purple}\text{purple}$ может быть любым неотрицательным целым числом.
- Количество луковиц $\color{Green}\text{green}$ кратно 2.
- Количество луковиц $\color{Red}\text{red}$ кратно 3.
- Количество луковиц $\color{Blue}\text{blue}$ кратно 5.
Если у Коди 23 луковицы, сколько может быть различных распределений цветов?
Вопрос ниже можно решить звездочками и полосками, но это утомительно. Мы можем решить ее, используя производящие функции.
Найдите количество неотрицательных целых решений уравнения
\[ 3x +y + z = 24.\]
Попробуйте также:
Есть $10$ $ \mathrm{\color{red {красный}}$ шары, $10$ $\mathrm{\color{синий}}{синий}}$ шары и $10$ $ \ mathrm{\color{зеленый} {зеленый} }}$ мячи.
Сколькими способами можно выбрать $16$ шаров так, чтобы было хотя бы по одному шару каждого цвета? 9{\infty}\) — это способ выражения $c_n$ через $k$ предыдущих членов последовательности для некоторого положительного целого числа $k.$. Однородное линейное рекуррентное отношение — это отношение form $c_n + q_1c_{n-1} + q_2c_{n-2} + \cdots +q_kc_{n-k} = 0. $ Это линейно, потому что каждый член имеет только один моном вида $c_i$ и он однороден, потому что правая часть равна 0. Если бы правая часть была ненулевой функцией $n,$, то она была бы неоднородной. Чтобы полностью решить рекуррентное соотношение, нам нужны начальные значения для первых $k$ членов, где это $k$ такое же, как и в определении. 9d},\]
, где у нас есть $j+1$ начальные члены $c_0,c_1,\ldots,c_k$, а $m_i$ определены как
\[\begin{ массив}{л} m_0 = c_0\\ m_1 = c_1 + q_1c_0\\ m_2 = c_2 + q_1c_1 + q_2c_0. \end{array}\]
Мы можем использовать это, чтобы явно найти $c_k$, найдя корни знаменателя и разложив рациональную функцию на частные дроби. Мы можем найти коэффициент при $c_k$, применяя теорему отрицательного бинома к каждому члену. Таким образом, мы можем сделать следующий вывод: 9п.\]
Константы $a_{1,1}, a_{1,2}, \ldots, a_{j,m_j}$ выбраны так, чтобы удовлетворять начальным условиям.
Обратите внимание, что общее количество этих констант равно $k,$, поэтому нам нужны $k$ начальных значений. {n+1} \] 92}. \ _\квадрат\]
64 66 69 72
Есть 30 следующих шаров:
- 5 одинаковых белых шаров
- 10 одинаковых черных шаров
- 15 одинаковых красных шаров.
Сколькими способами можно разделить эти шары на 2 ящика A и B так, чтобы в каждом ящике было по 15 шаров?
У вас есть 10 различных пустых контейнеров: 6 могут содержать до 3 л воды и 4 могут содержать до 8 л воды.
Сколькими способами можно наполнить эти сосуды ровно 46 л воды так, чтобы количество литров воды в каждом сосуде было целым числом?
Детали и предположения:
- Порядок заполнения контейнеров значения не имеет.
- Вы не можете набрать воду ни из одной из $10$ емкостей.
- Разливов нет.
\[ \begin{eqnarray} 0. && 00000 \quad 00001 \quad 00001 \quad 00002 \quad 00003 \quad 00005 \quad 00008 \\ && 00013 \quad 00021 \quad 00034 \quad 00 055 \четверка 00089\четверка 00144 \quad \ldots \\ \end{eqnarray} \]
Выше показаны первые несколько цифр (фактически 65) десятичного представления дроби $ \large \frac1{9,999,899,999}. $ Если мы разделим цифры на разделы по 5, мы видим, что числа образуют последовательность Фибоначчи: $0,1,1,2,3,5,8,13,\ldots$. Сколько положительных чисел Фибоначчи мы можем найти, прежде чем паттерн разорвется?
Примечание: Например, предположим, что дробь равна \[0,00000 \quad 00001 \quad 00001 \quad 00002 \quad 00003 \quad 00009 \ldots \] вместо той, что указана вверху. Тогда вы сможете найти только первые пять чисел Фибоначчи, а именно $0,1,1,2,3$. Таким образом, ваш ответ будет заключаться в том, что есть 4 положительных числа Фибоначчи, прежде чем модель прервется.
- Бонус : Обобщите это.
- Попробуйте решить задачу Даниэля Лю, вдохновленную этой задачей. 9я.$$ Мудрец может решить многие рекуррентные отношения; это позволяет нам проверить наш ответы. Иногда формат может немного отличаться от того, что вы получаете рукой.
  Вот интересная особенность этого выражения: поскольку $|(1-\sqrt5)/2|
  Мы можем проверить это в Sage. {n-1}}={1+\sqrt{5}\over 2}. $$ Это так называемое «золотое сечение». 9n$, $h_0=0$, и использовать его, чтобы найти формулу за $h_n$.
  Пример 3.4.4 Найдите производящую функцию решений задачи $h_n=4h_{n-2}$, $h_0=0$, $h_1=1$ и используйте его, чтобы найти формулу для $h_n$. (Это легко открыть эту формулу непосредственно; дело здесь в том, чтобы увидеть, что метод производящей функции дает правильный ответ.)
  Пример 3.4.5 Найдите производящую функцию решений $h_n=h_{n-1}+h_{n-2}$, $h_0=1$, $h_1=3$ и используйте его, чтобы найти формулу за $h_n$.
  Пример 3.4.6 Найдите производящую функцию решений $h_n=9h_{n-1}-26h_{n-2}+24h_{n-3}$, $h_0=0$, $h_1=1$, $h_2=-1$, и используйте его, чтобы найти формулу для $h_n$.
  Пример 3.4.7 Найдите производящую функцию решений $h_n=3h_{n-1}+4h_{n-2}$, $h_0=0$, $h_1=1$, и используйте его, чтобы найти формулу для $h_n$.
  Пример 3.4.8 Найдите рекурсию количества способов расставить флаги на $n$ футовый столб, где у нас есть красные флаги высотой 2 фута, синие флаги высотой 1 фут и желтые флаги высотой 1 фут; в высота флагов должна составлять $n$.
  No related posts.