Partage
  • Partager sur Facebook
  • Partager sur Twitter

Nombre de combinaisons contenant certaines lettres

Sujet résolu
    23 juin 2020 à 17:05:11

    Bonjour !

    Mon problème : je souhaite savoir combien de fois, il y a au moins une fois les caractères "P" et "I" dans toutes les COMBINAISONS de trois lettres.

    Attention : ce sont des combinaisons donc "API" = "PIA" = ... = +1 au compte et surtout "PPI" = "PIP" = "IPP" = ... = +1 au compte aussi ! Mais "PPP", "AAP" ou "AIB" ne marchent pas dans le compte que je veux (il faut "P" et "I").

    La formule du totale des combinaisons possibles c'est bon : \[  \binom{26 + 3 -1}{3}=\binom{28}{3}=3276 \]

    De plus, je vois que pour deux lettres il y a qu'une combinaison qui marche ("PI" = "IP")

    Mais ne sachant pas comment on appelle ça, je n'ai rien trouvé sur le sujet...

    Là c'est la version simplifiée de mon problème (combinaisons de beaucoup de lettres (22) et plus de caractère choisis (15)) donc je voudrais un calcul ou des pistes car c'est trop long à faire avec un programme (1,5e13 combinaisons)

    Voilà c'est tout ! donc si vous savez comment ça s'appelle ou que vous savez faire le calcule, dites-le s'il vous plait ! :)

    -
    Edité par Sebudeci 23 juin 2020 à 17:09:46

    • Partager sur Facebook
    • Partager sur Twitter
      23 juin 2020 à 18:41:12

      Salut,

      On peut essayer de construire les solutions et les dénombrer à partir de là.

      Par exemple pour les combinaisons de 3 lettres qui contiennent "P" et "I" parmi n lettres (26, mais si tu veux rajouter autre chose) :

      2 lettres sont déjà choisies : "P" et "I". On ne peut donc que choisir la dernière lettre, donc finalement n (=26) possibilités.

      Pour les mots de 22 lettres qui contiennent les 15 que tu veux, on doit donc prendre une fois chacune de ces quinze lettres, puis on en choisit les 7 restantes parmi les n.

      Il s'agit en fait du nombre de combinaisons de 7 lettres parmi n avec remise, donc on utilise la formule que tu as donnée.

      Comme ça on a construit tous les mots possibles.

      • Partager sur Facebook
      • Partager sur Twitter
        23 juin 2020 à 18:58:42

        Merci beaucoup Leukos ! Je me doutais que c'était assez simple mais j'y arrivait pas ..........
        • Partager sur Facebook
        • Partager sur Twitter
          24 juin 2020 à 0:49:43

          Il est tard, et j'ai le cerveau lent. Mais j'ai quand même l'impression que ce n'est pas la bonne solution.
          • Partager sur Facebook
          • Partager sur Twitter
            24 juin 2020 à 9:28:35

            (En fait je n'avais pas bien compris...)

            -
            Edité par robun 26 juin 2020 à 9:25:02

            • Partager sur Facebook
            • Partager sur Twitter
              24 juin 2020 à 18:02:15

              tbc92 j'ai aussi eu l'impression de rater quelque chose mais je ne trouve pas de problème.

              De cette façon on ne rate aucune possibilité, donc j'imagine que je peux m'être trompé sur le calcul du nombre de combinaisons de 7 lettres parmi 26 avec remises, mais cette formule correspond bien à cette situation (l'ensemble dans lequel on pioche les éléments est l'alphabet, on cherche le nombre de sous-ensemble de l'alphabet avec remises).

              Bref je suis rarement sûr de moi en combinatoire, j'ai regardé le nombre de mots de 4 et 5 lettres qui contiennent 'P' et 'I' et ce calcul donne le bon résultat, donc il y a quand même de fortes chances que ce soit bon.

              • Partager sur Facebook
              • Partager sur Twitter
                25 juin 2020 à 9:44:20

                Si le problème est de trouver le nombre de mots de 22 lettres parmi les 26 possibles contenant au moins une fois 15 lettres données, j'aurais dit comme leukos.

                -
                Edité par robun 25 juin 2020 à 9:44:36

                • Partager sur Facebook
                • Partager sur Twitter
                  25 juin 2020 à 15:07:34

                  Je pense que vous avez raison. 

                  En fait J'ai interprété la 1ère réponse comme C(26,3) ; j'ai considéré que le 28 était une faute de frappe, parce que je ne connaissais pas cette 'astuce' d'ajouter 3-1 ... pour gérer l'histoire du 'avec remise'. ... ce n'est probablement pas très clair, mais pas grave.

                  Avec C(26,3), c'est clair, il manquant des cas de figure. Il manquait toutes les combinaisons avec une lettre en double ou en triple. Il semblerait qu'avec C(28,3), ça résolve ça.  Je n'ai pas vérifié, je n'ai pas non plus cherché de référence qui justifierait ça (si vous avez ça sous la main facilement, je prends). Je n'ai pas trop de temps cette semaine, mais c'est sûr, je vais m'intéresser à cette 'astuce' dans les semaines à venir.

                  Désolé pour le dérangement :)

                  • Partager sur Facebook
                  • Partager sur Twitter
                    26 juin 2020 à 10:09:27

                    Ah, je crois que c'est plus compliqué que je ne le croyais...

                    Pour calculer le nombre de combinaisons de 3 lettres contenant un I et un P pouvant apparaître plusieurs fois, on peut procéder comme pour des comptages de mains dans un jeu de carte.

                    Je cherche les mains de trois cartes qui contiennent au moins un roi et un as. Il y a 1 roi parmi 4, 1 as parmi 4, et 1 carte parmi les 50 restantes.

                    Imaginons qu'il n'y ait plus que 15 cartes : tous les carreaux, plus un roi et un as de trèfle. Même question. Il y a cette fois 1 roi parmi 2, 1 as parmi 2, et 1 carte parmi les 13 restantes. Ce qui fait \( 4 \binom{13}{1} \).

                    Dans le problème simplifié de Sebudeci il y a deux lettres qui peuvent apparaître en double (pas en triple), c'est comme si on avait 28 lettres : 26 lettres de carreau, plus le I et le P de trèfle. Donc : 1 parmi 2, 1 parmi 2, 1 parmi les 26 lettres restantes, soit \( 4 \binom{26}{1} \). Zut, ça ne fait pas 3276... Pourtant ça m'avait l'a correct à première vue.

                    Et dans le cas général ? On cherche les combinaisons de L lettres parmi I lettres imposées devant apparaître au moins une fois dans un alphabet de A lettres. Par exemple L = 22, I = 15 et A = 26 (forcément A > L > I). Les lettres imposées peuvent apparaître combien de fois au maximum ? Je dirais L-I+1. Par exemple pour des mots de 3 lettres dont 2 imposées, on peut avoir des lettres imposées en double. Pour des mots de 22 lettres avec 15 imposées, il pourra y avoir jusqu'à 8 apparition d'une même lettre imposée (8 + les 14 autres = 22, CQFD).

                    Je vais donc reprendre mon raisonnement en supposant que les lettres imposées existent en huit couleurs (carreau, trèfle, etc.)

                    Choisissons d'abord les I lettres imposées : 1 parmi 8, 1 parmi 8, etc. 1 parmi 8. Il reste à choisir 7 lettres parmi 11 + 7 + ... + 7 = 11 + 7x15 = 116 (7 lettres à choisir car 15 l'ont déjà été ; 11 lettres non imposées, qui n'existent que dans une seule couleur, plus toutes les lettres imposées qui n'ont pas été choisies : 7 de chaque). 

                    Je refais avec le calcul littéral.

                    - On choisit d'abord une lettre pour chaque lettre imposée : il y a I lettres imposées, et pour chacune on choisit 1 parmi L-I+1. Total : \( I \cdot (L-I+1) \).

                    - Nombres de lettres restantes à choisir : L-I.

                    - Lettres non imposées pas encore choisies : A-I. Lettres imposées pas encore choisies : pour chacune des I lettres imposées, il en reste (L-I+1)-1. Total : \( A-I + I(L-I) \).

                    Ce qui donne (attention les yeux)...

                    \[ I \cdot (L-I+1) \cdot \binom{A-I + I(L-I)}{L-I} \]

                    J'espère ne pas m'être trompé... :ninja:

                    -
                    Edité par robun 26 juin 2020 à 13:17:26

                    • Partager sur Facebook
                    • Partager sur Twitter
                      26 juin 2020 à 10:44:36

                      J'ai lu très très vite.. (j'ai pas lu en fait).

                      On cherche les mots de 22 lettres qui contiennent au moins les 15 lettres suivantes  : etc etc

                      Ok.

                      Donc en fait, on cherche tous les mots de 7 lettres, avec remise, et sans prendre en compte l'ordre.  Et on rajoutera notre séquence de 15 lettres devant chaque mot. Les 15 lettres n'interviennent pas plus que ça dans le problème.

                      On est bien d'accord que PPI=PIP=IPP, PII=IPI=IIP,  mais PPI n'est pas égal à PII ? Et donc, on se moque des 15 lettres qu'on va ajouter systématiquement à chaque mot.

                      • Partager sur Facebook
                      • Partager sur Twitter
                        26 juin 2020 à 10:57:55

                        Bonjour à tous,

                        J'ai lu la plupart, et je dois être très bête, mais dans le cas des combinaisons de 3 lettres contenant au moins un P et un I, ça veut dire que sur les 3 lettres, il y en a 2 de fixes, donc la seule variable est la 3ème lettre => 26 cas. Si on s'en fout de l'arrangement des lettres on arrive que à 26 cas non ? 

                        D'où vient ce 3276 ?

                        Même principe pour le mot de 22 lettres contenant 15 lettres fixes. Ça revient à la même chose que de chercher les combinaisons de 7 lettres (26^7 ?)

                        J'avoue être complètement perdu devant le raisonnement de certains ici ^^

                        C'est la compréhension du problème ou de la solution qui m'échappe ?

                        -
                        Edité par Tiffado 26 juin 2020 à 11:01:16

                        • Partager sur Facebook
                        • Partager sur Twitter
                          26 juin 2020 à 13:10:06

                          Tiffado a écrit:

                          ça veut dire que sur les 3 lettres, il y en a 2 de fixes, donc la seule variable est la 3ème lettre => 26 cas. Si on s'en fout de l'arrangement des lettres on arrive que à 26 cas non ? 

                          C'est ce que je croyais au début, mais ce matin je me suis rendu compte que ça ne collait pas avec la possibilité d'avoir des lettres en double, et je suis parti sur l'astuce des 28 lettres qui me semblait résoudre le problème. Mais voilà que je ne me souviens plus quel était ce problème. Je ne le vois plus. Tout me re-paraît simple : 26 choix.

                          Par contre, pour le cas général, il ne suffit pas de dire : on choisit les 15 lettres imposées, il reste alors 7 lettres à choisir, donc c'est 7 parmi 26. Non, car 7 parmi 26 donnera des lettres distinctes, or parmi ces 26 lettres, 15 d'entre elles (les lettres imposées) peuvent encore apparaître plusieurs fois. Là on a besoin de faire comme si chaque lettre imposée existait en plusieurs exemplaires.

                          Si je me trompe pas, je peux reprendre mon raisonnement dans le cas général, mais en remplaçant I⋅(L−I+1) par 1 (chaque lettre imposée doit apparaître au moins une fois, on n'a pas le choix). Donc le résultat serait :

                          \[ \binom{A-I + I(L-I)}{L-I} \]

                          Pour A = 26, L = 3, I = 2, ça donne \( \binom{24 + 2}{1} \) : ça a l'air juste.

                          -
                          Edité par robun 26 juin 2020 à 13:19:30

                          • Partager sur Facebook
                          • Partager sur Twitter
                            26 juin 2020 à 14:16:56

                            robun a écrit:

                            Tiffado a écrit:

                            ça veut dire que sur les 3 lettres, il y en a 2 de fixes, donc la seule variable est la 3ème lettre => 26 cas. Si on s'en fout de l'arrangement des lettres on arrive que à 26 cas non ? 

                            C'est ce que je croyais au début, mais ce matin je me suis rendu compte que ça ne collait pas avec la possibilité d'avoir des lettres en double, et je suis parti sur l'astuce des 28 lettres qui me semblait résoudre le problème. Mais voilà que je ne me souviens plus quel était ce problème. Je ne le vois plus. Tout me re-paraît simple : 26 choix.

                            Par contre, pour le cas général, il ne suffit pas de dire : on choisit les 15 lettres imposées, il reste alors 7 lettres à choisir, donc c'est 7 parmi 26. Non, car 7 parmi 26 donnera des lettres distinctes, or parmi ces 26 lettres, 15 d'entre elles (les lettres imposées) peuvent encore apparaître plusieurs fois. Là on a besoin de faire comme si chaque lettre imposée existait en plusieurs exemplaires.

                            Si je me trompe pas, je peux reprendre mon raisonnement dans le cas général, mais en remplaçant I⋅(L−I+1) par 1 (chaque lettre imposée doit apparaître au moins une fois, on n'a pas le choix). Donc le résultat serait :

                            \[ \binom{A-I + I(L-I)}{L-I} \]

                            Pour A = 26, L = 3, I = 2, ça donne \( \binom{24 + 2}{1} \) : ça a l'air juste.

                            -
                            Edité par robun il y a environ 1 heure

                            Non mais c'est pas 7 parmi 26 qu'il faut compter, juste pour chaque lettre, tu as 26 possibilités => 26^7.

                            C'est pas aussi simple que ca ?
                            Je ne vois nul part dans l'énoncé l'interdiction d'avoir plusieurs fois la même lettre, qu'elle fasse partie des lettres imposées ou non.

                            Dans l'exemple initial avec 4 lettres dont P et I d'imposés. Est-ce que PIAA est autorisé ?

                            -
                            Edité par Tiffado 26 juin 2020 à 14:21:44

                            • Partager sur Facebook
                            • Partager sur Twitter
                              26 juin 2020 à 16:54:21

                              Tiffado, non parce qu'ainsi tu comptes plusieurs fois les mêmes combinaisons, par exemple en piochant ABAAAAA et BAAAAAA.

                              Le 3276 correspond au nombre de combinaisons de 3 lettres avec remises, donc c'est pas la réponse à la question du nombre de combinaisons de 3 lettres contenant P et I.

                              tbc92 je suis d'accord avec toi, les 15 lettres sont imposées dans on peut les oublier quand on veut dénombrer l'ensemble des possibilités.

                              robun, je comprends pas l'objection, tu aurais un contre-exemple ? Les 15 lettres choisies peuvent très bien réapparaître ou non. Ou alors j'ai mal compris le problème.

                              La page Wikipédia est assez claire : https://fr.wikipedia.org/wiki/Combinaison_avec_r%C3%A9p%C3%A9tition

                              Une combinaison avec répétition de k objets pris dans un ensembleE = {x1x2, … , xn} de n objets discernables est une manière de sélectionner k fois de suite un objet dans E, sans tenir compte de l'ordre des k choix et « avec remise », le même objet pouvant donc être sélectionné plusieurs fois. On obtient ainsi un groupement non ordonné de k objets éventuellement répétés : ce groupement n’est pas un ensemble, la définition en extension d'un ensemble empêchant la répétition des éléments, mais un multiensemble

                              -
                              Edité par leukos 26 juin 2020 à 16:57:37

                              • Partager sur Facebook
                              • Partager sur Twitter
                                26 juin 2020 à 17:39:26

                                leukos a écrit:

                                Tiffado, non parce qu'ainsi tu comptes plusieurs fois les mêmes combinaisons, par exemple en piochant ABAAAAA et BAAAAAA.

                                Le 3276 correspond au nombre de combinaisons de 3 lettres avec remises, donc c'est pas la réponse à la question du nombre de combinaisons de 3 lettres contenant P et I.


                                Ok, merci.

                                Mon cerveau avait mis de côté cette subtilité.

                                • Partager sur Facebook
                                • Partager sur Twitter
                                  26 juin 2020 à 20:22:23

                                  leukos a écrit:

                                  robun, je comprends pas l'objection, tu aurais un contre-exemple ? Les 15 lettres choisies peuvent très bien réapparaître ou non. Ou alors j'ai mal compris le problème.

                                  De quelle objection tu parles ? Celle où je répondais à Tiffado ? (L'idée de base est juste, mais le détail de ma réponse est faux car j'ai cru qu'il calculait 7 parmi 26, en fait c'était 26 puissance 7, ce qui n'est pas correct non plus).
                                  • Partager sur Facebook
                                  • Partager sur Twitter
                                    27 juin 2020 à 3:52:03

                                    Si ça vous intéresse, j'ai trouvé ceci:
                                    http://www.alloprof.qc.ca/BV/pages/m1346.aspx
                                    Ce sera à vous de déterminer de quel cas de figure on parle.
                                    Par exemple 15 lettres sans remise parmi 26 plus 7 avec remise parmi les 11 restantes:
                                    C(26, 15) * 11**7

                                    -
                                    Edité par PierrotLeFou 27 juin 2020 à 4:29:45

                                    • Partager sur Facebook
                                    • Partager sur Twitter

                                    Le Tout est souvent plus grand que la somme de ses parties.

                                      27 juin 2020 à 18:12:16

                                      Au temps pour moi, je pensais que tu contestais ma première réponse.
                                      • Partager sur Facebook
                                      • Partager sur Twitter
                                        27 juin 2020 à 18:30:34

                                        leukos a écrit:

                                        Au temps pour moi, je pensais que tu contestais ma première réponse.

                                        Je ne conteste rien, je n'ai fait que proposer la solution à MON interprétation.

                                        • Partager sur Facebook
                                        • Partager sur Twitter

                                        Le Tout est souvent plus grand que la somme de ses parties.

                                          27 juin 2020 à 20:00:48

                                          Ce n'est pas à moi que leukos répondait ? (Déjà que les calculs sont compliqués, si on commence à ne plus savoir à qui on parle... ;) )

                                          • Partager sur Facebook
                                          • Partager sur Twitter
                                            27 juin 2020 à 21:14:30

                                            La page Wikipedia de Leukos était pas mal aussi.
                                            • Partager sur Facebook
                                            • Partager sur Twitter
                                              31 août 2020 à 14:29:39

                                              Bonjour !

                                              Je n'avais pas vu qu'il y avait eu d'autre réponse. Merci !

                                              Pour moi la méthode de @leukos est la bonne.

                                              donc on trouve pour la solution final : 3 365 856

                                              @robun : c'est en faite la version plus poussé de @leukos ! même si j'ai rien compris au explications avec les cartes et pourquoi tu rajoutes le

                                              robun a écrit:

                                              - Lettres non imposées pas encore choisies : A-I. Lettres imposées pas encore choisies : pour chacune des I lettres imposées, il en reste (L-I+1)-1. Total : \( A-I + I(L-I) \)

                                              Donc merci les gars et très bonne journée a tous !

                                              • Partager sur Facebook
                                              • Partager sur Twitter

                                              Nombre de combinaisons contenant certaines lettres

                                              × Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
                                              • Editeur
                                              • Markdown