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 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

Maintenant simulons deux tirages aléatoires différents :

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

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

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

Bonjour à tous,

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

 

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

J'ai donc un nombre total d'ordonnancement distincts de 40! / (2² * 6¹) soit un total de environ 8×10⁴⁷ / 24 = 3×10⁴⁶

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

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

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 ...

Coucou,

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

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 !!

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

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 ( 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
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

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

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

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.

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 :

• Obtenir un triple et deux cartes distincts :

• Obtenir deux double et une carte :

• Obtenir un double et trois cartes distincts  :

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