Denombrement et recurrence

par **Anonyme** » 12 Juin 2009, 14:10

Bonjour! Deuxième avertissement.... Attention

problème:

on désigne par An le nombre de chaines de n caractères de l'alphabet {A,B,C,D,........,Z}qui ne contiennent pas le sous ensemble DM.

1. Démontrer la relation de récurrence : An = 26*An-1 - An-2 ? :mur:

2. déterminer les conditions initiales et résoudre la relation de récurrence pour la formule explicite de An.

mon raisonnement est le suivant :
en 1. je détermine le nombre A'n : le nombre de chaines de n caractères de l'alphabet qui est: 26 puissance n et je cherche à enlever le nombre de fois qui peut apparaitre D suivi de M. :marteau:

on peut voir dans le sens ou on commence à l'ordre 1 i.e on a A1=26, puis pour n=2, on a A2=26*26 - 1, en suite n = 3, on a A3 = 26*26*26 - 2 parce que on a les cas: DMD, DDM uniquement.
c'est juste un aperçu, j'aimerai avoir vos idées(résoudre ce problème :doh: )
Merçi la question 2 est facile

par **Dominique Lefebvre** » 12 Juin 2009, 14:54

Bonjour,

Il me semble urgent que tu ailles lire le règlement du forum afin de t'imprégner de l'esprit du forum...

par **yos** » 12 Juin 2009, 16:26

Bonjour.

Je crois que tu saisis mal le problème : il faut d'abord établir la formule de récurrence (question 1) et ensuite trouver une formule explicite (question 2).
Toi tu pars d'emblée sur une formule explicite, ce qui est sûrement faisable dans ce cas précis mais pas simple le plus souvent.

En calculant

on prend les chaînes de (n-1) caractères qu'on complète à droite par un n-ème caractère parmi A,B,...,Z. Toutes ces chaînes sont admises sauf celles qui terminaient par D et pour lesquelles on a mis un M à droite : cela fait peu de chaînes en trop. Pour dénombrer ces dernières, on peut les voir comme des chaînes de (n-2) caractères (ne renfermant pas la séquence DM) suivies de la la séquence DM. Il y en a donc

.

Si quelqu'un parvient à être plus clair, qu'il se gêne pas car j'ai peur d'avoir été confus.

par **Anonyme** » 13 Juin 2009, 10:09

yos a écrit:Bonjour.

Je crois que tu saisis mal le problème : il faut d'abord établir la formule de récurrence (question 1) et ensuite trouver une formule explicite (question 2).
Toi tu pars d'emblée sur une formule explicite, ce qui est sûrement faisable dans ce cas précis mais pas simple le plus souvent.

En calculant on prend les chaînes de (n-1) caractères qu'on complète à droite par un n-ème caractère parmi A,B,...,Z. Toutes ces chaînes sont admises sauf celles qui terminaient par D et pour lesquelles on a mis un M à droite : cela fait peu de chaînes en trop. Pour dénombrer ces dernières, on peut les voir comme des chaînes de (n-2) caractères (ne renfermant pas la séquence DM) suivies de la la séquence DM. Il y en a donc .

Si quelqu'un parvient à être plus clair, qu'il se gêne pas car j'ai peur d'avoir été confus.

Bonjour,
C'est un plaisir d'avoir une idée.
c'est déjà un début de solution mais c'est pas clair vous ne faites expliquer la formule alors qu'il faut démontrer. C'est à dire comment faire pour arriver à cette formule.
Merci pour l'aperçu.

par **Anonyme** » 13 Juin 2009, 10:26

yos a écrit:Bonjour.

Je crois que tu saisis mal le problème : il faut d'abord établir la formule de récurrence (question 1) et ensuite trouver une formule explicite (question 2).
Toi tu pars d'emblée sur une formule explicite, ce qui est sûrement faisable dans ce cas précis mais pas simple le plus souvent.

En calculant on prend les chaînes de (n-1) caractères qu'on complète à droite par un n-ème caractère parmi A,B,...,Z. Toutes ces chaînes sont admises sauf celles qui terminaient par D et pour lesquelles on a mis un M à droite : cela fait peu de chaînes en trop. Pour dénombrer ces dernières, on peut les voir comme des chaînes de (n-2) caractères (ne renfermant pas la séquence DM) suivies de la la séquence DM. Il y en a donc .

Si quelqu'un parvient à être plus clair, qu'il se gêne pas car j'ai peur d'avoir été confus.

c'est déjà un début de solution mais c'est pas clair vous ne faites expliquer la formule alors qu'il faut démontrer. C'est à dire comment faire pour arriver à cette formule.
Merci pour l'aperçu.

par **fatal_error** » 13 Juin 2009, 11:49

Salut,

une autre manière pour trouver le resultat 2.
On suppose qu'a

, on a un mot correct (pas de DM)
pour construire

, on a deux possibilités : soit le mot termine par D, soit par autre choses.
S'il termine par D, on a que 25 lettres possibles (et pas 26). Sinon, on a 26 choix possibles.
On déduit :

Maintenant, on peut affiner les resultats et connaitre quand le mot qu'on cree termine par D :

Ya plus qu'a resoudre le systeme

genre en diagonalisant etc...

enfin, je pense

par **yos** » 13 Juin 2009, 16:09

151282 a écrit:c'est déjà un début de solution mais c'est pas clair vous ne faites expliquer la formule alors qu'il faut démontrer. C'est à dire comment faire pour arriver à cette formule.

Ah non, ma preuve est complète. Démontrer c'est expliquer pourquoi, et c'est exactement ce que j'ai fait. Après, on peut trouver ma prose médiocre, mais pas me dire que c'est pas une démo. Tu dis ça parce que j'ai pas mis assez de formules??

par **Anonyme** » 17 Juin 2009, 17:15

yos a écrit:Ah non, ma preuve est complète. Démontrer c'est expliquer pourquoi, et c'est exactement ce que j'ai fait. Après, on peut trouver ma prose médiocre, mais pas me dire que c'est pas une démo. Tu dis ça parce que j'ai pas mis assez de formules??

bonsoir,
Merci pour l'explication, excuses moi pour avoir dire que c'est pas une demo mais là tu t'emportes vite.
du calme et saches que j'ai tiré quelques choses de tes explications. :++:

Denombrement et recurrence

Denombrement et recurrence

Qui est en ligne