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

Рекуррентные соотношения и производящие функции

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

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

   

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

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

и

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

   

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

   

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

   

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

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

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

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

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

   

где — произвольное комплексное число.

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

   

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

   

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

   

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

   

что совпадает с левой частью равенства 2) при \alpha=n, откуда получаем требуемое.

Можно также доказать следующие равенства (сделайте это самостоятельно):

   

3. Деление производящих функций

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

Утверждение. Пусть — формальный степенной ряд, такой, что . Тогда существует единственный формальный степенной ряд , такой, что .

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

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

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

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

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

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

Представим дробь в виде суммы простейших дробей:

   

здесь .

Отсюда

   

Здесь мы воспользовались тем, что .

5. Числа Каталана

Еще одна известная последовательность: последовательность Каталана Она задается соотношением , >. Так, например, при получаем .

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

   

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

   

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

   

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

   

или, умножая числитель и знаменатель на и сокращая на , получаем

   

Эта формула дает и более простое рекуррентное соотношение для чисел Каталана:

   

6. Рациональные производящие функции

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

   

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

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

   

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

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

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

Скажем несколько слов о производящих функциях несколько более общего вида.

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

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

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

   

и

   

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

   

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

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

   

Выражение в правой части этого равенства называется квазимногочленом от переменной .

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

   

Коэффициент при в этой производящей функции равен

   

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

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

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

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

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

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

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

   

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

   

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

   

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

   

Легко видеть, что

   

поэтому

   

Задачи.

1. Решите последовательности

а) , , , .

б) , , , .

2. Докажите равенства (3)–(7).

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

а) ;

б) ;

в) .

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

а) ;

б) ?

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

а) ;

б)

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

а) ;

б) ;

в) ;

г) .

7. Пусть . Докажите, что

   

Докажите, что .

8. Последовательность такова, что

   

Найдите .

9. Пусть . Найдите рекуррентное уравнение

   

Оцените сходимость и вычислите .

10. Пусть

   

Доказать, что для некоторого .

11. Доказать, что при любых натуральных

   

— целые числа, удовлетворяющие рекуррентному соотношению

   

12. Пусть

   

Докажите, что

   

Источник: С.К. Ландо “Лекции о производящих функциях”, МЦНМО, Москва, 2004.

Производящие функции — Студопедия

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

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

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

Примеры: 1) Для степенного ряда , члены которого можно рассматривать как геометрическую прогрессию, знаменатель . Значит, степенной ряд при условии сходится к своей сумме . Таким образом, получаем:

, если .

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

2) Аналогично можно получить:

.

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

3) Из формулы бинома Ньютона следует:

,

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

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

;

;

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

Кроме того:

,

,

.

В последнем равенстве, если , то считают, что . Поэтому меняется от до наименьшего из чисел , .

Последнее равенство можно доказать следующим образом:

,

.

Отсюда следует: .

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

В частном случае, когда , получаем равенство:

, .

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

1) Рассмотрим разбиение числа на слагаемые, каждое из которых равно одному из чисел . При этом слагаемые не повторяются и их порядок не играет роли.

Для решения задачи рассмотрим выражение . Раскрывая скобки, получим слагаемые вида , где – некоторые из чисел . Поэтому ^{встретится в сумме столько раз, сколькими способами можно разбить на слагаемые требуемым образом.}

Например, если надо узнать, сколькими способами можно заплатить 78 копеек, беря не более одной монеты каждого достоинства, то надо составить выражение:

,

раскрыть скобки и найти коэффициент при слагаемом .

2) Если требуется разложить число на слагаемые , каждое из которых может встречаться в разложении один или несколько раз, тогда количество слагаемых в скобках увеличивается.

Например: 1) Сколькими способами можно заплатить 29 коп., используя монеты по 2 и 5 коп?

Т.е. надо найти число способов разбить число 29 на слагаемые, равные 2 и 5, причем порядок слагаемых роли не играет, и каждое слагаемое может повторяться несколько раз. Для этого составим выражение:

.

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

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

.

Разделив «уголком» числитель на знаменатель, находим коэффициент при выражении .

2) Поступающий в ВУЗ должен сдать 4 экзамена, причем для поступления достаточно набрать 17 балов. Сколькими способами абитуриент может сдать экзамены, чтобы поступить в ВУЗ?

Требуется узнать, сколькими способами можно представить число 17 в виде суммы 4-х слагаемых, принимающих значения 3, 4, 5, причем здесь порядок слагаемых имеет значение.

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

В выражении можно раскрыть скобки по полиномиальной теореме, а можно следующим образом:

.

Поэтому .

.

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

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

Пусть — производящая функция для последовательности чисел . Это означает, что является суммой степенного ряда: .

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

.

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

При считаем, что . А дальше все соотношения имеют вид: , где , т.к. не имеет членов степени , , …

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

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

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

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

Эндрю Эллинор, Хуа Чжи Ви, Махиндра Джейн, и

способствовал

Содержимое

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

  Примечание. Термин «формальный» используется потому, что это алгебраическое, а не аналитическое понятие.

  В приведенном выше примере мы могли бы просто подсчитать количество способов сделать 10 10 10 путем проверки. Однако производящие функции невероятно полезны, если полиномы могут быть выражены в более компактной форме (например, с использованием суммы геометрического ряда), а затем умножение может привести к сокращению и упрощению вычислений. 92 R2​(x)=[R1​(x)]2, следовательно, мы можем вычислить его напрямую, не считая каждого члена в отдельности. □_\квадрат□​

  Сколько решений в неотрицательных целых числах имеет уравнение a+b+c=20a + b + c = 20a+b+c=20?

  ---

  Сначала мы рассмотрим более общий вопрос о нахождении числа решений в неотрицательных целых числах уравнения a+b+c=n a + b + c = n a+b+c=n. Поскольку значением aaa может быть любое целое неотрицательное число 0,1,2,3,…,i,…0,1,2,3, \ldots, i , \ldots 0,1,2,3,…, i,… (см. примечание ниже), мы можем представить это как производящую функцию 9я + \cdots. (1−x)31​=(22​)+(23​)x+(24​)x2+⋯+(2i+2​)xi+⋯.

  Таким образом, при n=20n=20 n=20 ответ будет равен (222) { 22 \выбрать 2 } (222​). Это согласуется с тем, что мы знаем из метода звезд и полос. □_\квадрат□​

  Примечание. Может возникнуть путаница, почему мы допускаем, что aaa может быть любым неотрицательным целым числом, даже большим, чем nnn, что явно не приведет к решению. Подумайте, что произойдет, если мы допустим a=n+1a = n+1a=n+1 или a=n+2a = n+2a=n+2 или любое большее целое число: в конечном произведении полиномов показатели этих члены будут больше, чем n, n, n, поэтому они не будут вносить вклад в нужный нам член, который имеет показатель n.n.n.

  У Коди есть 4 вида луковиц:

  • Количество фиолетовых\цветных{#69047E}\text{фиолетовых}фиолетовых луковиц может быть любым неотрицательным целым числом.
  • Количество зеленых\цветных{#20A900}\text{зеленых}зеленых луковиц кратно 2.
  • Количество красных\color{#D61F06}\text{red}красных луковиц кратно 3.
  • Количество синих\color{#3D99F6}\text{blue}синих луковиц кратно 5.

  Если у Коди 23 луковицы, сколько может быть различных распределений цветов?

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

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

  3x+y+z=24. 3x+y+z=24,3x+y+z=24.

  Попробуйте и это:

  Есть 101010 красных \mathrm{\color{#D61F06}{red}}красных шаров, 101010 синих \mathrm{\color{#3D99F6}{blue}}синих шаров и 101010 зеленых \ матрм {\ color {# 20A900} {зеленый}} зеленые шары.

  Сколькими способами можно выбрать 161616 шаров так, чтобы было хотя бы по одному шару каждого цвета? 9{\infty}{ci​}i=1∞​ – это способ выражения cnc_ncn​ через kkk предыдущих членов последовательности для некоторого положительного целого числа k. k.k. Однородное линейное рекуррентное соотношение — это соотношение вида cn+q1cn−1+q2cn−2+⋯+qkcn−k=0.c_n + q_1c_{n-1} + q_2c_{n-2} + \cdots +q_kc_{ n-k} = 0.cn​+q1​cn-1​+q2​cn-2​+⋯+qk​cn-k​=0. Он линейный, потому что каждый член имеет только один моном вида cic_ici​, и однородный, потому что правая часть равна 0. Если бы правая часть была ненулевой функцией от n,n,n, то она была бы неоднородный. Чтобы полностью решить рекуррентное соотношение, нам потребуются начальные значения для первых членов kkk, где это kkk такое же, как в определении. 9n (n — 2) cn​=3×2n−(−1)n(n−2). □_\квадрат□​

  Обобщим приведенный выше пример. Предположим, что у нас есть последовательность чисел c0,c1,c2,…c_0, c_1, c_2, \ldotsc0​,c1​,c2​,… чисел, которые удовлетворяют рекуррентному соотношению ck+q1ck-1+q2ck-2+⋯+qdck- d=0.c_k + q_1 c_{k-1} + q_2c_{k-2}+ \cdots + q_dc_{k-d} = 0.ck​+q1​ck-1​+q2​ck-2​+⋯+ qdck−d=0. Тогда члены рекуррентности — это коэффициенты производящей функции, заданной некоторой рациональной функцией f(x)=p(x)/q(x). f(x) = p(x) /q(x).f( х)=р(х)/q(х). В частности, 9d},f(x)=k=0∑∞​ck​xk=1+q1​x+q2​x2+⋯+qd​xdm0​+m1​x+m2​x2+⋯+mj​​,

  , где у нас есть j+1j+1j+1 начальные члены c0,c1,…,ckc_0,c_1,\ldots ,c_kc0​,c1​,…,ck​ и mim_imi​ определены как

  m0=c0m1=c1 +q1c0m2=c2+q1c1+q2c0.\begin{массив}{l} m_0 = c_0\\ m_1 = c_1 + q_1c_0\\ m_2 = c_2 + q_1c_1 + q_2c_0. \end{array}m0​=c0​m1​=c1​+q1​c0​m2​=c2​+q1​c1​+q2​c0​.​

  Мы можем использовать это для явного определения ckc_kck​ нахождение корней знаменателя и разложение на частные дроби рациональной функции. Мы можем найти коэффициент ckc_kck, применив теорему отрицательного бинома к каждому члену. Таким образом, мы можем сделать следующий вывод: 9n.cn​=(a1,1​+a1,2​n+⋯+a1,m1​​nm1​−1)α1n​+⋯+(aj,1​+aj,2​n+⋯+aj,mj​ ​nmj​−1)αjn​.

  Константы a1,1,a1,2,…,aj,mja_{1,1}, a_{1,2}, \ldots, a_{j,m_j}a1,1​,a1,2​,…, aj,mj выбираются так, чтобы удовлетворять начальным условиям.

  Обратите внимание, что общее количество этих констант равно k,k,k, поэтому нам нужно kkk начальных значений.

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

  cn+q1cn−1+q2cn−2+⋯+qkcn−k=f(n).c_n + q_1c_{n-1} + q_2c_{n-2} + \cdots +q_kc_{n-k} = f(n ).cn​+q1​cn−1​+q2​cn−2​+⋯+qk​cn−k​=f(n).

  Даже с таким небольшим изменением решения становятся намного сложнее.

  Найдите cn,c_n,cn​, где

  cn−3cn−2−2cn−3=4n−2, для n≥3c_n -3c_{n-2} — 2c_{n-3} = 4n – 2, \mbox{ для } n \geq 3cn​−3cn −2​−2cn−3​=4n−2, для n≥3

  и c2=12,c1=5,c0=5 c_2 = 12, c_1 = 5, c_0 = 5 c2​=12,c1​=5,c0​=5.

  ---

  9н. \ _\square cn​=18101​×(−1)n+965​×2n−31​×(n+1)×(−1)n−25​×1n−1×(n+1)×( 1)н. □​

  Примечание. Типичный подход к решению такой задачи состоит в том, чтобы заметить, что если ana_nan​ и bnb_nbn​ — последовательности, удовлетворяющие рекуррентности, то dn=an−bnd_n = a_n — b_ndn​=an​−bn​ удовлетворяет рекуррентности cn +q1cn−1+q2cn−2+⋯+qkcn−k=0. c_n + q_1c_{n-1} + q_2c_{n-2} + \cdots +q_kc_{n-k} = 0.cn​+q1​cn− 1​+q2​cn−2​+⋯+qk​cn−k​=0. Заметим, что это однородная версия данной рекуррентной задачи, которая легко решается. Следовательно, нам просто нужно найти конкретный пример an a_n an​ и добавить его к общей форме для cn c_n cn​. 92}. \_\квадратϕ(x2)=1−x21​. □​

  64 66 69 72

  Есть 30 следующих шаров:

  • 5 одинаковых белых шаров
  • 10 одинаковых черных шаров
  • 15 одинаковых красных шаров.

  Сколькими способами можно разделить эти шары на 2 ящика A и B так, чтобы в каждом ящике было по 15 шаров?

  У вас есть 10 различных пустых контейнеров: 6 могут содержать до 3 л воды и 4 могут содержать до 8 л воды.

  Сколькими способами можно налить в эти сосуды ровно 46 литров воды так, чтобы количество литров воды в каждом сосуде было целым числом?

  Детали и предположения:

  • Порядок заполнения контейнеров значения не имеет.
  • Вы не можете набрать воду ни из одного из контейнеров 101010.
  • Разливов нет.

  0.00000000010000100002000030000500008000130002100034000550008

4… \begin{aligned} 0. && 00000 \quad 00001 \quad 00001 \quad 00002 \quad 00003 \quad 00005 \quad 00008 \\ && 00013 \quad 00021 \quad 00034 \quad 00055 \quad 00089\quad 00144 \quad \ldots \\ \end{aligned} 0.​​000000000100001000020000300005000080001300021000340005500084…​

Выше показаны первые несколько цифр (фактически 65) десятичного представления дроби 19999 899 999. \ большой \ гидроразрыв1 {9 999 899 999}. 9 999 899 9991​. Если мы разделим цифры на части по 5, то увидим, что числа образуют последовательность Фибоначчи: 0,1,1,2,3,5,8,13,…0,1,1,2,3,5, 8,13,\ldточки 0,1,1,2,3,5,8,13,…. Сколько положительных чисел Фибоначчи мы можем найти, прежде чем паттерн разорвется?

Примечание: Например, предположим, что фракция равна 0,000000000100001000020000300009… 0,00000 \ Quad 00001 \ Quad 00001 \ Quad 0000002 \ QUAD 00003 \ QUAD 00009 \ LDOTS 0,0000000100001000000003009 \…вместо того, что указано выше. Тогда вы сможете найти только первые пять чисел Фибоначчи, а именно 0,1,1,2,30,1,1,2,30,1,1,2,3. Таким образом, ваш ответ будет заключаться в том, что есть 4 положительных числа Фибоначчи, прежде чем модель прервется.

---

• Бонус : Обобщите это.
• Попробуйте решить задачу Даниэля Лю, вдохновленную этой задачей.
1. Найдите cnc_ncn явно, где cn-cn-1-cn-2=0c_n — c_{n-1} — c_{n-2} = 0cn​-cn-1​-cn-2​=0 и c0=1,c1=1.c_0 = 1, c_1 = 1.c0​=1,c1​=1. 9н. k=0∑n​(k2k​)(n−k2(n−k)​)=4n.

Решение

Цитировать как: Генерирующие функции. Brilliant.org . Полученное из https://brilliant.org/wiki/generating-functions-solving-recurrence-relations/

AC Использование генерирующих функций для решения повторяющихся ситуаций

Подход, который мы рассмотрели до сих пор в этой главе, — не единственный способ решения рекуррентных уравнений. Кроме того, это действительно применимо только к линейным рекуррентным уравнениям с постоянными коэффициентами. В оставшейся части главы мы рассмотрим несколько примеров того, как производящие функции можно использовать в качестве еще одного инструмента для решения рекуррентных уравнений. В этом разделе мы сосредоточимся на линейных рекуррентных уравнениях. В разделе 9п\текст{.} \end{equation*}

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

No related posts.