Problème de récurrence

[Dylaa2n]

Bonjour,

Je coince un petit peu pour trouver une équation de récurrence à ce problème :

Des véhicules sont rangés les uns derrière les autres, en ligne droite. Une moto occupe une place et une auto occupe deux places. De combien de façons différentes peut-on ranger des autos et des motos dans une file de n places, sans laisser aucun emplacement vide? On ne tient pas compte de l'identité des véhicules, mais uniquement de leur type : auto ou moto.

Comment trouver l'équation de récurrence de ce problème, si on nous donne comme indice qu'il s'agit d'une équation de récurrence de deuxième ordre?

Merci

[paquito]

considérons une file de n places, si le dernier est une moto il ya façons d'occuper les n-1 premières places, et si le dernier est une voiture, il y a façons d'occuper les n-2 premières places, d'où:



On convient que (il n'y a qu'une façon de ranger 0,véhicule, c'est de ne rien faire), (une moto) et (moto-moto ou voiture); on retrouve la suite de Fibonacci.

Problème analogue: combien y a t'il de façons de vider un tonneau de n litres avec un seau d'un litre et un de 2 litres, ou bien

combien y a t'il de façons de monter un escalier de n marches en montant soit une marche soit deux marches

[Dylaa2n]

considérons une file de n places, si le dernier est une moto il ya façons d'occuper les n-1 premières places, et si le dernier est une voiture, il y a façons d'occuper les n-2 premières places, d'où:



On convient que (il n'y a qu'une façon de ranger 0,véhicule, c'est de ne rien faire), (une moto) et (moto-moto ou voiture); on retrouve la suite de Fibonacci.

Problème analogue: combien y a t'il de façons de vider un tonneau de n litres avec un seau d'un litre et un de 2 litres, ou bien

combien y a t'il de façons de monter un escalier de n marches en montant soit une marche soit deux marches

Merci beaucoup pour la réponse claire et complète! :happy2: