Koja je formula povratka za L_n? L_n je broj nizova (a_1, a_2, ..., a_n) s riječima iz skupa {0, 1, 2} bez susjednih 0 i 2.

Koja je formula povratka za L_n? L_n je broj nizova (a_1, a_2, ..., a_n) s riječima iz skupa {0, 1, 2} bez susjednih 0 i 2.
Anonim

Odgovor:

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

Obrazloženje:

Prvo moramo pronaći # L_1 # i # L_2 #.

# L_1 = 3 # jer postoje samo tri niza: #(0) (1) (2)#.

# L_2 = 7 #, kao i svi nizovi bez susjednih 0 i 2

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

Sada ćemo pronaći ponavljanje # L_n # # (N> = 3) *.

Ako se niz završi #1#, nakon toga možemo staviti bilo koju riječ.

Međutim, ako se nizovi završavaju #0# možemo samo staviti #0# ili #1#.

Jednostavno, ako žice završavaju #2# možemo samo staviti #1# ili #2#.

pustiti #P_n, Q_n, R_n # biti broj bez žica #0# i #2# u susjednim položajima i to završava u #0,1,2#, respektivno.

# L_n, P_n, Q_n # i # R_n # slijedite ponavljanje:

# 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)

Ukratko (ii), (iii) i (iv) možete vidjeti za svaki #N> = 2 #:

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

# = 2 (P_n + Q_n + R_n) + Q_n #

# = Boja (plava) (2L_n) + boja (crvena) (L_ (n-1)) * (koristeći (i) i (iii))