Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Решение линейных рекуррентных уравнений.

Читайте также:
  1. B.8 Топологический анализ активных линейных цепей
  2. Алгоритмическое решение задач, анализ алгоритмической сложности
  3. Аналитическое и графическое решение уравнений, содержащих переменную под знаком модуля.
  4. Апелляция на решение Псковского городского суда по делу 2-2878
  5. Бог так устроил человеческую и ангельскую жизнь, чтобы сперва стало очевидным, что может свободное решение, а затем - что может дар благодати и суд справедливости
  6. ВОСКРЕШЕНИЕ СЛОВА
  7. ВОСКРЕШЕНИЕ СЛОВА
  8. Выражение элемента площади в криволинейных координатах
  9. Глава 14. Судьбоносное решение.
  10. Д) Разновидности внутреннего сопротивления. Решение больного подвергнуться психотерапевтическому лечению

Пример. Найдем производящую функцию к числам Фибоначчи: 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), где а – постоянная. Тогда

fkk 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а), получаем соотношение, известное как формула Бруно

Аnn(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; просмотров: 21 | Поможем написать вашу работу | Нарушение авторских прав

Конкретная математика | Производящие функции для сочетаний. | Представление перестановок в циклической форме. | Цикловые классы (типы). | Перестановки без единичных циклов | Композиции чисел. | Принцип включения и исключения. | Число способов, которыми можно пометить граф. | Связные графы. | Эйлеровы графы |


lektsii.net - Лекции.Нет - 2014-2024 год. (0.011 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав