Inscription / Connexion Nouveau Sujet
Niveau Maths sup
Partager :

NOMBRE DE CHEMINS ENTRE 2 POITNS à L AIDE DES COMBINAISONS

Posté par matou (invité) 26-10-04 à 19:54

bonjour, ce serait gentil de m'aider à répondre à ce problème:

dans un plan rapporté à un repère orthonormé (O, , )
on appelle chemin optique joignant 2 points A et B toute suite (Ao, A1, A2....., An) tel que
Ao=A, An=B et pour tout entier k (0<=k<=n-1) le vecteur AkAk+1 est égal au vecteur i ou j.
l'entier  n   est la longueur du chemin.
la droite est la droite d'équation y=x privé du point O.

1)  déterminer le nombre de chemins joignant le point O et le point M de coordonnées (p,q) avec p et q 2 entiers naturels.

2) déterminer le nombre de chemins d'origine O et de longueur fixée n où n est un entier naturel non nul.

3) soit les point A'(0,1), A(0,1) et M(p,q) avec p et q 2 entiers naturels tels que p>q>0
  a) montrer que le nombres de chemins joignant A et M  et rencontrant est égal au nombre de chemins  joignant A' et M
  b) En déduire le nombre de chemins joignant O et M et ne rencontrant pas la droite delta.


4)  soit n un entier naturel non nul.
      montrer que le nombre de chemins d'origine O, de longueur 2n, ne rencontrant pas la droite delta est  la combinaison de n éléments parmi 2n éléments


5)  utiliser ce qui précède pour démontrer la relation :

    (de k=0 jusqu'à k=n )du produit de la combinaison de k éléments parmi 2k éléments par la combinaison de (n-k)éléments parmi 2(n-k)éléments doit être égal à4n.


pour la question 1) je pense qu'il y en a une infinité mais je n'en suis pas sûr. Pour la question 2), j'ai trouvé que le nombre de chemins est (n+1) mais je n'arrive pas à le démontrer . Pour les autres questions, je n'ai aucune idée de la réponse.

                Merci d'avance, au revoir.
                                                MATH
  
  

Posté par
franz
re : NOMBRE DE CHEMINS ENTRE 2 POITNS à L AIDE DES COMBI 28-10-04 à 02:59

Bonsoir matou,

1)  Pour relier 0 à M, il faut constituer un (p+q)-uplet de segments verticaux (vers le haut) ou horizontaux (vers la droite) dont p seront horizontaux et q verticaux. Constituer un chemin revient à placer les p segments horizontaux ans le (p+q)-uplet. Tu as \left(\begin{tabular}{c}p+q\\p\end{tabular}\right) façons de constituer ce (p+q)uplet.
(Attention, on ne peut pas se déplacer ni vers la gauche ni vers le bas ce qui conduit à un nombre fini de chemins).

2)  Si la longueur du chemin est n(=p+q), on a n+1 points d'arrivée An possibles ( (0,n),(1,n-1),..., (n,0) ). En reprenant le résultat du 1°, le nombre de chemins cherché est donc:
\sum_{i=0}^n\left(\begin{tabular}{c}n\\i\end{tabular}\right)=2^n (formule du binôme).

Autre façon : un chemin de longueur n est un n-uplet de segments verticaux ou horizontaux. Pour chaque pas on a deux choix. Il y a donc 2^n chemins distincts.

3) Là, ça se corse un peu. (J'imagine que A(1,0) contrairement à ce que tu as écrit)
3a) Considère un chemin C allant de A à M et rencontrant . Soit P le dernier point du chemin situé sur . On peut décomposer le chemin C en deux "sous-chemins" C1 allant de A à P et C2 allant de P à M (le sous-chemin C2 ne rencontre pas ). Si on fait correspondre à C1 le chemin C'1 symétrique de C1 par rapport à , C'1 relie A' à P et le chemin C' constitué de C'1 et C2 va de A' à P. Il y a bijection entre les chemins allant de A à M et rencontrant et les chemins allant de A' à M (du moment que p>q).

3b) Soit
E l'ensemble des chemins reliant 0 à M.
E1 l'ensemble des chemins reliant 0 à M en passant par A qui ne touchent pas .
E2 l'ensemble des chemins reliant 0 à M en passant par A qui rencontrent.
E3 l'ensemble des chemins reliant 0 à M en passant par A' (et qui rencontreront forcément ).

(E1,E2,E3) forme une partition de E.
Card E = \left(\begin{tabular}{c}p+q\\p\end{tabular}\right) = Card E _1 + Card E _2 + Card E _3 = Card E _1 + 2.Card E _3 = Card E _1 + 2.\left(\begin{tabular}{c}p+q-1\\p\end{tabular}\right)
(il y a autant de chemins allant de A' à M qe de chemins allant de O à N(p,q-1) ).
Card E_1 = \left(\begin{tabular}{c}p+q\\p\end{tabular}\right) - 2.\left(\begin{tabular}{c}p+q-1\\p\end{tabular}\right) = \left(\begin{tabular}{c}p+q-1\\p-1\end{tabular}\right) - \left(\begin{tabular}{c}p+q-1\\p\end{tabular}\right) = \frac{(p+q-1)!}{p!q!}(p-q)

4) Le nombre de chemins de longueur 2n(=p+q) situés sous la ligne (car d'après la question précédente p>q) vaut
\sum_{p=n}^{2n} \left[ \left(\begin{tabular}{c}2n-1\\p-1\end{tabular}\right) - \left(\begin{tabular}{c}2n-1\\p\end{tabular}\right) \right] = \left(\begin{tabular}{c}2n-1\\n-1\end{tabular}\right)
Il y en a autant au dessus de .
Le nombre cherché vaut donc
2.\left(\begin{tabular}{c}2n-1\\n-1\end{tabular}\right)=\left(\begin{tabular}{c}2n-1\\n-1\end{tabular}\right)+\left(\begin{tabular}{c}2n-1\\n\end{tabular}\right)=\left(\begin{tabular}{c}2n\\n\end{tabular}\right)

Voilà. Je vais me coucher. Je verrai demain pour le 5.
Bon courage.

Posté par
franz
re : NOMBRE DE CHEMINS ENTRE 2 POITNS à L AIDE DES COMBI 29-10-04 à 22:13

Bonsoir matou,

Je n'ai pas eu le temps de finir hier comme convenu.
Voici la fin.

5) Soit A2k(k,k) un point situé sur la droite (éventuellement O dans ce cas k=0). On a \left(\begin{tabular}2k\\k\end{tabular}\right) sous chemins de longueur 2k reliant 0 à A2k et \left(\begin{tabular}2n-2k\\n-k\end{tabular}\right) sous chemins de longueur 2(n-k) issus de A2k ne coupant pas .
Cela donne \left(\begin{tabular}2k\\k\end{tabular}\right)\left(\begin{tabular}2n-2k\\n-k\end{tabular}\right) chemins de longueur 2n dont le dernier point sur est A2k.

Lorsque l'on fait varier A2k sur , on retrouve tous les chemins de longueur 2n (au nombre de 22n=4n) d'où le résultat : \bigsum_{k=0}^n\left(\begin{tabular}2k\\k\end{tabular}\right)\left(\begin{tabular}2n-2k\\n-k\end{tabular}\right)=4^n

P.S. J'aurais bien aimé savoir si ma 1° réponse avait été lue.
A bientôt j'espère.

Posté par matou (invité)MERCI POUR LES REPONSES 30-10-04 à 12:16

merci Franz pour ces réponses que je n'aurait peut être pas trouvées tout seul.

                                 Au revoir et peut  
                             être à une prochaine fois


                                     MATH



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 1674 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 !