Niveau LicenceMaths 2e/3e a

Exercice de dénombrement maths

Posté par
Slyder 15-11-19 à 02:09

Bonjour à tous

Je sollicite votre aide sur un exercice de dénombrement qui me pose problème.

Enoncé : Pour tout $\left(a,b \right)\in N^2$ \ $\left\{\left(0,0 \right) \right\}$
on note $M(a,b)$ l'ensemble des chemins qui vont du point $(0,0)$ au point $(a,b)$ tels que à chaque pas on se déplace soit en direction $(1,0)$ , soit en direction $(0,1)$ , soit en direction $(1,1)$ .
On pose $m_{a,b} = \left|M(a,b) \right|$

Question : Montrer que pour tout $(a,b)\in N^2$ \ $\left\{\left(0,0 \right) \right\} , m_{a,b} = \sum_{k=0}^{a}{\begin{pmatrix} a\\ k \end{pmatrix}}\begin{pmatrix} b+k\\ a \end{pmatrix}$

Ma démarche :

Soit $k\in N$ le nombre de $(1,1)$ effectué
Il faut donc $a - k$ choix de $(1,0)$ et $b - k$ choix de $(0,1)$ pour atteindre le point $M(a,b)$ parmi $a+b-k$ possibilités

d'où $m_{a,b} = \sum_{k=0}^{a}{\begin{pmatrix} a+b-k\\ k,a-k,b-k \end{pmatrix}}= \sum_{k=0}^{a}{\begin{pmatrix} a\\ k \end{pmatrix}}\begin{pmatrix} a+b-k\\ a \end{pmatrix}$

Or en inversant l'ordre de sommation et en utilisant la symétrie des coefficients binomiaux, on obtient :

$m_{a,b} = \sum_{k=0}^{a}{\begin{pmatrix} a\\ k \end{pmatrix}}\begin{pmatrix} b+k\\ a \end{pmatrix}$

Je ne suis pas du tout sûr de mon raisonnement et en cours nous n'avons pas vu l'usage des coefficients multinomiaux ce qui me laisse penser que je n'adopte pas la bonne démarche.
Je ne sais pas s'il y a une démarche permettant de n'utiliser que les coefficients binomiaux et permettant d'être plus clair sur le cheminement du raisonnement.

Merci beaucoup à tous pour votre aide !

Posté par re : Exercice de dénombrement maths 15-11-19 à 17:02

Slyder @ 15-11-2019 à 02:09

Ma démarche :

Soit $k\in N$ le nombre de $(1,1)$ effectué
Il faut donc $a - k$ choix de $(1,0)$ et $b - k$ choix de $(0,1)$ pour atteindre le point $M(a,b)$ parmi $a+b-k$ possibilités

Ici, je voulais dire pour atteindre le point $(a,b)$

Posté par re : Exercice de dénombrement maths 15-11-19 à 17:48

Bonsoir,
ton calcul et ton raisonnement sont juste. ( À mon avis ).

Tu peux redémontrer que le coefficient multinomial convient sans l'utiliser.

Par exemple : un chemin peut-être codé par une suite de lettre V ; H ; D avec V pour (0;1), H pour (1;0) et D pour (1;1).
Si il y a j lettres D dans la suite, sa longueur est a+b-j.

Il y a donc, pour une valeur de j fixé ( et plus petite que min(a;b) ) $\binom{a+b-j}{j}$ possibilités pour placer les D.
On place ensuite les H : il y a $\binom{a+b-2j}{a-j}$ possibilités.

En posant k=a-j ( on inverse la somme ) on a $\binom{b+k}{a-k}\times\binom{-a+b+k}{k}$ possibilités pour a-k lettres D.

Enfin un calcul pas trop compliqué montre que $\binom{b+k}{a-k}\times\binom{-a+b+k}{k}=\binom{a}{k}\times\binom{b+k}{a}$

Posté par re : Exercice de dénombrement maths 15-11-19 à 18:03

bonjour

je pense déjà que ton raisonnement repose sur le fait que ab
et que donc il ne peut y avoir plus de a déplacements (1;1)

cela n'est pas restrictif puisqu'on remarquera que m(a;b)=m(b;a)

par ailleurs, si on choisit de faire k déplacements (1;1), il reste (a+b-2k) déplacements à faire parmi lesquels (a-k) du type (1;0) et (b-k) du type (0;1)

Posté par re : Exercice de dénombrement maths 15-11-19 à 18:13

ensuite je rejoins verdurin (que je salue) sur la trame de la démo

Posté par re : Exercice de dénombrement maths 15-11-19 à 19:49

Salut matheuxmatou.
En utilisant la définition, pour v entier, $\binom{u}{v}=\frac{u\cdot(u-1)\cdots(u-v+1)}{v!}$ il est inutile de se demander si ab.
On a $\binom{a}{k}=0$ quand $a<k$ .

Posté par re : Exercice de dénombrement maths 15-11-19 à 22:29

Bonsoir

J'y vois désormais plus clair
Merci beaucoup à vous deux pour vos réponses !

Ce topic

Imprimer
Réduire / Agrandir
Pour plus d'options, connectez vous !
Fiches de maths

algèbre en post-bac
28 fiches de mathématiques sur "algèbre" en post-bac disponibles.

Rechercher

Espace membre

Zone membre

Pas de compte ?
Je m'inscris

Changer d'île

Cours et Exercices de maths

Forum de maths

college

lycee

Outils de maths

Pages les plus populaires

Exercice de dénombrement maths

Seuls les membres peuvent poster sur le forum !

Ce topic

Fiches de maths