Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO
7.2 ОСНОВНЫЕ МАНЕВРЫСконцентрируем теперь свое внимание на методах, которые и позволяют говорить о степенных рядах в превосходной степени. Сначала несколько слов о терминологии и обозначениях. Всякая производящая функция может быть произведена из следующего общего выражения
Мы говорим, что Сумма в (7.12) включает все При работе с производящими функциями можно говорить о двух разновидностях выражений в „замкнутом виде“ Возможно, мы выразим Теперь поговорим о перспективах. Производящая функция функция — просто формальный степенной ряд, в котором z стоит потому, что ведь что-то надо написать. В предыдущем разделе, например, мы использовали вторую точку зрения; несколько раз мы подставляли z в „сумму“ комбинаторных объектов вместо каких-либо качеств этих объектов. После этого коэффициент при Если мы рассматриваем Однако, как правило, сходимость не будет играть для нас существенной роли, если только мы не изучаем асимптотическое поведение коэффициентов. Почти всем операциям над производящими функциями, которые мы проделывали, можно дать строгое истолкование как операциям над формальными степенными рядами, и такие операции являются корректными, даже если ряд расходится. (Соответствующую теорию можно найти, например, в работах Белла [19], Найвена [228] и Хенричи [336, гл. С другой стороны, даже если мы отбросим все предосторожности и выведем какую-либо формулу без строгого обоснования, то обычно оказывается возможным просто взять окончательную формулу и доказать ее по индукции. Например, производящая функция для чисел Фибоначчи сходится лишь при До сих пор речь шла о перспективах. А теперь рассмотрим наш инструментарий, т. е. набор приемов преобразования производящих функций — их сложения, сдвига, замены переменных в производящих функциях, дифференцирования, интегрирования и перемножения. В последующем изложении мы примем, если не оговорено противное, что Вполне очевидно, что получится, если умножить каждую из производящих функций
Мы получаем производящую функцию последовательности Сдвиг производящей функции ненамного сложнее. Чтобы сдвинуть
Когда мы в гл. 6 искали выражение в замкнутом виде для чисел Фибоначчи, то использовали (дважды) именно эту операцию, а также сложение, чтобы вывести уравнение Чтобы сдвинуть
(Последнюю сумму нельзя распространить на все Еще один из наших трюков — это умножение z на константу:
получили производящую функцию последовательности Часто оказывается нужным добавить к коэффициентам множитель
Выполнив сдвиг на одну позицию вправо, получим формулу, которая иногда даже более полезна:
Это — производящая функция последовательности Обратная операция, интегрирование, дает способ поделить элементы последовательности на
(Заметьте, что постоянный член равен нулю.) Если вместо И, наконец, продемонстрируем умножение производящих функций:
Как мы видели в гл. 5, полученная сумма есть производящая функция последовательности Имеется ряд частных случаев умножения, которые заслуживают того, чтобы рассматривать их как отдельные операции. Один из таких случаев мы уже видели: если Еще один полезный частный случай получается, когда
Умножение производящей функции на В табл. 368 собраны все операции, которые мы рассмотрели. Для эффективного использования этих операций полезно иметь в запасе достаточно большой набор производящих функций. В табл. 369 перечислены простейшие из них; используя для начала их, мы уже сможем решить кое-какие задачи. Таблица 368 Преобразования производящих функций. (см. скан) Каждая производящая функция, включенная в табл. 369, сама по себе достаточно важна, чтобы ее стоило запомнить. Многие функции здесь — частные случаи других, а некоторые могут быть легко получены применением операций из табл. 368; таким образом, работа по запоминанию не очень велика. Рассмотрим, например, последовательность (см. скан) Последовательность
следовательно,
Аналогично можно извлечь члены с нечетными номерами:
В частном случае Попробуем применить этот прием к производящей функции для чисел Фибоначчи. Мы знаем, что
Эта функция производит последовательность
|
1 |
Оглавление
|