Qual è la formula di ricorrenza per L_n? L_n è il numero di stringhe (a_1, a_2, ..., a_n) con le parole dall'insieme {0, 1, 2} senza nessuna adiacente 0 e 2.

Risposta:

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

Spiegazione:

Per prima cosa dobbiamo trovare # # L_1 e # # L_2.

# L_1 = 3 # come ci sono solo tre stringhe: #(0) (1) (2)#.

# L_2 = 7 #, come tutte le stringhe senza adiacenti 0 e 2

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

Ora stiamo andando a trovare la ricorrenza di # # L_n # (N> = 3) #.

Se la stringa finisce in #1#, possiamo mettere qualsiasi parola dopo.

Tuttavia, se le stringhe finiscono in #0# possiamo mettere solo #0# o #1#.

Similare, se le corde finiscono dentro #2# possiamo mettere solo #1# o #2#.

Permettere #P_n, Q_n, R_n # essere il numero di stringhe senza #0# e #2# in posizioni adiacenti e che finisce in #0,1,2#, rispettivamente.

# L_n, P_n, Q_n # e # # R_n seguire le ricorrenze di seguito:

# L_n = p_n + Q_n + R_n # (io)

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

Riassumi (ii), (iii) e (iv) puoi vedere per ogni # n> = 2 #:

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

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

# = Colore (blu) (2L_n) + colore (rosso) (L_ (n-1)) # (usando (i) e (iii))