Besoin d'indication pour ces exercices [Résolu]

luisroni · 05-08-2009 14:37:09

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

freddy · 12-08-2009 16:20:28

Bonjour,

je pressens que
[tex]A_0 = 0 \, A_1 = 0 \, A_2= 1 \, A_3= 2[/tex]

Mais ensuite, je pressens de l'imprécision dans l'énoncé : que deux 0 consécutifs, au moins deux 0 consécutifs ???

Bis bald

Dernière modification par freddy (12-08-2009 16:22:10)

thadrien · 12-08-2009 17:12:41

Pour ma part, j'ai compris au moins deux "0" consécutifs.

Quand tu as une chaine de longueur n+2, tu as trois cas :
- Soit elle commence par 1
- Soit elle commence par 00
- Soit elle commence par 01

Une fois que l'on a dit cela, la suite est plus facile.

freddy · 13-08-2009 10:49:02

thadrien a écrit :

Pour ma part, j'ai compris au moins deux "0" consécutifs.
Quand tu as une chaine de longueur n+2, tu as trois cas :
- Soit elle commence par 1
- Soit elle commence par 00
- Soit elle commence par 01
Une fois que l'on a dit cela, la suite est plus facile.

Hi,

je ne suis pas sûr. Par exemple, la chaine 10101011101100 satisfait à la condition de l'énoncé, ainsi que celle là 101010111001100 et 101010111011000 celle là. Je me trompe ?

Bb

Dernière modification par freddy (20-08-2009 09:48:36)

thadrien · 13-08-2009 11:22:35

freddy a écrit :

Hi,
je ne suis pas sûr. Par exemple, la chaine 10101011101100 satisfait à la condition de l'énoncé, ainsi que celle là 101010111001100 et 101010111011000 cell e là. Je le trompe ?
Bb

Non. Mais où est le problème ? Tes trois chaines vérifient le premier cas.

Je pense que cela serait plus clair si je postais l'intégralité de mon raisonnement, mais je laisse d'abord chercher un peu...

Dernière modification par thadrien (13-08-2009 11:24:06)

freddy · 13-08-2009 13:26:16

Salut thadiren,

as tu bien regardé dans le détail les 3 chaînes que j'ai construites ?

thadrien · 16-08-2009 16:25:21

Salut,

Bon, je pense que je serai plus clair si je poste l'intégralité de mon raisonnement.

Soit une chaîne de longueur n+2. Trois cas sont possibles, mutuellement exclusifs :

* Soit elle commence par 1
* Soit elle commence par 01
* Soit elle commence par 00

Dénombrons le nombres de chaines contenant 00 pour chacun des trois cas :

* Premier cas : [tex]A_{n+1}[/tex]
* Second cas : [tex]A_{n}[/tex]
* Troisième cas : [tex]2^n[/tex]

Donc [tex]A_{n+2} = A_{n+1} + A_n + 2^n[/tex].

L'idée de ce raisonnement, c'est que ni 1 ni 01 n'ont pour suffixe un préfixe de 00. Je pense être plus clair maintenant.

freddy · 19-08-2009 18:44:52

Salut,

je pense qu'il y a une petite erreur pour le troisième cas. On a :

[tex]A_n+1[/tex]

Par conséquent, la récurrence cherchée est :

[tex]A_{n+2} = A_{n+1} + 2A_n + 1[/tex] avec n>= 2

Et en particulier :

[tex]A_7 = 42[/tex]

Dernière modification par freddy (19-08-2009 19:25:32)

thadrien · 20-08-2009 07:59:02

Salut,

Est-tu vraiment sûr ? Il y a 2^n chaînes de longueur n+2 qui commencent par 00, et toutes contiennent 00.

Dernière modification par thadrien (20-08-2009 08:00:20)

freddy · 20-08-2009 09:43:43

Re,

en effet, astucieux !

pierre-paul · 20-08-2009 12:10:33

Bonjour,
Et si l'on comptait le nombre de chaines qui ne contiennent aucun couple 00 ?

thadrien · 25-08-2009 09:29:35

Salut,

Pourquoi pas. Il faut faire des essais : c'est cela qui fait avancer.

Forum de mathématiques - Bibm@th.net

#1 05-08-2009 14:37:09

Besoin d'indication pour ces exercices [Résolu]

#2 12-08-2009 16:20:28

Re : Besoin d'indication pour ces exercices [Résolu]

#3 12-08-2009 17:12:41

Re : Besoin d'indication pour ces exercices [Résolu]

#4 13-08-2009 10:49:02

Re : Besoin d'indication pour ces exercices [Résolu]

#5 13-08-2009 11:22:35

Re : Besoin d'indication pour ces exercices [Résolu]

#6 13-08-2009 13:26:16

Re : Besoin d'indication pour ces exercices [Résolu]

#7 16-08-2009 16:25:21

Re : Besoin d'indication pour ces exercices [Résolu]

#8 19-08-2009 18:44:52

Re : Besoin d'indication pour ces exercices [Résolu]

#9 20-08-2009 07:59:02

Re : Besoin d'indication pour ces exercices [Résolu]

#10 20-08-2009 09:43:43

Re : Besoin d'indication pour ces exercices [Résolu]

#11 20-08-2009 12:10:33

Re : Besoin d'indication pour ces exercices [Résolu]

#12 25-08-2009 09:29:35

Re : Besoin d'indication pour ces exercices [Résolu]

Pied de page des forums