X-PDF

Производящие функции

Поделиться статьей

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

u(x) = ,

который называется производящей функцией данной последовательности. Слова “формальный ряд” означает, что эту формулу мы трактуем только как удобную запись последовательности. Для нас сейчас несущественно, при каких значениях х ряд сходится и сходится ли вообще, т.к. вычислять значение u(x) мы никогда не будем.

Пример 3.5. Известно, что = 1 + х + х2 + … + хn + … Следовательно, функция является производящей для последовательности 1,…, 1.

Пример 3.6. Согласно формуле бинома Ньютона (1 + х)n= . Следовательно, функция (1 + х)n является производящей для конечной последовательности .

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

4.2.а. Линейная комбинация. Если функция u(x) соответствует последовательности {un}, а v(x) – последовательности {vn}, то функция a×u(x) + b×v(x) (a и b – константы) является производящей для последовательности { a×un + b×vn}.

4.2.б. Сдвиг. Если функция u(x) соответствует последовательности {un}, то функции хm×u(x) соответствует последовательность … – сдвиг вправо.

Аналогично, функция является производящей для последовательности um, um+1, … – сдвиг влево.

4.2.в. Умножение. Если функция u(x) соответствует последовательности {un}, а v(x) – последовательности {vn}, то функции u(x)×v(x) соответствует последовательность {wn}, где

– формула Коши. Например, w0 = u0×v0 . w1 = u0 ×v1 + u1 ×v0 . w2 = u0 ×v2 + u1 ×v1 + u2 ×v0.

Пример 3.7. Пусть u(x) соответствует последовательности {un}, а v(x) = – производящая функция для последовательности 1,…, 1 (см. пример 3.5). Тогда функция

= u0 + (u0 + u1) x + (u0 + u1 + u2) x2 +… (3.9)

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

4.2.г. Дифференцирование и интегрирование. Если u(x) соответствует последовательности {un}, то по правилу дифференцирования рядов

u¢(x) = 0 + u1 + 2 u2 x + 3 u3 x2 + ….

То есть u¢(x) является производящей функцией для последовательности {k uk}.

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

Пример 3.8. = . Следовательно, функция является производящей для последовательности {k}.

Далее,

(3.10)

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

Сопоставляя (3.10) с (3.9) получаем

,

где – гармонические числа.

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

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

Пример 3.9. На окружности находится 2n точек. Сколькими способами можно их попарно соединить так, чтобы полученные отрезки не соединялись друг с другом?

Представленная информация была полезной?
ДА
58.69%
НЕТ
41.31%
Проголосовало: 990

Решение. Обозначим un – число способов соединить 2n точек. Построим рекуррентное соотношение.

Формально положим u0 = 1 (нет точек, нет пересечений, следовательно, способ единственный). u1 = 1 – очевидно, т.к. две точки соединяются единственным способом, и пересечений нет. u2 = 2. Способы соединения изображены на рис. 3.1.

           
   
 
 
 
   
Рис. 3.1. Способы соединения 4-х точек

Пусть n &gt . 1. Выберем одну из 2(n + 1) точек, обозначим ее А. Соединим А с вершиной В, выбрав ее так, чтобы с обеих сторон от соединяющей их линии находилось четное число точек. Пусть слева будет 2k точек, справа – 2(n – k). 2k точек можно соединить между собой uk способами, 2(n – k) точек – unk способами. При этом линии не пересекутся, т.к. 2k и 2(n – k) точек расположены по разные сторона от АВ.

Следовательно, при фиксированном k получим uk×unk способов соединения. Но k меняется от 0 до n. Следовательно,

un +1 = u0×un + u1×un–1 + … + un×u0. (3.11)

Получили искомое нелинейное рекуррентное соотношение, формула общего решения которого нам, к сожалению, неизвестна.

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

u(x) = u0 + u1х + u2 x2 + u3 x3 + …. (3.12)

Имеем, согласно формуле Коши:

[ u(x) ]2 = (u0)2 + (u0×u1 + u1×u0) х + (u0×u2 + u1×u1 + u2×u02 + …

Видно, что коэффициенты для разложения [ u(x) ]2 можно получить с помощью формулы (3.11).

Из (3.12) имеем: = u1 + u2 x + u3 x2 + ….

Подставим в эту формулу выражение uk согласно (3.11). С учетом того, что u1 = (u0)2 получим: . Следовательно, имеем квадратное уравнение относительно u(х). Решив его, получим .

По формуле бинома имеем:

++…= 1 –.

Умножим каждое k-е слагаемое на 1 = . Тогда коэффициент k-го члена ряда равен:

= = = .

Отсюда

.

Для того, чтобы коэффициенты ряда были положительными, надо перед корнем в формуле u(x) брать знак “–”. Заменим индекс суммирования k на k +1. В результате получим:

u(x) = == .

Окончательно – это так называемые, числа Каталана.


Поделиться статьей
Автор статьи
Анастасия
Анастасия
Задать вопрос
Эксперт
Представленная информация была полезной?
ДА
58.69%
НЕТ
41.31%
Проголосовало: 990

или напишите нам прямо сейчас:

Написать в WhatsApp Написать в Telegram

ОБРАЗЦЫ ВОПРОСОВ ДЛЯ ТУРНИРА ЧГК

Поделиться статьей

Поделиться статьей(Выдержка из Чемпионата Днепропетровской области по «Что? Где? Когда?» среди юношей (09.11.2008) Редакторы: Оксана Балазанова, Александр Чижов) [Указания ведущим:


Поделиться статьей

ЛИТЕЙНЫЕ ДЕФЕКТЫ

Поделиться статьей

Поделиться статьейЛитейные дефекты — понятие относительное. Строго говоря, де­фект отливки следует рассматривать лишь как отступление от заданных требований. Например, одни


Поделиться статьей

Введение. Псковская Судная грамота – крупнейший памятник феодального права эпохи феодальной раздробленности на Руси

Поделиться статьей

Поделиться статьей1. Псковская Судная грамота – крупнейший памятник феодального права эпохи феодальной раздробленности на Руси. Специфика периода феодальной раздробленности –


Поделиться статьей

Нравственные проблемы современной биологии

Поделиться статьей

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


Поделиться статьей

Семейство Первоцветные — Primulaceae

Поделиться статьей

Поделиться статьейВключает 30 родов, около 1000 видов. Распространение: горные и умеренные области Северного полушария . многие виды произрастают в горах


Поделиться статьей

Вопрос 1. Понятие цены, функции и виды. Порядок ценообразования

Поделиться статьей

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


Поделиться статьей

или напишите нам прямо сейчас:

Написать в WhatsApp Написать в Telegram
Заявка
на расчет