Besoin d'indication pour ces exercices

bonjour à tous les membres du forum! et merci d'avance à ceux qui prendront le temps de lire !

jai cet exercice dont je ne sais pas comment démarrer!

Soit An le nombre de chaines le nombre binaires de longueur n qui contiennent deux "0" consécutifs.
1- trouver une relation de recurrence pour An
2- quelles sont les conditions initiales pour la recurrence?
3- combien de chaines binaires de longueur 7 contiennent deux "0" consecutifs

Merci d'avance

Bonjour,
Merci pour la participation, et bienvenu au forum.

Je reprends l'énoncé:
Soit An le nombre de chaines de nombre binaires ==> qu'est-ce qu'une chaine de nombre binaire?
Est-ce que tu veux dire simplement "An le nombre de nombre binaires" ?
On va supposer que c'est ça ce que tu veux dire...

et puis, est-ce que les chaines contiennent une seule séquence de "00"?
Par exemple, les chaines suivantes "1000" et "100100" devrait-elle être prise en compte...


En attendant des réponses de ta part... essaie de commencer par voir le comportement de la suite An pour les premiers termes n=1..4,


Prenons quelques exemples pour différents "n":
n=01, alors, A(01)=0
n=02, alors, A(02)=1, c'est le nombre "00" zéro en binaire.
n=03, alors, A(03)=3, puisque la liste des chaines est {000,001,100}
n=04, alors, A(04)=7, puisque la liste des chaines est {0000,0001,0010,0011,1000,1001,1100}

ça rappelle un peu le dénombrement...

Merci Nabil pour la réaction je pense que j'ai mal redigé l'énoncé
Soit An le nombre de chaines binaires de longueur n qui contiennent deux "0" consécutifs.
1- trouver une relation de recurrence pour An
2- quelles sont les conditions initiales pour la recurrence?
3- combien de chaines binaires de longueur 7 contiennent deux "0" consecutifs
Je reprends l'énoncé:
Soit An le nombre de chaines de nombre binaires ==> qu'est-ce qu'une chaine de nombre binaire?
Une chaine binaire ici est une suite de "0" et de "1", ainsi elle peut avoir une longueur n = au nombre de zero et de un qui ont constitué la chaine!
Maintenant parmi les chaines binaires de longueur n il y'en dont on peut y trouver deux zero consécutifs! a mon avis qu'il yait 2 ou 3 séquences de zero consecutifs importe peu, pourvu qu'il y'en ait!
Je pense avoir apporter les précisions !
Je vois les premiers essais mais jusque là je ne vois aucune conjecture
Merci encore pour la participation

Bonh ... une relation de récurrence entre A(n) et A(n+1) ... je ne vois pas clairement.

Voilà un exemple de chemin bloquant:

Soit E(n) l'ensemble des nombres binaires de longueur "n" vérifiant la condition de l'exercice.
Si on prend un élément X(i,n) de E(n) et l'on veut construire à partir de ce nombre un élément de E(n+1), alors, il suffit d'insérer un zéro à l'extrémité droite/gauche de la chaine contenant au moins 2 zéros qui figurent dans le nombre X(i,n).

Exemple:
Soit X(i,6) = 110001: un élément de E(6).
Alors, à partir de X(i,6) on peut construire 2 nouveaux nombres de E(7):
X(i,7) = 1100001 et X(j,7) = 1100001.
Donc, on peut penser que E(7) peut être construit en entier à partir de E(6).

ça reste à prouver! (j'en doute!)

Où est-ce que tu en es maintenant ?

Bonjour et merci encore pour le suivi!
voila la relation de recurrence mais cest la conjecture

A(n) = 2A(n-1) + 2^(n-3) - A(n-3)

luisroni a écrit:Bonjour et merci encore pour le suivi!
voila la relation de recurrence mais cest la conjecture

A(n) = 2A(n-1) + 2^(n-3) - A(n-3)

Dès que je trouve un peu plus de temps, je vais réfléchir plus sérieusement au problème. C'est passionnant.

luisroni a écrit:Bonjour et merci encore pour le suivi!
voila la relation de recurrence mais cest la conjecture

A(n) = 2A(n-1) + 2^(n-3) - A(n-3)

Bonjour,

Les premiers termes de la suites A(n) ?