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 точек. Сколькими способами можно их попарно соединить так, чтобы полученные отрезки не соединялись друг с другом?
|
|
Решение. Обозначим un – число способов соединить 2n точек. Построим рекуррентное соотношение.
Формально положим u0 = 1 (нет точек, нет пересечений, следовательно, способ единственный). u1 = 1 – очевидно, т.к. две точки соединяются единственным способом, и пересечений нет. u2 = 2. Способы соединения изображены на рис. 3.1.
|
Пусть n > . 1. Выберем одну из 2(n + 1) точек, обозначим ее А. Соединим А с вершиной В, выбрав ее так, чтобы с обеих сторон от соединяющей их линии находилось четное число точек. Пусть слева будет 2k точек, справа – 2(n – k). 2k точек можно соединить между собой uk способами, 2(n – k) точек – un–k способами. При этом линии не пересекутся, т.к. 2k и 2(n – k) точек расположены по разные сторона от АВ.
Следовательно, при фиксированном k получим uk×un–k способов соединения. Но 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×u0)х2 + …
Видно, что коэффициенты для разложения [ 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) = == .
Окончательно – это так называемые, числа Каталана.