Линейни рекурентни отношения с постоянни коефициенти. Основни дефиниции и примери за рекурентни релации Често решението на един комбинаторен проблем може да се сведе до решаването на подобни проблеми с по-ниско измерение, като се използва определена релация, наречена рекурентна от латинската дума recurrere връщане. По този начин решението на сложен проблем може да бъде получено чрез последователно намиране на решение на по-лесни проблеми и след това преизчисляване с помощта на рекурентни отношения, за да се намери решение на труден проблем. Повтарящата се връзка на...
Ако тази работа не ви подхожда, в долната част на страницата има списък с подобни произведения. Можете също да използвате бутона за търсене
Аранов Виктор Павлович. Дискретна математика. Раздел 2. Елементи на комбинаториката.
Лекция 5. Метод на рекурентните отношения
Лекции 5. МЕТОД НА ПОВТАРЯЩИТЕ СЕ ВРЪЗКИ
Конспект на лекцията:
Бине.
Често решението на един комбинаторен проблем може да се сведе до решаването на подобни проблеми с по-ниско измерение, като се използва определена връзка, наречена рекаР наем (от латинската думарецидивиращ връщане). По този начин решението на сложен проблем може да бъде получено чрез последователно намиране на решения на по-лесни проблеми и след товад Изчисляване с помощта на рекурентни отношения, намиране на решение на труден проблем.
Рекурентна връзка от ти порядъкмежду елементите на редица от числа се нарича формула на вида
(1)
Частно решениерекурентна връзка е всеки наследник b ност, която превръща връзката (1) в идентичност. Съотношение (1) imд има безкрайно много конкретни решения, тъй като първите елементи са последователниО ity може да се задава произволно. Например последователността е pд чрез промяна на рекурентната връзкаО решения, тъй като идентичността е валидна.
Решението на рекурентната връзка от ти ред се наричачесто срещано, ако е за a зависи от произволни константи и чрез избиране на тези константи можеми но получите каквото и да е решение на тази връзка. Например за съотношениетод ции
(2)
общото решение ще бъде
. (3)
Наистина, лесно е да се провери, че последователност (3) превръща връзка (2) в идентичност. Следователно трябва само да покажем, че всяко решение на релация (2) можеи но го представете във формата (3). Но всяко решение на тази връзка е еднозначно определено T със значения и. Следователно трябва да докажем, че за всякакви числа и има tА какви значения и какви
Тъй като тази система има решение за всякакви стойности на и, решение (3) наистина е общо решение на отношение (2).
Пример 1. Числата на Фибоначи.През 1202 г. известният италиански математик ЛеО Нардо от Пиза, по-известен с псевдонима си Фибоначи ( Fib o nacci съкратено filius Bonacci , т.е. синът на Боначи), е написана книга „ Liber abacci" ("Книга и ga за сметалото"). Тази книга е достигнала до нас във втората си версия, която датира от 1228 г. Нека разгледаме една от многото задачи, дадени в тази книга.
Двойка зайци ражда потомство от два заека (женски и мъжки) веднъж месечно,И отколкото новородените зайци вече носят потомство два месеца след раждането. Колко зайци ще се появят?д рез година, ако в началото на годината имаше една двойка зайци?
От условията на задачата следва, че след месец ще има две двойки зайци. След два месецааз Само първата двойка зайци ще роди, а вие ще получите 3 чифта.А след още един месец, както оригиналната двойка зайци, така и двойката зайци, появила се преди два месеца, ще раждат. Следователно ще има общо 5 двойки зайци и т.н.
Нека означим с брой двойки зайци по месеци от началото на годинатаО да Тогава след няколко месеца ще има тези двойки и много повече новородени двойкиО лица, колко бяха в края на месеца, тоест все още двойка. Така, pд текущото съотношение
. (4)
Тъй като последователно намираме: и т.н. Тези числа съставляват последователността
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377,…,
което се наричадо Фибоначи и неговите членове Числата на Фибоначи. Те имат редица прекрасни свойства. Числата на Фибоначи са свързани със следните комбинациино трудна задача.
Намерете броя на двоичните думи с дължина, в които не следват две единициг ред.
Ще наречем тези думиправилно и означете броя им с. Нека разделим набора от тези правилни думи на два класа: думи, завършващи на нула, и думи, завършващи на единица. Нека обозначим броя на думите в тези класове и coo T отговорно. Според правилото за добавяне
(5)
Очевидно дума, завършваща на нула, има своите първи знаци, образуващи правилна дума с дължина, или с други думи, има биекция между набора от правилни думи с дължина, завършващи на нула, и набора от редовни думи с дължина, т.е.
Ако дума с валидна дължина завършва на единица, тогава предишният знак на тази дума трябва да е нула, а първите знаци трябва да образуват дума с валидна дължина. Както в предишния случай, отново имаме биекция между набора от правилни думи с дължина, завършващи на единица, и набора от правилни думи с дължина. Следователно. . От формула (5) получаваме рекурентната връзкаотносно шиенето
. (6)
За да се използва рекурентната връзка, са необходими изчисления за даденостс променя всички предишни стойности. Например, ако трябва да знаем броя на правилата b думи от 10 знака, тогава може да се намери чрез последователно попълване на следнотоб лице:
маса 1
Първите две стойности се намират директно (думи 0 и 1; думи 000, 010, 101), а останалите с помощта на формула (6).
Пример 2. Проблемът с поставянето на скоби в израз с неасоциативен контейнервтора операция. Нека “” означава някаква двоична операция. Нека разгледаме вс израз, в който символът обозначава някаква двоична неасоциацияА тивна операция. Колко различни начина има за поставяне на скоби в това?Ядосан ли си?
Пример за неасоциативна операция е векторното произведение. Друг пример е обикновено събиране и умножение, извършено на компютър. Б сИ поради факта, че представянето на всяко число в компютърната памет е ограничено до определенн При голям брой цифри при извършване на всяка операция възниква грешка им Крайният резултат от тези грешки зависи от поставянето на скоби. Позволяваммашина нула . Означава, че. След това, докато.
Нека обозначим броя на възможните начини за подреждане на скоби с. Тогава
Нека наречем операцията продукт. За произволен, ние разделяме всички методи за подреждане на скоби в класове, включително в методите на класа, в коитоА Първо, произведението на първия и последния операнд се изчислява с известно разстояниеА нови скоби и след това техният продукт се изчислява:
(7)
Където.
По дефиниция броят на начините за поставяне на скоби за изчисляване на първите операнди е равен на за последните. Според правилото за продукта броят на подредбите skО страна за израз (4) е равна. Според правилото за добавяне
, (8)
Например, .
Нека функцията във връзка (1) е линейна th noy
, (9)
къде са някои числа. Такива отношения се наричатлинейни зависимости ции от ти ред с постоянни коефициенти.
Първо, ние разглеждаме отношенията от втори ред в детайли и след това преминаваме към b всеки повод. Когато от формула (9) получаваме
, . (10)
Решението на тези отношения се основава на следните лесно доказуеми твърдения e ния.
Лема 1. Нека е решение на релация (10) и нека е произволно число. Тогава последователността също е решенаИ Аз ям това съотношение.
Лема 2. Нека и решения на релациятаО шиене (10). Тогава последователността също еаз се определя от решението на тази връзка.
От тези две прости леми можем да направим следното важно заключение. СовокуП съществуването на всички възможни последователности с pokoo операцииР dinata събиране и умножение със скалар образува векторно пространство. СовокуП броят на последователностите, които са решения на релация (10), е сО битката е подпространство на това пространство. Обхващащото пространство на всички възможни nО следствията е безкрайномерно, но подпространството на решенията на линейно повторение T Тази връзка има крайна размерност, равна на реда на уравнениетое ния.
Лема 3. Размерността на пространството на решенията на рекурентната връзка (10) е две.
От лема 3 следва, че за определяне на всички решения на уравнение (12) е необходимо да се намерят две линейно независими решения. Всяко друго решение ще бъде изпратено b чрез линейна комбинация от тези основни решения.
Разгледайте рекурентната връзка от първи ред
, (11)
където е константа.
Ако, тогава от (11) имаме
, (12)
това означава, че решението на рекурентно уравнение от първи ред е геометрична прогресия.
Ще търсим решение на рекурентната връзка от втори ред също във вида (12). След това, замествайки (12) в (9), получаваме
. (13)
При =0 имаме нулево решение, което не представлява интерес. Преброявайки, разделяме последното съотношение на:
(14)
Така геометричната прогресия (12) е решение на рекурентната връзка (10), ако знаменателят на прогресията е коренът на квадратното уравнениед ния (14). Това уравнение се наричахарактеристично уравнениеза повтарящо се гукане t носене (9).
Конструирането на основни решения зависи от корените и характеристичното уравнение (14).
(15)
чрез подходящ избор на константи може да се получи всяко решение на връзката (10). Нека разгледаме произволно решение. Нека изберем константите и така че за и:
(16)
Детерминанта на линейна система (16)
следователно системата има единствено решение, което означава формула (15) обща pд решение на релация (10).
. (17)
В случая на връзката от ти ред (9) са валидни твърдения, подобни на тези, разглеждани за уравнения от втори ред.
. (18)
Полином
(19)
Наречен характерен полиномрекурентна връзка (9).
. (20)
За дадени начални стойности на решението, константи nА напускане на системата
Нека характеристичното уравнение (18) има корени: ,..., кратност сО отговорно,..., и. След това характерните мнО член и общото решение на релация (9) ще бъде представено във формата
Пример 3. Формулата на Бине . Нека поставим задачата да получим формула в ясен вид за hИ Фибоначи седна. За да направим това, ще намерим решение на рекурентната връзка (4) при условие, че. Да съставим характеристично уравнение, да намерим неговите корени и да получим общо решение. Константи и дефинициид lim от началните условия: . Тогава или
, (21)
къде е златното сечение. Формула (21) се наричаФормулата на Бине . При което. От формулата на Бине следва, че.
Други подобни произведения, които може да ви заинтересуват.vshm> |
|||
| 3792. | Рационалност на съотношенията в активите на предприятието | 113,83 KB | |
| Балансът е основната форма на финансова отчетност. Той характеризира имущественото и финансовото състояние на организацията към отчетната дата. Балансът отразява салдата по всички счетоводни сметки към отчетната дата. Тези показатели се представят в баланса в определена група. | |||
| 8407. | Константен метод | 17,82 KB | |
| Казва се, че методът на обекта има свойството неизменност (постоянство), ако след неговото изпълнение състоянието на обекта не се променя. Ако свойството неизменност не се контролира, тогава неговото осигуряване ще зависи изцяло от уменията на програмиста. Ако непроменим метод произвежда странични ефекти по време на изпълнение, резултатът може да бъде много неочакван; много е трудно да се отстраняват грешки и да се поддържа такъв код. | |||
| 13457. | Метод на фазовата равнина | 892,42 KB | |
| Методът на фазовата равнина е използван за първи път за изследване на нелинейни системи от френския учен Анри Поанкаре. Основното предимство на този метод е точността и яснотата на анализа на движенията на нелинейна система. Методът е качествен | |||
| 2243. | МЕТОД НА ВЪЗМОЖНИТЕ ПОСОКИ | 113,98 KB | |
| Идеята на метода на възможните посоки на MVN е, че във всяка следваща точка има такава посока на спускане, че преместването на точката по тази посока за определено разстояние не води до нарушаване на ограниченията на проблема. Посоката, определена от вектора, се нарича възможна посока в точка, ако достатъчно малко изместване от в посоката не извежда точката извън допустимата област m. Очевидно, ако това е вътрешна точка на набор, тогава всяка посока в тази точка е възможна. Възможен... | |||
| 12947. | МЕТОД ЗА ХАРМОНИЧНА ЛИНЕАРИЗАЦИЯ | 338,05 KB | |
| Преминавайки директно към разглеждането на метода на хармоничната линеаризация, ще приемем, че изследваната нелинейна система е намалена до формата, показана в. Нелинеен елемент може да има всякаква характеристика, стига да е интегрируем без прекъсвания от втори вид. Трансформацията на тази променлива, например, чрез нелинеен елемент с мъртва зона е показана на фиг. | |||
| 2248. | Графичен метод за решаване на ЗЛП | 219,13 KB | |
| Точките, разположени вътре и на границата на тази област, са валидни планове. А именно, всички точки на отсечката AB са оптимални планове за задачата, при които се постига максимална стойност на линейната форма. Метод за последователно подобряване на плана. Методът се основава на подредено търсене на ъглови точки на много планове на проблема в посока на увеличаване или намаляване на линейната форма и съдържа три значими точки. Първо се посочва методът за изчисляване на опорния план. | |||
| 7113. | Метод на хармонична линеаризация | 536,48 KB | |
| Метод на хармонична линеаризация Тъй като този метод е приблизителен, получените резултати ще бъдат близки до истината само ако са изпълнени определени допускания: Нелинейната система трябва да съдържа само една нелинейност; Линейната част на системата трябва да бъде нискочестотен филтър, който отслабва по-високите хармоници, възникващи в граничния цикъл; Методът е приложим само за автономни системи. Изследва се свободното движение на системата, т.е. движението при ненулеви начални условия при липса на външни влияния.... | |||
| 10649. | Индексен метод на анализ | 121,13 KB | |
| Индивидуални индекси. Общи агрегатни индекси. Средни трансформирани индекси. Индекси на променлив и постоянен състав, индекси на структурни промени. | |||
| 12914. | Метод на най-малките квадрати | 308,27 KB | |
| Уведомете ни от теоретични съображения, че. Затова можем да кажем, че нашата задача е да проведем линията по възможно най-добрия начин. Ще приемем, че цялата грешка се крие в. Ние ще изберем необходимите коефициенти, така че произволното добавяне да е минимално. | |||
| 9514. | Счетоводен метод | 1002,23 KB | |
| Счетоводните документи са същите. Състои се от редица основни елементи: документация; складова наличност; рахунки; подчинен запис; Оценяване; изчисляване; баланс; слава. Счетоводните коефициенти се използват за осигуряване на яснота на активите и пасивите. Счетоводните документи са същите. | |||
Анотация: Разположения без повторение. Пренареждания. Комбинации. Рекурентни отношения. Друг метод за доказване. Процесът на последователни дялове. Задача: „Трудност за майордомото“.
Има различни предмети. Колко от тях могат да бъдат подредени? В този случай две подредби се считат за различни, ако се различават една от друга поне в един елемент или се състоят от едни и същи елементи, но подредени в различен ред. Такива договорености се наричат поставяния без повторения, а броят им е означен с . Когато съставяме разположения без повторение на елементи, трябва да направим избор. На първата стъпка можете да изберете всеки от наличните елементи. Ако този избор вече е направен, тогава във втората стъпка трябва да изберете от останалите елементи. На -та стъпка от обекти. Следователно, съгласно правилото за произведение, намираме, че броят на -разположенията без повторение на обекти се изразява, както следва:
При компилиране на аранжименти без повторение от елементи, получихме аранжименти, които се различават един от друг както по състава, така и по реда на елементите. Но ако вземем подредби, които включват всички елементи, тогава те могат да се различават един от друг само по реда на елементите, включени в тях. Такива договорености се наричат пермутации на n елемента, или накратко, пермутации.
В случаите, когато не се интересуваме от реда на елементите в една комбинация, а се интересуваме само от нейния състав, говорим за комбинации. И така, комбинации от елементи са всякакви подредби, съставени от тези елементи и различаващи се един от друг по състав, но не и по реда на елементите. Броят на -комбинациите, които могат да бъдат съставени от елементи, се означава с .
Формулата за броя на комбинациите се получава от формулата за броя на разположенията. Всъщност, нека първо съставим всичко - комбинации от елементи и след това да пренаредим елементите, включени във всяка комбинация, по всички възможни начини. В този случай се оказва, че всички са разположения на елементи, всяко само веднъж. Но можете да правите комбинации от всяко! пермутации, а броят на тези комбинации е равен на . Така че формулата е правилна
От тази формула намираме това
При решаването на много комбинаторни задачи те използват метода за редуциране на даден проблем до проблем, включващ по-малък брой обекти. Извиква се методът за свеждане до подобен проблем за по-малък брой обекти метод на рекурентните отношения(от латинското "recurrere" - "да се върна").
Ние илюстрираме концепцията за рекурентни отношения с класически проблем, който беше поставен около 1202 г. от Леонардо от Пиза, известен като Фибоначи. Значението на числата на Фибоначи за анализа на комбинаторни алгоритми прави този пример доста подходящ.
Фибоначи постави проблема под формата на история за темпа на растеж на популацията на зайци при следните допускания. Всичко започва с една двойка зайци. Всяка двойка става плодородна след месец, след което всяка двойка ражда нова двойка зайци всеки месец. Зайците никога не умират и размножаването им никога не спира.
Нека е броят на двойките зайци в популацията след месеци и нека тази популация се състои от двойки потомци и „стари“ двойки, т.е. Така през следващия месец ще се случат следните събития: . Старото население в даден момент ще се увеличи с броя на ражданията в даден момент. 
. Всяка възрастна двойка в определен момент произвежда двойка потомство в даден момент. Този модел се повтаря през следващия месец:
Комбинирайки тези равенства, получаваме следната рекурентна връзка:
| (7.1) |
Изборът на началните условия за числовата редица на Фибоначи не е важен; Основното свойство на тази последователност се определя от рекурентната връзка. Ще приемем (понякога 
).
Нека погледнем този проблем малко по-различно.
Една двойка зайци ражда котило от две зайчета (женско и мъжко) веднъж месечно, а новородените зайчета вече носят потомство два месеца след раждането. Колко зайци ще се появят за една година, ако в началото на годината е имало една двойка зайци?
От условията на задачата следва, че след месец ще има две двойки зайци. След два месеца само първата двойка зайци ще роди, а ще бъдат 3 двойки. А след още един месец и оригиналната двойка зайчета, и появилата се преди два месеца двойка зайчета ще родят. Следователно ще има общо 5 двойки зайци. Нека означим с брой двойки зайци по месеци от началото на годината. Ясно е, че след няколко месеца ще има тези двойки и още толкова новородени двойки зайци, колкото е имало в края на месеца, тоест повече двойки зайци. С други думи, има връзка на повторение
| (7.2) |
Тъй като, по условие, и , Ние последователно намираме
В частност, 
.
Извикват се номерата Числата на Фибоначи. Те имат редица прекрасни свойства. Сега нека изведем израза за тези числа чрез . За да направим това, ще установим връзка между числата на Фибоначи и следната комбинаторна задача.
Намерете броя на последователностите, състоящи се от нули и единици, в които няма две последователни единици.
За да установим тази връзка, нека вземем всяка такава последователност и сравним чифт зайци с нея съгласно следното правило: единиците съответстват на месеците на раждане на една от двойките „предци“ на тази двойка (включително оригиналния) и нулите съответстват на всички останали месеци. Например, последователността 010010100010 установява следната „генеалогия“: самата двойка се появява в края на 11-ия месец, нейните родители в края на 7-ия месец, „дядото“ в края на 5-ия месец и „великият -дядо” в края на втория месец. След това оригиналната двойка зайци се криптира с последователността 000000000000.
Ясно е, че в този случай две единици подред не могат да се появят в каквато и да е последователност - двойка, която току-що се е появила, не може, според условието, да носи потомство след месец. Освен това, с определеното правило, различните двойки зайци съответстват на различни последователности и обратното, две различни двойки зайци винаги имат различна „генеалогия“, тъй като според условието женският заек ражда потомство, състоящо се само от един чифт зайци.
Установената връзка показва, че броят на -последователностите, притежаващи посоченото свойство, е равен на .
Нека сега докажем това
| (7.3) |
Къде , ако е нечетно и , ако е четно. С други думи, - цялата част от числото (в бъдеще ще означаваме цялата част от числото с ; по този начин, 
).
Всъщност това е броят на всички последователности от 0 и 1, в които няма две 1 съседни. Броят на такива поредици, които съдържат точно единици и нули, е равен на . Тъй като това трябва да се направи
Числата на Фибоначи.
При решаването на много комбинаторни задачи те използват метода за редуциране на дадена задача до задача, включваща по-малък брой елементи. Например, можете да извлечете формула за броя на пермутациите:
Това показва, че винаги може да се редуцира до факториел на по-малко число.
Добра илюстрация на изграждането на рекурентни отношения е проблемът на Фибоначи. В своята книга през 1202 г. италианският математик Фибоначи представя следния проблем. Една двойка зайци раждат две зайчета (женско и мъжко) веднъж месечно, а самите новородени зайчета раждат потомство два месеца след раждането. Колко зайци ще се появят за една година, ако в началото е имало една двойка зайци.
От условията на задачата следва, че след месец ще има две двойки зайци, след два месеца само първата двойка зайци, появила се преди два месеца, ще даде потомство, така че ще има общо 3 двойки зайци. След месец вече ще има 5 чифта. И така нататък.
Нека означим с брой двойки зайци по месеци от началото на годината. Тогава след един месец броят на двойките зайци може да се намери по формулата:
Тази зависимост се нарича рекурентна връзка . Думата „рекурсия“ означава връщане назад (в нашия случай връщане към предишни резултати).
По условие и , след това по отношение имаме: , , и т.н., .
Определение 1:Извикват се номерата Числата на Фибоначи . Това е добре известна поредица от числа в математиката:
1, 1, 2, 3, 5, 8, 13, 21, ...
В тази последователност всяко следващо число е сбор от двете предходни числа. И във връзката на повторение следващият член също се намира като сбор от двата предходни члена.
Нека установим връзка между числата на Фибоначи и комбинаторния проблем. Да кажем, че трябва да намерим редица последователности, състоящи се от нули и единици, в които няма две единици подред.
Нека вземем всяка такава последователност и съпоставим чифт зайци с нея съгласно следното правило: единиците съответстват на месеците на раждане на една от двойките „предци“ на тази двойка (включително оригиналната), а нулите съответстват на всички останали месеца. Например, последователността установява такова „генеалогия“ - самата двойка се появява в края на 11-ия месец, родителите й в края на 7-ия месец, „дядото“ в края на 5-ия месец и „великият -дядо” в края на 2-рия месец. Първоначалната двойка е криптирана с последователността. В нито една последователност не могат да стоят две единици в един ред - двойка, която току-що се е появила, не може да роди потомство след месец. Очевидно различни последователности съответстват на различни двойки и обратно.
По този начин броят на последователностите с посочените свойства е равен на .
Теорема 1:Числото се намира като сбор от биномни коефициенти:. Ако – странно, тогава . Ако – дори, тогава . В противен случай: – цяла част от числото .
Доказателство:Наистина, е броят на всички поредици от 0 и 1, в които няма две 1-ци, съседни. Броят на такива последователности, съдържащи точно единици и нули, е равен на , след което варира от 0 до . Прилагайки правилото за сумата, получаваме тази сума.
Това равенство може да се докаже по различен начин. Да обозначим:
От равенството следва, че . Освен това е ясно, че. Тъй като и двете последователности и отговарят на рекурентната връзка, тогава , и .
Определение 2:Рекурентната връзка има поръчка , ако позволява изчисление чрез предишни членове на редицата: .
Например, е рекурентна връзка от втори ред и рекурентна връзка от 3-ти ред. Отношението на Фибоначи е отношение от втори ред.
Определение 3: Чрез решениерекурентна връзка е последователност, която удовлетворява тази връзка.
Ако е дадена рекурентна връзка от ред, тогава тя се удовлетворява от безкрайно много последователности, тъй като първите елементи могат да бъдат зададени произволно. Но ако първите елементи са дадени, тогава останалите членове се определят еднозначно.
Например, в допълнение към последователността 1, 1, 2, 3, 5, 8, 13, 21, ... обсъдена по-горе, съотношението на Фибоначи може да бъде удовлетворено и от други последователности. Например последователността 2, 2, 4, 8, 12,... е изградена по същия принцип. Но ако посочите началните членове (има 2 от тях в редицата на Фибоначи), тогава решението е еднозначно определено. Взети са толкова начални термини, колкото и редът на връзката.
Използвайки известни рекурентни отношения и начални членове, можем да изпишем членовете на редицата един след друг и по този начин да получим всеки от нейните членове. Но в много случаи нямаме нужда от всички предишни членове, а само от един конкретен член. В този случай е по-удобно да имаме формула за тия член на редицата.
Ще кажем, че определена последователност е решение на дадена рекурентна релация, ако при заместване на тази последователност връзката е идентично изпълнена.
Например последователността е едно от решенията на релацията: . Това е лесно да се провери с просто заместване.
Определение 4:Решението на рекурентна връзка от ‑ти ред се нарича общ , ако зависи от произволни константи, променяйки които, може да се получи всяко решение на тази връзка.
Например за релацията общото решение ще бъде .
Всъщност е лесно да се провери, че това ще бъде решение на нашата връзка. Нека покажем, че всяко решение може да бъде получено в тази форма. Нека бъдат произволни.
Тогава ще има и такива, които
Очевидно за всяко , системата от уравнения има единствено решение.
Определение 5:Рекурентната връзка се нарича линеен , ако е написано във формата:
където са числените коефициенти.
Най-общо казано, няма общи правила за решаване на произволни рекурентни отношения. Съществуват обаче общи правила за решаване на линейни рекурентни отношения.
Нека първо разгледаме връзката от 2-ри ред.
Решението на тази връзка се основава на следните твърдения.
Теорема 2:Ако и - са решение на дадена рекурентна връзка от 2-ри ред, тогава за всякакви числа и последователността също е решение на тази връзка.
Теорема 3:Ако числото е корен на квадратно уравнение, тогава последователността е решение на рекурентната връзка.
От теореми 2, 3 следва следното правило за решаване на линейни рекурентни отношения от 2-ри ред.
Нека е дадена рекурентна връзка.
1) Да съставим квадратно уравнение, което се нарича Характеристика за дадено съотношение. Да намерим всичкокорени на това уравнение (дори многократни и сложни).
2) Нека създадем общо решение на рекурентната връзка. Структурата му зависи от вида на корените (те са еднакви или различни).
а) Ако тази връзка има две различни корении , тогава общото решение на връзката има формата .
Наистина, от теоремите 2, 3 следва, че - решение и система от уравнения
Има едно единствено решение, т.к като се има предвид, че .
Например за числата на Фибоначи имаме . Характеристичното уравнение има формата: . Решавайки последното уравнение, получаваме корените:, .
Ако всички корени на характеристичното уравнение са различни, тогава общото решение има формата: .
Ако, например, този корен съответства на решенията:
на тази рекурентна връзка. В общото решение този корен съответства на частта .
Например, решаване на рекурентната връзка:
Съставяме характеристично уравнение от вида: .
Корените му са... Следователно има общо решение.
Този метод се състои в това, че решението на комбинаторна задача с n обекта се изразява чрез решение на подобна задача с по-малък брой обекти, като се използва определено отношение, наречено рекурентно. За поредица от елементи u0 , u1 , … un , … върху полето от комплексни числа C се казва, че удовлетворява рекурентна връзка от ред k, ако
където a1, …, ak са коефициенти от C. Отношения от този тип възникват естествено при решаване на комбинаторни задачи.
Пример. Нека има последователност от позиции, номерирани с 1, 2, ... , n, ... и в началния момент обектът е на 1-ва позиция. С едно движение предметът се придвижва напред с 1 и 2 позиции. Намерете броя на начините да стигнете до n-та позиция.
♦ Нека un е числото, което ни интересува. Ясно е, че u2 = 1, u3 = 2. След това разделяме всички начини за влизане в позиция номер n на два класа: тези, при които на последната стъпка обектът се премества с 1 стъпка и тези, при които се премества с 2 стъпки. Ясно е, че в първия случай имаме un-1 опции, във втория случай un-2 опции. Следователно имаме
Полиномът P(x) се нарича Характеристиказа линейна рекурентна връзка (2). Обърнете внимание, че всяка повтаряща се последователност от k-ти ред се определя еднозначно чрез определяне на нейните първи k члена.
Нека λ е коренът на характеристичния полином P(x).
Теорема 1. Последователността u0, u1, … un, …, където un = cλ n, c е произволна константа от C, удовлетворява линейната рекурентна връзка (2).
♦ Замествайки тези стойности un, n = 0, 1, … в (2), имаме
cλ n - a1 cλ n-1 - a2 cλ n-2 - … - ak cλ n-k = cλ n-k (λ k - a1 λ k-1 - … - ak ) ≡ 0. ♦
Теорема 2. Нека последователностите un, vn, n = 0, 1, ... удовлетворяват линейната рекурентна връзка (2). Тогава последователността има това свойство.
rn , n = 0, 1, … , където rn = α un + β vn , n , α, β са произволни константи от C.
♦ Доказателството е очевидно. ♦
Теорема 3. Нека λ 1, …, λ k са прости (т.е. некратни) корени на характеристичния полином P(x) за последователност (2).
Тогава общото решение на тази рекурентна връзка има формата
където c1, …, ck са подходящи константи от C.
♦ Съгласно предишното забелязваме, че редицата un, n = 0, 1, … е решение на релация (2). За да се докаже, че всяко решение има формата (5), е достатъчно да се покаже, че за произволна последователност vn, n = 0, 1, …, удовлетворяваща
(2), има константи c1,...,ck, такива че un = vn, n. За това е достатъчно v0 = u0, v1 = u1, …, vk-1 = uk-1. Нека разгледаме тези условия
спрямо c1, c2, …, ck. Детерминантата на тази система е детерминантата на Вандермонд и според (7, стр. 118).
= ∏ (λi − λj ) ≠ 0 |
||||||
λ k− 1 |
λ k− 1 |
L λ k − 1 |
||||
съгласно предположението за корените λ 1, ..., λ k. Тук следва изявлението. ♦ Като пример, разгледайте рекурентната връзка (3). Имаме характерен полином
P(x) = x2 - x -1
Корените му са равни на λ 1 = 1 + 2 5, λ 2 = 1 − 2 5. Общото решение има формата
u n = c 1 1+ 2 5 n + c 2 1− 2 5 n
Система от уравнения за константи c1, c2: c1 1 + 2 5 + c2 1 − 2 5 = 1
1− 5 |
||||||||||
Къде да вземем c1 |
C2 = - |
|||||||||
Нека сега λ е коренът на кратността r на характеристичния полином P(x). Подобно на предишния се доказва
Теорема 4. Последователности c1 λ n , c2 nλ n ,K , cr n r − 1 λ n , n = 0, 1, … за про-
произволни константи c1 , … , cr от C отговарят на съотношението (2).
Теорема 5. Нека характеристичният полином P(x) има корени λ 1 , … , λ s от кратности r1 , … , rs (r1 + … + rs = k) . Тогава общото решение на рекурентната връзка
Нека посочим още едно полезно свойство на линейните рекурентни отношения. Теорема 6. Нека имаме връзката
un = a1 un-1 + … + ak un-k
с начални условия u1 , … , uk . Тогава връзката е валидна за всички n ≥ k
а 1 а 2 |
A k n − k uk |
||||||||||
u k− 1 |
u n− 1 |
||||||||||
u n− k+ 1 |
|||||||||||
♦ Доказателство чрез индукция по n. За n = k равенството (8) е валидно. Нека е вярно за n. За n + 1 имаме
а 1 а 2 |
A k n + 1 − k uk |
|||||||||||||||||||
u k− 1 |
||||||||||||||||||||
0 . . 1 0 |
||||||||||||||||||||
а 1 а 2 |
a k a 1 a 2 |
a k n − k uk |
||||||||||||||||||
u k− 1 |
||||||||||||||||||||
а 1 а 2 |
u n+ 1 |
|||||||||||||||||||
u n− 1 |
||||||||||||||||||||
1 0 un − k + 1 |
u n− k+ 2 |
|||||||||||||||||||
В повечето случаи обаче, когато се изучават проблеми с изброяването, възникват нелинейни рекурентни отношения, за разрешаването на които се използват специфични техники. Някои от тях ще бъдат обсъдени допълнително. Нека дадем важен пример за нелинейна рекурентна връзка.
Теорема 7. Нека C(n, k) е броят на пермутациите на набор от n елемента, имащ точно k цикъла. Тогава е честно
C(n - 1, k - 1) + (n - 1)C(n - 1, k) |
||
1, C(0, 1) = 0 |
♦ Нека разделим множеството от пермутации на множеството X = (1, 2, … n,) с точно k цикъла на два класа - пермутации, в които елемент n се съдържа в единичен цикъл, и пермутации, в които елемент n е в цикъл с дължина l, l > 1. В първия случай броят на заместванията съвпада с броя на заместванията на множеството X′ = (1, 2, …, n - 1), имащо k - 1 цикъла, т.е. C(n - 1, k - 1). Във втория случай, като премахнем елемент n, получаваме
Разглеждаме заместването на множеството X′ = (1, 2, …, n - 1) с k цикъла, чийто брой е равен на C(n - 1, k). Нека сега разберем по какъв брой начини можем да добавим елемент n към заместване от степен n - 1 с k цикъла. Ако има цикъл с дължина i, тогава това може да се направи по i начини. Общият брой пътища е равен на i1 + … + ik, където i1, …, ik са дължините на циклите на заместване. Въпреки това i1 + … + ik = n - 1. Това означава, че броят на заместванията от втория клас е равен на
(n - 1)C(n - 1, k). От тук получаваме (9). ♦
Получените числа C(n, k) са свързани с известните числа на Стърлинг от първи вид sn,k, които се дефинират, както следва:
sn,k = (- 1)n+k C(n, k)
Ето таблица с първите няколко стойности на числата sn,k.
s n,1 |
s n,2 |
s n,3 |
s n,4 |
s n,5 |
||
Таблица Числа на Стърлинг от първи вид
