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 !
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.
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.
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.
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.
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} \]
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.
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 ?
ç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.
ç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é ?
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.
Une combinaison avec répétition de k objets pris dans un ensembleE = {x1, x2, … , 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.
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.
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).
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 !
Nombre de combinaisons contenant certaines lettres
× 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.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.