Mathématiques - dénombrement

dénombrement
(Cliquez-ici pour accéder à la version originale de cette discussion avec couleurs et images)

Posted by: sue

Bonjour,

comment trouver le nombre de p-uplets $(x_1,..x_p) \in N^p$ tq $\sum_{k=1}^{p} x_k=n$ ?

j'ai le résultat mais je sais pas comment le prouver .

merci

Posted by: tize

Bonjour Sue,
cela revient à compter le nombre d'application $u$ de $E_p=\{1;2;...;p\}$ dans $\{0;1;...;n\}$ tels que $\sum\limits_{x\in E_p} u(x)=n$ .
Et pour cela il est parfois plus facile de compter les applications qui vérifient $\sum\limits_{x\in E_p} u(x)\leq n$ ,
il y a une bijection entre ces deux genres d'applications...

Posted by: emdro

Bonjour Sue,

c'est une idée simple:
Imagine que tu places n billes alignées.
Maintenant, tu dois faire p paquets. Il te suffit pour signifier x1=2 par exemple de tracer un trait entre les billes N° 2 et 3. Pour x2=5, tu traceras un trait entre la bille N°7 et la 8 (billes 3,4,5,6,7 dans ton deuxième paquet). etc.
A chaque p-uplet est associé une et une seule répartition des billes.

Il te suffit alors de compter le nombre de manières de placer p-1 traits dans n+1 espaces (de "avant la première bille" à "après la n-ième)

Posted by: ThSQ

C'est le grand classique combinaison avec répétition

C'est le même nombre que :

$(x_1,..x_p) \in N^{*p}$ tq $\sum_{k=1}^{p} x_k=n+p$

Tu mets n+p chiffres 1 à la suite et tu en regroupes certains (en mettant un "trait") pour se ramener à p nombres. Il faut mettre p-1 traits parmi n+p-1 ça fait donc $C_{n+p-1}^{p-1}$ possibilités

Posted by: sue

je vous remercie tous

sinon une autre question toujours dénombrement ..
dans un exo on pose la question sur le nombre de relations symétriques / réflexives/ antisymétriques , je me demande donc si on peut calculer le nombre de relations transitives sur E ?

merci

Posted by: ThSQ

Citation:

Posté par sue

le nombre de relations transitives sur E ?

J'ai posé la même question à mon prof y'a pas longtemps, il m'a répondu qu'on ne connaissait pas de formule "fermée" (c'est-à-dire une formule simple s'exprimant à l'aide de bidules connus).