Antal följder

Hej!

Jag har en uppgift som lyder "Bestäm antalet följder av längd n som bara innehåller symbolerna *, ? och / och inte innehåller två * i rad".

Jag har tänkt att det går att lösa med en rekursionsekvation och jag har fått fram följande.

$L å t N_{n} v a r a a n t a l e t f ö l j d e r s o m u p p f y l l e r k r a v e t o v a n m e d l ä n g d n . D å ä r N_{1} = 3, N_{2} = 8 o c h N_{3} = 22$

$M a n k a n s e d e t s o m f ö l j a n d e . H_{n + 1} = 2 H_{n} + f (n) f ö r n å g o n f u n k t i o n f, d ä r f (n) > 0 \forall n \in ℕ \ {0} E f t e r s o m a t t m a n k a n a l l t i d p l a c e r a e t t ? e l l e r e t t / f r a m f ö r a l l a e l e m e n t i f ö r e g å e n d e f ö l j d .$

$A l t e r n a t i v t k a n d e t k a n s k e s k r i v a s p å f o r m e n H_{n + 1} = 3 H_{n} - f (n) f ö r n å g o t a n n a t f, d ä r f (n) > 0 \forall n \in ℕ \ {0}$

Någon klipsk observation eller lösning uppskattas!

Hör det till någon kurs? Kanske kan peka åt rätt typ av metoder isf. Eller bara någon kul lösning?

Den här borde funka om man har miniräknare att upphöja matrisen med.

Den är från en kurs i komplex analys på kapitlet rekursionsekvationer. Jag förstår inte riktigt din lösning. Var kommer den ifrån?

Det är en markovkedja, så typ sannolikhetslära/diskmatte/linalg, beror nog helt på var man läser. Är det något du känner igen?

Men då misstänker jag att du ska använda typ z-transform? Är inte så bra på det..

Nja, dit är jag inte riktigt. Det är bara meningen att jag skell ställa upp en rekursionsekvation och lösa den.

Det här var ju kul :) Testade mig fram lite och tror ev jag kom fram till något. Finns säkert smidigare sätt dit men jag tänkte ungefär såhär

Låter rimligt, tänkte inte på att rekursionsekvationen skulle vara av högre grad. Då blir svaret korrekt när jag löst ekvationen. Tack så mycket!

Svara

Visa senaste svar