Mots de longueur n sur un alphabet

[Zweig]

Bonjour,

Combien de mots de longueurs sur l'alphabet sont tels que la différence entre deux voisins est d'au plus 1 ?

[lapras]

salut,
sans faire les calculs (équation caractéristique) :
Notons a_n le nombre de mot vérifiant l'énoncé se finissant par 1.
b_n le nbre de mots finissant par un 0.
c_n le nbre de mots finissant par un 2.
On a b_n = c_n (évident).
et, à partir d'un mot se finissant par 0, on ajoute un 1. De même avec un mot se finissant par 2 on ajout un 1.
enfin, a partir d'un mot se terminant par 1, on ajoute un 1.
D'où :


à partir d'un mot se terminant par un 1, on obtient un mot se terminant par un 0. A partir d'un mot se terminant par un 0, on obtient un mot se terminant par un 0.
d'où



On obtient ensuite des relations avec uniquement des a_n, uniquement des b_n, puis le nombre total de mot est