Répondre à la discussion
Affichage des résultats 1 à 11 sur 11

Dénombrement



  1. #1
    Makay

    Dénombrement


    ------

    On effectue le lancer de n dés.Chaque dé est numéroté de 1 à 6 .
    Quel est le nombre de combinaisons possibles sachant que l'ordre ne compte pas (par exemple ,avec n=3, 123 et 312 sont une même combinaison) ?

    -----

  2. Publicité
  3. #2
    Ledescat

    Re : Dénombrement

    Bonjour.
    Je dirais 6^n (mais bon le dénombrement et moi, ça fait 2, c'est le cas de le dire )
    Cogito ergo sum.

  4. #3
    flostein

    Re : Dénombrement

    Ca ne marche pas car l'ordre ne compte pas, pour n=2 je trouve 31 possibilités.

  5. #4
    Kacsou

    Re : Dénombrement

    En résolvant une petite récurrence, on trouve que, si tu as dés numérotés avec les chiffres de 1 à , alors le nombre de combinaisons possibles différentes modulo réordonnancement est donné par la formule :
    .
    En particulier, dans ton cas, . D'où le résultat :
    .
    Tu veux la preuve ou est-ce inutile?
    Au passage, pour 2 dés à 6 faces, je ne trouve que 21 possibilités en les énumérant toutes, et pas 31.
    Dernière modification par Kacsou ; 06/07/2007 à 15h30.

  6. A voir en vidéo sur Futura
  7. #5
    flostein

    Re : Dénombrement

    oui c'est tout à fait ca d'ailleur je viens de voir que j'ai écrit 31 à la place de 21 ....

  8. #6
    Makay

    Re : Dénombrement

    Je veux bien la preuve stp Kacsou

  9. Publicité
  10. #7
    Makay

    Re : Dénombrement

    Quelqu'un aurait la preuve svp ?

  11. #8
    homotopie

    Re : Dénombrement

    En attendant Kacsou qui a peut-être une autre preuve.
    C'est vrai pour tous les entiers k>0, pour n=1.
    Supposons vrai pour tous les jusqu'au rang n.
    pour le rang n+1, soit k un entier>0 quelconque, on écrit les possibilités de manière ordonnée :
    a1<=a2<=a3<=...<=a(n+1)
    Cas a1=1->on a le même nombre que pour (n,k)
    cas a1=2->on a le même nombre que pour (n,k-1)
    ...
    cas a1==k->on a le même nombre que pour (n,k+1-k=1)
    J'écris les coeeficients binomiaux en ligne, on a au total en partant du cas a1=k en remontant au cas a1=1 :
    (n,n)+(n+1,n)+(n+2,n)+...+(n+k-1,n)
    =(n,0)+(n+1,1)+(n+2,2)+...+(n+ k-1,k-1) (en utilisant l'égalité (N,i)=(N,N-i))
    =[(n+1,0)+(n+1,1)] +(n+2,2)+...+(n+k-1,k-1) (en utilisant (N,0)=1 pour tout N)
    =[(n+2,1)+(n+2,2)] +(n+3,3)+...+(n+k-1,k-1) (en utilisant (N,i-1)+(N,i)=(N+1,i))
    = [(n+3,2)+(n+3,3)] +(n+4,4)+...+(n+k-1,k-1) (en utilisant l'égalité précédente...)
    =[(n+k-1,k-2)+(nk-1,k-1)]
    =(n+k,k-1)
    =(n+1+k-1, n+1) (en utilisant l'égalité (N,i)=(N,N-i))
    (Il faudrait une démo par récurrence sur k pour formaliser tout ça mais bon...)
    La propriété est donc vraie pour tous les k au rang n+1.

  12. #9
    Makay

    Re : Dénombrement

    Merci homotopie.
    Mais il n'y aurait pas une preuve directe (sans procéder par récurrence)?

  13. #10
    acx01b

    Re : Dénombrement

    salut

    n dés qu'on lance tous en même temps sans les distinguer:
    ou n lancés du même dés, mais où l'ordre ne compte pas

    nombre de possibilités:
    S(6,n) = C(n+6-1, n) = C(n+5,5)

    donc pour n = 2 on a 21 possiblités

    cherche sur google:
    combinaison avec répétition
    k-combinaison
    sélection
    bijection entre application strictement croissante et application croissante

    la notion d'application croissante elle vient du fait que pour n = 4
    tu peux avoir 1332, 3132, 3312 comme tirages avec tes dés.... qui sont tous le même tirage
    si tu ranges ces 4-upplets tu obtiens
    1233 pour tous
    l'application croissante c'est f : {1,2,3,4} --> {1,2,3,4,5,6}
    f(1) = 1, f(2) = 2, f(3) = 3, f(4) = 3

    c'est facile à démontrer que tu peux mettre cette application en bijection avec une application g : {1,2,3,4} --> {1,2,3,4,5,6,7,8,9}
    en posant g(i) = f(i) + i - 1
    ça marche car si f(1) = 1, alors g(1) = 1, et si f(4) = 6, g(4) = 9
    g est bien une application strictement croissante (donc une combinaison)

    et il y a autant de f différents que de g différents, donc autant de combinaison avec répétition (n , p ) que de combinaison de (n+p-1 , p)

  14. #11
    homotopie

    Re : Dénombrement

    Citation Envoyé par acx01b Voir le message

    c'est facile à démontrer que tu peux mettre cette application en bijection avec une application g : {1,2,3,4} --> {1,2,3,4,5,6,7,8,9}
    en posant g(i) = f(i) + i - 1
    L'astuce du g m'avait échappé.
    Histoire d'être tatillon, il faudrait quand même reformuler le début : l'application qui à f associe g est une bijection (+) de l'ensemble des fonctions croissantes (n->p) dans l'ensemble des applications strictement croissantes (n->p+n-1).(++)

    (+) :construire la réciproque et vérifier que c'est bien la réciproque est facile.
    (++) : Vérifier que f->g va bien des croissantes dans les strictement croissantes à valeurs dans {1,...,p+n-1} et g->f va des strictement croissantes dans les croissantes à valeurs dans {1,...,p} est facile aussi.

Discussions similaires

  1. Denombrement
    Par jeremy1907 dans le forum Mathématiques du supérieur
    Réponses: 1
    Dernier message: 17/12/2007, 17h40
  2. Dénombrement
    Par jiraiya dans le forum Mathématiques du collège et du lycée
    Réponses: 4
    Dernier message: 04/10/2006, 11h46
  3. dénombrement
    Par sensor dans le forum Mathématiques du supérieur
    Réponses: 3
    Dernier message: 01/10/2006, 16h36
  4. dénombrement
    Par Astro boy dans le forum Mathématiques du collège et du lycée
    Réponses: 4
    Dernier message: 16/05/2006, 15h07
  5. dénombrement
    Par yonyon dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 11/05/2006, 19h15