Exercice combinatoire 2

[ArtyB]

Bonsoir dans le même genre que l'exercice de combinatoire précédent (voir http://www.maths-forum.com/superieur/exercice-combinatoire-t171501.html), ici on rajoute les déplacements en diagonale:

Etant donnés des entiers naturels n et m on s'intéresse au nombre de façons d'aller dans N² de (0,0) à (m,n) par un chemin où à chaque pas on se déplace de (1,0 ), (0,1) ou (1,1) . En désignant par la lettre H un déplacement horizontal, par V un déplacement vertical et par D un déplacement diagonal, tout chemin peut être vu comme un mot écrit sur l'alphabet {H,V,D}. l'ensemble des ces mots sera noté D(m,n) son cardinal D(m,n) et par convention on pose d(0,0)=1.

1. Lorsque m, n>=1, exprimer d(m,n) en fonction de d(m-1,n), d(m,n-1) et d(m-1,n-1).
2. Combien de fois un mot de D(m,n) peut il contenir la lettre D au minimum et au maximum ?
3. Combien de fois un mot de D(m,n) contenant d fois la lettre D contient-il la lettre H, et la lettre V ? EN déduire le nombre de mots de D(m,n) contenant d fois la lettre D.
4. Prouver que, pour tous m, n entiers naturels, on a :


On considère qui à tout mot de D(m,n) associe celui obtenu en remplaçant chaque lettre D par HV. (par exemple .
5. Quelle est l'image directe de l'ensemble D(m,n) par ?
6.Combien d'antécédents par un mot de E(m,n) possédant d blocs de la forme HV possède-t-il ? (où E(m,n) est l'ensemble des mots pour les déplacements H et V seulement, pas D).
7.Quel est le nombre de mots de E(m,n) possédant d blocs de la forme HV ?
En déduire que, pour tous entiers naturels m, n on a :



1. On remarque facilement que d(m,n)=d(m-1,n)+d(m,n-1)+d(m-1,n-1) après quant à le démontrer de manière rigoureuse je ne sais pas trop encore une fois.

2. Un mot e D(m,n) peut ne pas contenir la lettre D, ie si on ne fait que des déplacements H et V. et il le contient au maximum min(m,n) fois.

3. Je dirai qu'il contient m+n-2d fois une lettre H ou une lettre V. Mais après quand à préciser pour H ou V cela me semble plus dur sauf à considérer séparément les cas m>n, n>m etc ?

5. C'est l'ensemble E(m,n).

6. J'ai remarqué que pour d=1,2,3 on a 2^d antécédents mais je ne sais pas si c'est vrai pour tous d ni comment le démontrer avec rigueur.

Pour les questions 4, et 7 je sèche totalement

[zygomatique]

salut

quand on travaille dans le plan il est souvent utile de faire un dessin pour regarder et voir ....


1/ il n'y a rien à prouver ... juste à traduire en mathématique le texte en français .... ce que tu as fait ....

2/ preuve ?

3/ comme je le disais au début un dessin peut aider ... on peut faire une translation de vecteur d(1, 1) = (d, d) de l'origine en le point P

si M est le point de cordonnées (m, n) il reste un rectangle de diagonale [PM] qu' on ne parcourt qu'avec des déplacements H ou V .... donc voir l'exercice précédent ....


qui est E(m, n) ?

[ArtyB]

Merci de ta réponse Zygomatique.

2. Un D peut toujours se réécrire HV ou VH donc on pourra toujours trouver un élément que l'on peut écrire sans D d'où le minimum=0.
Et pour le maximum, si D est de dimension (m,n) avec m>n alors on pourra faire n fois D puis après on devra faire des déplacements V et inversement si n>m.

3. Le rectangle de coins opposés P et M est de taille (m-d,n-d) et donc il contient m-d V et n-d H

E(m,n) est l'ensemble défini dans l'exercice précédent, lorsque l'on se refere au cas où il n'y a pas de déplacements diagonaux mais seulement H et V