Inscription / Connexion Nouveau Sujet
Dénombrements dans des chemins monotones
Bonjour,
Je ne comprend pas bien les dénombrements dans des chemins monotones. Pourriez vous m'aider pour cet exercice s'il vous plaît.
Enoncé:
Dans le plan rapporté au repère orthonormé (0,
,
), tous les points considérés sont de coordonnées entières.
Soit n
. On appelle chemin monotone à n pas d'origine A et d'extrêmité B, toute ligne polygonale définie par n+1 points: M0,M1,...,Mn-1,Mn avec:
M0=A, Mn=B et 
k[1,n] soit vecteur(Mk-1,Mk)=, soit vecteur(Mk-1,Mk)=
La valeur de vecteur(Mk-1,Mk) définit le kème pas. Tous les pas sont donc de longueur 1 car abs()=abs)=1 et c'est soit un pas horizontal à droite pour soit un pas vertical en haut pour .
1) Soit A un point du plan de coordonnées (x,y) et n un entier naturel.
a) Combien y a t il de chemins monotones à n pas d'origine A?
b) Soit un chemin monotone à n pas d'origine A qui possède globalement i pas horizontaux. Quelles sont alors les coordonnées de son extrémité (notée B)?
2) Soit A de coordonnées (x,y) et B de coordonnées (x',y'). On rappelle que (x,y) et (x',y') sont éléments de Z2.
a) A quelles conditions sur x, y, x', y', existe t-il au moins un chemin monotone d'origine A et d'extrêmité B?
b) Quels sont alors les valeurs du nombre de pas horizontaux? de pas verticaux?
3) Applications. Soit 
(-1,-2), A(7,8), B(1,3) et C (5,4).
a) Quel est le nombre de chemins monotones d'origine et d'extremité A?
b) Parmi ceux ci, combien passent par B, par C, par B et C, par B ou par C, ni par B ni par C.
4) Soit les chemins monotones d'origine 0 de coordonnées (0,0) et d'extremité M de coordonnées (n+m,p) (où n,m,p sont trois points entiers naturels)
a) Combien y-en-at-il qui passent par Q de coordonnées (n,k)?
b) En dénombrant de deux façons différentes les chemins monotones d'origine 0 et d'extremité M, retrouver une formule bien connue (laquelle?)
En vous remerciant,
Drazele
je vois que personne n'aime le dénombrement 
(je vous en veux pas, moi non plus j'aime pas ca 
)
J'aime le dénombrement et je ne pense pas être le seul...
1)a) Pour faire u nchemin monotone à n pas à partir d'un points, à chaque pas on choisit d'aller à droite ou à gauche, ce qui fait 2n possibilités.
1)b) On a fait n pas dont i horizontaux, donc n-i verticaux ; les coordonnées de B sont (x+i, y+n-i).
mince j'ai dit une bêtise l'autre fois :
1)a) Pour faire u nchemin monotone à n pas à partir d'un points, à chaque pas on choisit d'aller à droite ou à gauche,
je voulais dire : on choisit d'aller à droite ou en haut
Que dois-je (et aussi que devons-nous) comprendre ?que je suis nulle en dénombrement
que je suis nulle en dénombrement
Il y a des problèmes de dénombrement difficiles et d'autres simples, ce que tu dis n'est pas raisonnable. Je t'ai posé ces questions tout à l'heure :
As-tu compris ce qu'est un chemin monotone ? As-tu fait un dessin ?
... et tu n'as pas répondu...
Désolé pour le retard mais je n'ai pas internet à la maison...
Oui, j'ai fais un dessin et je crois avoir compris ce qu'est un chemin monotone.
Pour le nombre de chemins monotones à n pas d'origine A, j'ai compris pourquoi il est égal 2nen faisant des dessins pour n=1, n=2, n=3.
Si on pose A (x,y) et si on fait i pas horizontaux et qu'on a A comme origine, alors le nombre de pas verticaux est n-i, c'est à dire la totalité des pas n moins les pas horizontaux. D'où l'extémité B (x+i,y+n-i).
Ai-je bien compris?
Avec mes remerciements.
Merci
Pour la question 1)a) je ne savais pas comment rédiger. J'ai écrit : pour le 1er pas on a deux chemins monotones puis pour chaque pas suivant on aura 2 fois plus de chemins monotones. Donc, il y a 2nchemins monotones à n pas d'origine A.
Ma formulation est-elle correcte?
Encore merci.
2)a)
Les conditions sur x,y,x',y'sont :
Il faut au moins un pas horizontal ou vertical.
Donc x
x'ou yy' et x'
x et y'>y ou y'y et x'>x
Ma réponse et ma rédaction sont elles correctes?
Remerciements
Nickel. Enfin tu peux abréger car quand tu dis [xx' ou yy'] et [x'x et y'>y ou y'y et x'>x], le début ne sert à rien, tu peux te contenter d'écrire : [x'x et y'>y ou y'y et x'>x]
donc les valeurs du nombre de pas horizontaux sont i=x'-x et j=y'-y avec j le nombre de pas verticaux et i le nombre de pas horizontaux. (j=n-i et i=n-j accessoirement). Est-ce juste?
merci
2)c)
Factoriel x'-x dans n = factoriel y'-y dans n
3)J'ai tout calculé avec la formule du 2)c)
4)a)
Le nombre de chemins monotones d'origine O et d'extrémité M passant par Q est :
factoriel de p dans n+m+p * factoriel de k dans n+k
4)b)
Le nombre de chemins monotones d'origine O et d'extrémité M est :
factoriel de n+m dans n+m+p = factoriel de p dans n+m+p
et i = n+m , j = p donc i = n-j = n-p et j = n-i = n-(n+m) = m
d'où factoriel de p dans n = factoriel n-p dans n
C'est la fin, en espèrant que tout cela soit juste ?
Merci
c'est des combinaisons
Annuler
connectez vous
géométrie en post-bac