Exercice combinatoire

[ArtyB]

Bonsoir,

Voici un exercice que je trouve intéressant mais que je ne sais pas du tout par quel bout le prendre:

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 ) ou (0,1). En désignant par la lettre H un déplacement horizontal et par V un déplacement vertical, tout chemin peut être vu comme un mot écrit sur l'alphabet {H,V}. l'ensemble des ces mots sera noté E(m,n) son cardinal e(m,n) et par convention on pose e(0,0)=1.

1) Quelle est la longueur d'un mot de E(m,n) ? Combien de fois un tel mot contient-il la lettre H ? Et la lettre V ?
2) En déduire une expression e(m,n) en fonction de m et n.
3) Soient et . Dans , combien y a-t-il de façons d'aller de à par un chemin où, à chaque pas, l'une des coordonnées augmente d'une unité ?

[chan79]

Salut
Prends un exemple simple comme (m,n)=(4,2)
Fais un dessin et énumère tous les "mots".

[Ben314]

Salut,
J'aurais tendance à dire que là, tu "pousse un peu le bouchon".
Prend du papier à carreaux et regarde comment ça marche sur un exemple : regarde quelques trajets (voire tous) allant de (0,0) à (3,4) en faisant uniquement des "1 cran à droite" ou des "1 cran au dessus".
Tu devrait rapidement constater que tout ces trajet ont des trucs en communs (c.f. fin de la question 1 qu'il vaut sans doute mieux faire avant le début si on n'y vois vraiment rien)

EDIT : grilled...

[ArtyB]

Pardon je me suis mal exprimé, j'ai "remarqué" les réponses mais ne sait pas comment les démontrer de manière rigoureuse.

1) Pour e(m,n) il y a m V et n H et la longueur est m+v mais est-ce qu'il y a un moyen de le démontrer ?
2) Pour cette question c'est comment combiner n H et m V dans un ensemble de taille m+n c'est donc
e(n,m)=
3) Pour la dimension c'est plus dur de se le représenter haha

EDIT: j'ai oublié le facteur dans l'expression de e(n,m)
C'est:
e(n,m)=

[zygomatique]

salut

1/ si P est le point de coordonnées (m, n) alors m + n est le demi-périmètre du rectangle de diagonale [OP] ....

2/ je ne comprends pas : choisir (quand faire) les m déplacements horizontaux c'est choisir (quand faire) les n déplacements verticaux ....

on a m + n déplacements horizontaux ou verticaux

je choisis m entiers parmi les m + n (non nuls) pour lesquels je fais un déplacement horizontal ....

il me reste m + n - m = n déplacements je choisis ces n entiers pour faire les n déplacements verticaux ....

on généralise à déplacements dans N^k

je choisis n_1 entiers au hasard parmi les N premiers non nuls pour faire les déplacements suivant la première coordonnée

je choisis n_2 entiers parmi les N - n_1 restants pour faire les déplacements suivant la deuxième coordonnée

je choisis n_3 entiers parmi les N - n_1 - n_2 restant pour faire les déplacements suivant la troisième coordonnée

.....

[ArtyB]

Merci de ta réponse zygomatique.
Je ne comprends pas très bien ce que tu veux dire pour la dimension .
Est-ce que l'on aurait ?

où est "b parmi a"

[Robot]

Nan, tu as lu de travers, et tu emploies des sommes au lieu de produits.

[ArtyB]

Qu'ai je lu de travers ?
J'ai oublié le facteur 1/2 dans ma réponse pour la dimension 2.
Et pour la dimension k je pense que c'est un facteur 1/k qu'il faut rajouter.
Concernant les produits je ne vois pas trop pourquoi mettre des produits dans les parenthèses.

[Ben314]

J'ai pas tout lu en détail, mais j'ai l'impression que personne ne t'a dit que ça

e(n,m)=

c'est toujours faux.
Et les une des deux raisons pour lesquelles c'est assez clairement faux est précisément celles évoquées par Robot ci dessus : vu ton problème, il n'y a rien à "sommer" : ne jamais oublier de revenir au C.P.. Faire la somme de deux trucs, c'est compter combien il y a d'élément dans un ensemble composé de deux types d'éléments différent : 3 pommes + 5 bananes = 8 fruits. Où voit tu des "éléments de type différents" ici ?
La deuxième raison, c'est qu'il n'y a aucune raison qu'il y ait deux coefficients binomiaux dans ton truc : une fois que tu as chois à quels endroit tu mettait des H, tu n'as évidement plus aucun choix à faire vu que tout le reste ça va être des V.

[ArtyB]

Je ne comprends pas pourquoi cela est faux, j'ai fait plusieurs tests et ça semblait marcher.
Pourquoi n'y a-t-il rien à sommer ?
On est d'accord que e(m,n) c'est le nombre de chemins possibles ?

NB: Pour la somme des éléments on peut aussi faire des sommes d'éléments de même type: 2 pommes + 2 pommes=4 pommes...

[ArtyB]

Ok en fait c'est stupide, on aura toujours (n parmi n+m)=(m parmi n+m) ici d'où ce que je faisais donne le bon résultat puisque je multiplie par deux puis divise par deux. Mais c'était un raisonnement idiot que je faisais.
En fait le nombre de chemins possibles, ie le nombre d'arrangements possibles de n parmi n+m c'est simplement n parmi n+m.
D'où l'on a e(m,n)=

[Ben314]

Effectivement, tu as parfaitement raison sur le fait que le résultat est juste (j'ai même pas fait gaffe que 1/2(A+A)=A : la honte...)
Mais effectivement (aussi...), c'était une façon on ne peut plus bizarre de donner le résultat vu que ce n'est pas du tout comme ça qu'on l'obtient mais comme tu le dit juste au dessus.

Bon, bref, pour k>2 tu le vois comment le truc ?

[ArtyB]

Dans le cas où l'on se situe dans la dimension k avec déplacements (en reprenant les notations de zygomatique).
Si je fais mes déplacements selon la premiere coordonnée alors il me reste déplacements possibles etc jusqu'à ce que l'on arrive à et le k-ème déplacement est déterminé.
Donc ?

[Ben314]

Non, c'est pas ça.
O.K. pour le début : tu commence par choisir n1 élément parmi les N (qui sont les "étapes" où c'est la première coordonnée qui va faire "+1").
O.K. pour la deuxième étape ou tu choisi n2 élément parmi les N-n1 restant.
Pour la 3em -> ???

(et c'est bien un produit qu'il faut faire entre ces différents coefficients binomiaux vu qu'on a un arbre avec des embranchements à chaque étape)

Indication : ton résultat final, écrit le uniquement à l'aide de factorielles. Il va être "extrêmement simple" (et il porte un nom)

[ArtyB]

Je voulais dire qu'au moment de choisir mon k-ème élément il me reste mea culpa.

Comment ça l'écrire sous forme de factorielle ? Je sais que les coefficients binomiaux peuvent s'écrire sous forme factorielle mais je ne sais pas trop comment on peut écrire une quelconque forme factorielle pour compter le nombre de déplacements ici

[Ben314]

Ecrit ton e(n1,n2,...,nk) à l'aide des coeff. binomiaux (éventuellement, plutôt que d'utiliser le symbole "produit", écrit le avec des points de suspension pour mieux visualiser le truc)
Ensuite remplace tes coeff. binomiaux par leurs expressions à l'aide de factorielles et regarde ce que ça donne...

[ArtyB]

On a
Ce qui en termes de factorielles donne:

)
=
NB: Je ne sais pas pourquoi mais à chaque fois que j'essaye d'écrire ma fraction finale cela bug, du coup je suis obligé de faire deux ensembles latex que je ne peux pas concatener...

[zygomatique]

enfin ça semble bon ....

mais bon pourquoi écrire compliqué quand on peut simplifier ...

Ben314 t'a dit qu'il y a plein de simplification ....

en particulier si N = n_1 + n_2 + ... + n_k alors N - n_1 - n_2 - ... - n_k = .... ?

[ArtyB]

Oui en effet si alors d'où l'on a:

[Ben314]

Ca commence à ressembler au résultat "classique", mais il y a quand même un "léger" problème : je te rappelle que le résultat en question, c'est le nombre de blablabla.... et qu'en conséquence, ça serait "mieux" que le résultat soit un entier naturel or 1/(n1!n2!...nk!) ça sonne pas trop "entier naturel".
Bref, tu as oublié un truc (au numérateur forcément).

Et a titre de "culture générale", les bazars en question, ça s'appelle des coefficients multinomiaux et c'est une généralisation très naturelle des coefficients binomiaux.