Читайте также:
|
Пример. Найдем производящую функцию к числам Фибоначчи: F0=F1=1, Fn+2=Fn+Fn+1, n³0.
Производящая функция F(t) для последовательности F(0),F(1),F(2),… удовлетворяет уравнению
F(t)= 
=1+t+ 
=
1+t+t2 
+t 
=
1+t+t2F(t)+x(F(t)-1)= 1+(t+t2)F(t),
т. е. F(t)=(1-t-t2)-1.
Найдя корни уравнения 1-t-t2=0, получаем разложение
1-t-t2=(1-аt)(1-bt), где а=(1+Ö5)/2, b==(1-Ö5)/2.
Используя метод неопределенных коэффициентов, найдем
= 
+ 
т. е.
F(t)=A(1-at)-1+B(1-bt)-1=A 
+B 
= 
tk
и
Fk= 
+ 
Замечание. этот метод можно перенести на произвольное линейное уравнение с постоянными коэффициентами.
Задача 1. Пусть задана последовательность Фибоначчи
F0=F1=1, Fn+2=Fn+Fn+1, n³0.
Рассмотрим множество последовательностей из нулей и единиц длины n, в которых нет двух рядом стоящих единиц. Пусть таких последовательностей A(n). Тогда А(n)=Fk+1.
Доказательство.
Имеем А(0)=1, так как существует только одна – пустая, такая последовательность; А(1)=2, так как существует две такие последовательности – ‘0’ и ‘1’.
Заметим, что число последовательностей длины n, у которых на n месте находится нуль, равно А(n-1).
Все последовательности длины n+1 могут быть построены из последовательностей длины n приписыванием к каждой из них на n+1 место нуля и, кроме того, тем из них, которые на n месте имеют ноль, можно также приписать единицу. Таким образом, А(n+1)=A(n)+A(n-1)=Fn+1+Fn=Fn+2.
Задача 2. "n>0 А(n)= 
= 
.
Доказательство.
А(n) можно получить следующим образом:
Заметим, что каждая такая последовательность длины n может содержать не более [(n+1)/2] единиц. Подсчитаем, сколько существует последовательностей, содержащих k единиц, 0£k£[(n+1)/2]. Если последовательность имеет к единиц, то она содержит n-k нулей. Рассмотрим последовательность из n-k нулей. Тогда в этой последовательности имеется n-k+1 мест для расстановки k единиц. Т. е. общее число требуемых последовательно
стей длины n,содержащих k единиц, равно 
. Таким образом,
A(n)= .
Производные сложных функций (Формула Бруно)
Сложная функция – это функция от функции. Ей можно придать стандартную форму экспоненциальной (или обычной) производящей функции, воспользовавшись ее производными. Выражая производную сложной функции через ее компоненты, приходим к некоторой совокупности полиномов – полиномов Белла, – характерных для многих комбинаторных и статистических задач.
Положим
А(t)=f[g(t)] (1)
и
A(t)=An, [ 
f(u)]u=g(t)=fn, g(t)=gn, где Dt=d/dt, Du=d/du
Затем последовательным дифференцированием (1) получим
А1=f1g1
А2=f1g2+f2 
А3=f1g3+ 3f2g2g1+f2 
В общем виде можно записать
Аn=f1An1+ f2An2+…+f2Ann=
= 
An,k(g1, g2,… gn) (2)
Отметим, что коэффициенты An,k зависят только от производных g1, g2,… gn и не зависят от fk. Следовательно, они могут быть определены специальным выбором f; удобно положить f(u)=exp(au), где а – постоянная. Тогда
fk=аk exp(ag), g=g(t)
и
e-ag eag=ΣAn,k(g1, g2,… gn)ak=
An(a, g1, g2,… gn), (3)
где вторая строка – сокращенная запись первой
В этих обозначениях (2) принимает вид
Аn=An(a, g1, g2,… gn), fk≡fk, (2a)
где
А0=f0=A(t)
Соотношение (3) полностью определяет полиномы An(a,g1,g2,…gn) и с помощью (2а), – производные An. Можно заметить, что в обозначениях Белла
An(1, y1, y2,… yn)=Yn(y1, y2,… yn)=e-y 
ey,
y≡y(x).
С целью получения явного выражения для полиномов Белла обозначим кратко
An(a, g1, g2,… gn)
через Аn(a) и используем формулу Лейбница для дифференцирования произведения
Аn+1(a)=e-agDn(Deag)=
=a-agaDn(g1 eag)=
=а 
(e-agDn-keag)Dkg1=
=а An-k(a)gk+1=
=ag(A(a)+g)n; (A(a))k≡Ak(a), gk≡gk (4)
Частными случаями соотношения (4) при А0(a)=1 являются соотношения
А1(a)=ag1
А2(a)=ag2+ag1А1(a)=ag2+a2
А3(a)=ag3+ 2ag2А1(a)+ag1А2(a)= ag3+ 3a2g2g1+a3 ,
что согласуется с результатами, предшествующими (2)
Далее, соотношение (4) влечет за собой соотношение для экспоненциальной производящей функции
exp(uA(a))= 
(a)un/n!=
=exp(a[ug1+u2g2/2!+…])=
=exp(aG(U), (5)
в котором
G(u)=exp(ug) – g0, gn≡gn
Дифференцированием (5) и приравниванием коэффициентов при un получаем (4).
Наконец, раскрывая (5) с помощью полиномиальной теоремы и приравнивая коэффициенты при un получаем искомую формулу
Аn(a)= 
, (6)
в которой k1 +k2+…+kn=k и сумма берется по всем решением в неотрицательных целых числах уравнения k1 +2k2+…+nkn=n, или по всем разбиениям n. Отсюда, имея в виду (2а), получаем соотношение, известное как формула Бруно
Аn=Аn(f)= 
(5а)
Замечание. Если A(t) разлагается в ряд Тейлора, т. е. если
A(t+u)=exp(uA(t)), An(f)≡An(f),
то
=An(f) при t=0,
A(t)= exp(uA0), (A0)n≡ .
Дата добавления: 2015-09-11; просмотров: 82 | Поможем написать вашу работу | Нарушение авторских прав |