Partage
  • Partager sur Facebook
  • Partager sur Twitter

Analyse combinatoire

Collection d'objet avec des éléments en double

    21 juillet 2018 à 22:18:33

    Bonjour à tous,

    Voici une simplification de mon énoncé :

    Avec une liste des 40 caractères, combien peut on écrire de mot à 5 chiffres (il s'agit donc d'un tirage sans remise) ?

    Voici la liste de caractères que je dispose : a a z z z e e r t y u i o p q s d f g h j k l m w x c v b n 7 4 1 8 5 2 9 6 3 0

    En utilisant la formule classique je trouve 40! / (40 - 5)! = 78 960 960 mots possibles.

    Je pense qu'à ce stade vous avez tous compris où je souhaite en venir : comment gérer les doublons liés à la liste de caractères que j'utilise ?

    Pour ceux qui ne comprendraient pas, je vais réécrire mon alphabet en donnant des couleur différentes aux mêmes lettres :

    a    z     e      r t y u i o p q s d f g h j k l m w x c v b n 7 4 1 8 5 2 9 6 3 0

    Maintenant simulons deux tirages aléatoires différents :

    • a i h s a
    • a i h s a
    Vous remarquerez que ces deux tirages, pourtant différents, comme le met en avant la couleur rouge, forment le même mot. Mon compte de 78 960 960 mots est donc faux.
    J'espère avoir été clair.
    J'ai lu pas mal de sujet un peux partout et j'ai suivie pas mal de cours à ce sujet mais rien n'y fais, je ne trouve pas cette réponse.
    J'aimerais éviter d'avoir à faire de la recherche personnel dessus tant que je ne suis pas sûr que quelqu'un a déjà établie une formule.
    Des piste de recherches ? A défaut, des piste de réflexion ?
    Merci d'avance,
    Bonne soirée,
    jam-jam

    -
    Edité par jam-jam68140 21 juillet 2018 à 22:21:07

    • Partager sur Facebook
    • Partager sur Twitter
      22 juillet 2018 à 0:13:34

      Hello.

      Ce sujet a l'air intéressant. Il est un peux tard pour que j'y réfléchisse mais je vais essayer demain :)
      Ma piste  d'investigation serait : est ce qu'on serait capable de gerer la différence en terme de nombre de tirage entre : "a,b,c,d,e,f" et "a,a,b,c,d,e,f" ?

      Donc ce qu'il se passe lorsqu'un caractère est présent deux fois mais a la même signification lors du tirage . On pourra ensuite essayer trois puis voir le cas que tu présente.

      sinon, je n'ai pas encore vu de sujet semblable mais je vais essayer de fouiller dans ma mémoire :)

      -
      Edité par edouard22 22 juillet 2018 à 2:30:26

      • Partager sur Facebook
      • Partager sur Twitter
        22 juillet 2018 à 14:52:45

        Bonjour à tous,

        J'ai fais de investigations perso et j'ai trouvé un résultat grace à une conjecture que j'ai faite :

         Formule conjecturé par mes soins

        Du coup, d'après ma formule et pour l'exemple donnée lus haut j'ai x qui vaut 40, m2 qui vaut 2 (car j'ai deux double, le a et le e) et m3 qui vaut 1 (car j'ai un triple, le z).

        J'ai donc un nombre total d'ordonnancement distincts de 40! / (22 * 61) soit un total de environ 8×1047 / 24 = 3×1046

        Bon maintenant si je veux chercher les nombre de mot disctinct de 5 caractère je devrais diviser ce réultat par (40 - 5)! je me trompe ?

        Ca me donnerais un total de 40! / (24 × 35!) = 40*39*38*37*36 / 24 = 3 290 040 mots. Ce qui est considérablement moins que 78 960 960.

        Est ce que quelqu'un a compris ma démarche et peut me confirmer que c'est la bonne ? :)

        Merci d'avance,

        EDIT : après quelques tests je suis tombé sur une incohérence, je pense qu'il ne faut pas vulgairement diviser par (40 - 5)! pour obtenir le nombre de mot possible à partir du nombre d'ordonnancements différents. Je cherche encore comment faire.

        -
        Edité par jam-jam68140 22 juillet 2018 à 17:36:51

        • Partager sur Facebook
        • Partager sur Twitter
          23 juillet 2018 à 14:22:01

          Le nombre total de mot de 5 caractères pris parmi 40 caractères distincts est effectivement 78.960.960 ( nombres d'arrangements de 5 parmi 40).

          Pour trouver le nombre de mots distincts lorsque il y a des caractères répététés, on peut utiliser le résultat classique suivant:

          Si un mot est composé de \(n\) caractères, avec des caractères répétés \(n_1,n_2,..., n_k\) fois, le nombre de mots distincts vaut :\(\frac{n!}{n_1!n_2!....n_k!}\). On  retrouve bien sûr \(n!\) si tous les caractères  sont distincts.

          Donc par exemple,  on peut former  \( 5!=120\) mots distincts de 5 lettres   avec 5 caractères distincts mais si deux sont identiques , il n'y en a plus que \(\frac{5!}{2!}=60\).

          Dan le problème considéré , il y a  \(\frac{36!}{31!}= 45.239.040\) mots avec des caractères tous distincts .

          Compte tenu des  doublons ou plus ( 3 z par exemple) , le nombre 78.960.960 - 45.239.040 =33.721.920 est un nombre en excès qui contient un sous-ensemble de mots identiques.

          Pour trouver le nombre réel de mots,  je pense qu'il faut calculer par disjonction de tous les cas possibles, et utiliser à chaque fois la propriété rappelée ci-dessus.

          Les cas possibles sont: 

           

          aaxxx 60 39270 2356200
          eexxx 60 39270 2356200
          zzxxx 60 39270 2356200
          aaeex 30 34 1020
          aazzx 30 34 1020
          eezzx 30 34 1020
          zzzxx 20 1190 23800
          zzzaa 10   10
          zzzee 10   10
                7.095.480
               
           


          où les x sont les autres caractères utilisables. La colonne 2 indique le nombre de mots possibles pour chaque combinaison complémentaire xxx, xx , x ou aucun.

          La colonne 3 indique le nombre de combinaisons complémentaires possibles.Par exemple si j'ai 2 a , on a le choix de 3 x parmi 35 ( 33 +1e +1z)

           soit (A_35^3 =2356200\) possibilités. En multipliant  col 2x col 3, on obtient alors  le nombre de mots distincts pour chaque situation de caractères multiples.

          Le total général donne alors 7.095.480 au  lieu de 33.721.920,

          soit un nombre total de mots distincts de 45.239.040 + 7.095.480 = 52.334.520 mots distincts.

          sauf oubli ou erreur de calcul . J'ai fait cela un peu vite ! mais le principe me semble correct :)

          -
          Edité par Sennacherib 23 juillet 2018 à 14:25:47

          • Partager sur Facebook
          • Partager sur Twitter
          tout ce qui est simple est faux, tout ce qui est compliqué est inutilisable
            23 juillet 2018 à 15:36:32

            Hello! 
            Alors, j'ai lu en diagonale, mais je me demandais pourquoi ma reflexion était fausse : 

            Si on considère que (j'ai donné des noms pourris, mais qui n'existent pas encore, et qui sont visibles :))

            a = alpha 

            z = beta

            z = theta

            e = gamma 

            Alors l'alphabet devient :

             alpha a beta theta z gamma e r t y u i o p q s d f g h j k l m w x c v b n 7 4 1 8 5 2 9 6 3 0

            donc les exemples deviennent :

            a i h s alpha

            alpha i h s a

            Qui ne sont pas les même mots. On a bien 40 lettres, et si on doit faire un tirage de 5 mots, on a bien 40! / 5!
            Je comprends pas pourquoi ce calcul est faux ducoup ...
            • Partager sur Facebook
            • Partager sur Twitter

            « Je n’ai pas besoin de preuve. Les lois de la nature, contrairement aux lois de la grammaire, ne permettent aucune exception. »
            D. Mendeleïev

              23 juillet 2018 à 17:23:39

              Coucou,

              KirbXCouCou, il est faut car tu ne dois pas remplacer le a rouge par alpha :p

              Il y a bien deux a dans ma collection de départ qui sont des élément identiques. Donc à la fin mes mot seront identiques aussi et je voudrais les éliminer pour optimiser mes calculs te ne pas avoir de doublon.

              A terme il faudrait même que je considère comme étant le même mot les mots suivants (car il contiennent exactement les mêmes lettres, peu importe l'ordre) :

              • a i h s a
              • i a a s h

              Mais bon, on va y aller étape par étape et résoudre la première question.

              Sennacherib, pourrais tu me dire d'où tu tire ta formule ? Elle est strictement identique à la formule que j'ai conjecturé, j'airais bien aimé voir une démo ou pouvoir mettre un nom sur la formule histoire que je la retienne.

              En suite, j'ai l'impression que tu est partie du nombre de lettre distinctes pour ton calcul puis tu as rajouter des combinaisons. Il me semble que tu en a oublié ( axxxa par exemple ? ou encore axxax ? )

               Je ne suis pas très à l'aise avec l'idée de devoir combien de combinaison on a "oublié" et de les rajouter en suite. Je préfère conter combien on en a mis en trop et les retirer.

              EDIT : je viens de comprendre ton raisonnement avec 36! / 31!

              C'est pas con de le borner pour limiter la recherche et vérifier la cohérence des résultats.

              EDIT 2 : Après mûre réflexion ta technique est géniale !! :D

              Merci beaucoup, je fais essayer de trouver une formule générale pour ne pas avoir à faire tout ça à chaque fois ^^' :)

              -
              Edité par jam-jam68140 23 juillet 2018 à 17:49:07

              • Partager sur Facebook
              • Partager sur Twitter
                23 juillet 2018 à 20:51:40

                Hello :)

                Visiblement j'arrive un peux tard mais je vais partager l'idée que j'ai eu au boulot ce midi :)
                Cependant, je trouve  uniquement 1.148.986 doublons, ce qui nous ferait : 77.811.974 mots Soit j'ai 20 millions de mot en trop, ou Senna en a perdu 20 millions :p ( Edit, j'ai bien des mots en trop.. :'( )

                Une solution serait peut être de faire une récurrence sur le nombre de lettre dans le mot..

                je laisse le truc faux si cela vous intéresse :D
                On a ici l'alphabet A={ a a z z z e e r t y u i o p q s d f g h j k l m w x c v b n 7 4 1 8 5 2 9 6 3 0 }
                Comme l'a dit Sennascherib, on a \( C_5^{40} = 78.960.960 \) façon de choisir 5 lettres parmi les 40 dans A.

                Comme Senna, mon idée est ensuite de compter les mots en double, pour cela, je commence par considérer un nouvel alphabet A = A \ {a}  afin de compter les doublons du au double a.

                1er cas : Exactement un  'a' dans le mot, ce sont les mots du type : a x x x x avec \( x \in A \)
                Le nombre de mot x x x x est \( C_4^{38} = 73.815 \) qu'il faut multiplier par \( C_1^5 = 5 \) le nombre de façon de placer le a. On doit donc enlever ici 369.075 mots

                2er cas : Exactement deux 'a' dans le mot, ce sont les mots du type : a a x x x avec \( x \in A \) 
                Le nombre de mot x x x  est \( C_3^{38} = 8.436 \) qu'il faut multiplier par \( C_2^5 = 10 \) le nombre de façon de placer les deux a. On doit donc enlever ici 80.436 mots

                Donc si on enlève les doublons causés par les a, on tombe à 78.511.449 mots. Et l'alphabet devient :
                A ={ a z z z e e r t y u i o p q s d f g h j k l m w x c v b n 7 4 1 8 5 2 9 6 3 0 }

                note : le fait d'enlever les doublons de a de l'alphabet permet d'éviter ensuite de ré-supprimer des mots déjà supprimé. Sauf qu'on oublie des mots en faisant cela.  il ne faut donc pas le faire mais faire attention aux A.


                On recommence donc pour z :
                1er cas : Exactement un  'z' dans le mot, ce sont les mots du type : z x x x x avec \( x \in A \)
                Le nombre de mot x x x x est \( C_4^{36} = 58.905 \) qu'il faut multiplier par \( C_1^5 = 5 \) le nombre de façon de placer le z. On doit donc enlever ici 294.525 mots

                Or ici A A E E n'est pas compté dans \( C_4^{36} \)  donc on oublie de supprimer pleins de mot

                2nd cas : Exactement deux 'z' dans le mot, ce sont les mots du type : z z x x x avec \( x \in A' \) 
                Le nombre de mot x x x  est \( C_3^{36} = 7.140 \) qu'il faut multiplier par \( C_2^5 = 10 \) le nombre de façon de placer les deux a. On doit donc enlever ici 71.400 mots

                3iem cas : Exactement trois 'z' dans le mot, ce sont les mots du type : z z z x x avec \( x \in A' \) 
                Le nombre de mot  x x  est \( C_2^{36} = 630 \) qu'il faut multiplier par \( C_3^5 = 10 \) le nombre de façon de placer les deux a. On doit donc enlever ici 6.300 mots

                Les 'z' enlèvent donc 372.225 mots, il en reste : 78.139.224

                (ici, je me rends compte que je suis bien au dessus du compte de Senna, mais on va finir pour voir :), car le raisonnement me semble bon )
                A={ a z e e r t y u i o p q s d f g h j k l m w x c v b n 7 4 1 8 5 2 9 6 3 0 }
                A'={ a z r t y u i o p q s d f g h j k l m w x c v b n 7 4 1 8 5 2 9 6 3 0 }  ( 35 lettres )

                1er cas : Exactement un  'e' dans le mot, ce sont les mots du type : e x x x x avec \( x \in A' \)
                Le nombre de mot x x x x est \( C_4^{35} = 52.360 \) qu'il faut multiplier par \( C_1^5 = 5 \) le nombre de façon de placer le e. On doit donc enlever ici 261.800 mots

                2nd cas : Exactement deux 'e' dans le mot, ce sont les mots du type : e e x x x avec \( x \in A' \) 
                Le nombre de mot x x x  est \( C_3^{35} = 6.545 \) qu'il faut multiplier par \( C_2^5 = 10 \) le nombre de façon de placer les deux e. On doit donc enlever ici 65.450 mots


                On doit doit encore enlever 327.250 mots. On devrait donc avoir : 77.811.974 mots

                La bonne question maintenant est pourquoi ca marche pas. c'est dommage on pouvait en faire un algo efficace et simple à prog :o

                -
                Edité par edouard22 23 juillet 2018 à 22:11:57

                • Partager sur Facebook
                • Partager sur Twitter
                  23 juillet 2018 à 22:22:18

                  Edouard, c'est prise de tête comme sujet hein x)

                  En fait l'algo de Senna est assez simple à programmer et relativement performant. J'aurais bien aimé une formule explicite plutôt qu'une formule récurrente :p

                  Je n'ai pas eu le temps de travailler sur la définition d'une telle formule à partir de l'algo mais dès que j'ai le temps je m'y mets :)

                  Encore merci pour l'aide. Je reviendrais plus tard.

                  • Partager sur Facebook
                  • Partager sur Twitter
                    26 juillet 2018 à 13:10:21

                    Bonjour tous le monde,

                    Grace à la manière de faire de Senna, j'ai pus dénombrer le nombre de mots de 5 lettres possibles sans tenir compte de l'ordre des lettres (c'est ça mon problème initial, comme je l'expliquais à KirbXCouCou).

                    Considérons maintenant un deck de 40 cartes où il y aurait deux doubles et un triple. Nous avons 32 cartes distincts dans ce deck. Nous avons donc 36! / (31! × 5!) =376992 mains distinct ne comportant aucun doublons.

                    Nous devons à présent dénombrer les mains avec des triples. La main de départ n’ayant que 5 cartes, il est impossible que celle ci contiennent deux triples. Les possibilités sont donc :

                    • Obtenir un triple et un doubles :

                    1

                    ×

                    2

                    =

                    2

                    Nombre de triple

                     

                    Nombre de double

                     

                    Nombre de mains


                    • Obtenir un triple et deux cartes distincts :

                    1

                    ×

                    35! / (33! × 2!)

                    =

                    595

                    Nombre de triple

                     

                    Nombre de manière distincts d’obtenir deux cartes distincts

                     

                    Nombre de mains


                    • Obtenir deux double et une carte :

                    3!

                    ×

                    34

                    =

                    204

                    Nombre de manières d’obtenir deux doubles

                     

                    Nombre de cartes distincts restantes

                     

                    Nombre de mains


                    • Obtenir un double et trois cartes distincts  :

                    3

                    ×

                    35!32! × 3!

                    =

                    6545

                    Nombre de manières d’obtenir un double

                     

                    Nombre de manière distincts d’obtenir trois cartes distincts

                     

                    Nombre de mains


                    On a donc un total de 376992+ 2 + 595 + 204 + 6545 = 384 338 mains possibles.


                    Je vais essayer de brute-force mon algo pour vérifier nos comptes puis si tout est juste j'essayerais d'établir une formule :)

                    • Partager sur Facebook
                    • Partager sur Twitter

                    Analyse combinatoire

                    × Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
                    × Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
                    • Editeur
                    • Markdown