Inscription / Connexion Nouveau Sujet
Niveau Maths sup
Partager :

Dénombrement

Posté par pupil (invité) 09-02-06 à 21:08

Bonjour a tous, je suis de retour avec de nouvelles complications mathématiques^^ :'(. En fait on utilise les nombres de Catalan...et je n'y comprends rien...

Alors on a le couple (m,n) tel que m sup. ou egal à n, et n sup ou egal à 0. Il s'agit de déplacements successifs par des chemins. (vers le haut ou la droite etc). m+1 sera un déplacement vers la droite, et n+1 vers le haut.

1) Je dois montrer que pour tout couple (m,n) on a: D(m,n)=((m-n+1)/(m+1))(m parmi (m+n)). Avec D(m,n) le nombre de chemins de (0,0) à (m,n).
Je dois procéder par récurrence sur m et vérifier pour chaque valeur de m l'égalité d'avant pour n=1 ,n=2,...,n=m. Je comprends riennnn :'(

2) Montrer que le nombre de chemins de (a,b) à (a+m,b+n) est (n parmi n+m)
avec a b m et n des entiers naturels... Pff idem !

Merci de votre aide !

Posté par pupil (invité)re : Dénombrement 09-02-06 à 22:21

personne pour m'aider? Sniff

Posté par
matheux2006
re : Dénombrement 09-02-06 à 22:37

Bonsoir pupil.
Je suis entrain de réfléchir sur ton sujet mai j'avoue que c'est pas du gateau.

Posté par pupil (invité)re : Dénombrement 09-02-06 à 22:47

merci t'as vu c'est pas simple ^^ j'y retourne

Posté par
veleda
denombrement 10-02-06 à 18:08

bonsoir,
tu peux remarquer que pour arriver en (m,n) ou bien on vient de(m-1,n) enfaisant un pas parallélement à ox ou bien on vient de (m,n-1)en fasant un pas parallélement à oy  donc
D(m,n) = D(m-1,n) +D(m,n-1) pour m>ou =n>ou=1
Tu peux écrire D(m+1,n)=D(m,n)+D(m+1,n-1)
               D(m+1,n-1)=D(m,n-1)+ D(m+1,n-2)
               ...............................
               ...............................
               D(m+1,1) =  D(m,1)  + D(m+1,0)
on peut en deduire D(m+1,n) en fonction de D(m,n),D(m,n-1)..........et D(m+1,0)qui vaut 1 . SAUF ERREUR
BON COURAGE

Posté par
veleda
redénombrement 10-02-06 à 18:11

je n'ai pas eu le temps d'en faire plus ce n'est qu'une idée

Posté par
elhor_abdelali Correcteur
re : Dénombrement 10-02-06 à 19:21

Bonjour;
1)Si on munit le plan euclidien usuel \mathbb{R}^2 du repére orthonormé (O,\vec{i},\vec{j}) avec \fbox{O=(0,0)\\\vec{i}=(1,0)\\\vec{j}=(0,1)} on s'aperçoit que le nombre de chemins allant de (0,0) vers (m,n) n'est que le nombre de façons de composer les deux translations t_{\vec{i}} et t_{\vec{j}} pour obtenir la translation t_{m\vec{i}+n\vec{j}}.Désignons alors par d le nombre de t_{\vec{i}} (nombre de déplacements à droite) et par h celui des t_{\vec{j}} (nombre de déplacements vers le haut) figurant dans le produit qui donne t_{m\vec{i}+n\vec{j}}.Le produit des translations étant commutatif on doit avoir t_{d\vec{i}+h\vec{j}}=t_{m\vec{i}+n\vec{j}} c'est à dire \fbox{d=m\\h=n}.Tout chemin allant de (0,0) à (m,n) est donc composé d'exactement m déplacements à droite et n déplacements vers le haut et s'avére ainsi totalement détérminé par la répartition de ses m déplacements à droite (ou ses n déplacements vers le haut) parmi ses m+n déplacements.
Conclusion:
4$\blue\fbox{D(m,n)=D(n,m)=C_{m+n}^{m}=C_{m+n}^{n}}
2)Si on note \scr D_{(0,0)}(m,n) l'ensemble des chemins allant de (0,0) vers (m,n) et \scr D_{(a,b)}(a+m,b+n) celui des chemins allant de (a,b) vers (a+m,b+n),l'application \fbox{\scr\phi{:}\scr D_{(0,0)}(m,n)\to\scr D_{(a,b)}(a+m,b+n)\\\scr C\to t_{a\vec{i}+b\vec{j}}(\scr C)} est clairement bijective et il y'a donc autant de chemins allant de (0,0) vers (m,n) que de chemins allant de (a,b) vers (a+m,b+n).

Sauf erreurs bien entendu

Posté par
veleda
denombrement 10-02-06 à 19:41

bonsoir,il me semble qu'il veut dénombrer les chemins joignant (0,0)à (m,n) et ne traversant pas la première bissectrice  (me st supérieur ou=n)    donc de C(n+m,n) il faut enlever le nombre de chemins coupant la première bissectrice.Le texte demande une récurrence et pas un dénombrement direct.
il me semble que les nombre D(m,n),D(m,n-1)......peuvent s'écrire sous forme d'une différence de combinaisons et que leur somme "s'arrange" avec le principe des dominos mais je confonds  peut êtreavec un autre exo
et je n'ai pas eu le temps de chercher
bonne soirée



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1699 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !