Mikä on L_n: n toistuvuuskaava? L_n on merkkijonojen lukumäärä (a_1, a_2, ..., a_n), jossa on sanoja joukosta {0, 1, 2} ilman vierekkäisiä 0 ja 2.

Vastaus:

# L_1 = 3, L_2 = 7, L_ (n + 1) = 2L_n + L_ (n-1) "" (n> = 2) #

Selitys:

Ensin on löydettävä # L_1 # ja # L_2 #.

# L_1 = 3 # koska on vain kolme merkkijonoa: #(0) (1) (2)#.

# L_2 = 7 #, kuten kaikki merkkijonot ilman vierekkäisiä 0 ja 2 ovat

#(0,0),(0,1),(1,0),(1,1),(1,2),(2,1),(2,2)#

Nyt aiomme löytää toistumisen # L_N # # (N> = 3) #.

Jos merkkijono päättyy #1#, voimme sanoa sen jälkeen.

Jos jouset kuitenkin päättyvät #0# voimme laittaa vain #0# tai #1#.

Samanaikainen, jos jouset päättyvät #2# voimme laittaa vain #1# tai #2#.

Päästää #P_n, Q_n, R_n # olla merkkijonojen lukumäärä ilman #0# ja #2# vierekkäisissä asennoissa ja päättyy #0,1,2#, vastaavasti.

# L_n, P_n, Q_n # ja # R_n # seuraa seuraavia toistoja:

# L_N = P_n + Q_n + R n # (I)

#P_ (n + 1) = P_n + Q_n # (Ii)

#Q_ (n + 1) = P_n + Q_n + R_n #(# = L_N #) (iii)

#R_ (n + 1) = Q_n + R_n # (Iv)

Yhteenveto (ii), (iii) ja (iv) voit nähdä jokaiselle #n> = 2 #:

#L_ (n + 1) = P_ (n + 1) + Q_ (n + 1) + R_ (n + 1) #

# = 2 (P_n + Q_n + R n) + Q_n #

# = Väri (sininen) (2L_n) + väri (punainen) (L_ (n-1)) # (käyttäen (i) ja (iii))