Permutations

[TheReveller]

Bonjour,

Je crois avoir un petit problème de manque de connaissances. En fait, j'aurais bien aimé réussir à trouver les réponses à mes questions par moi-même, mais par manque de temps et en cas de manque de connaissances pour réussir à trouver les meilleures réponses, je me suis dit qu'il valait mieux le demander ici.

J'ai fait un tableau avec le nombre de possibilités de permutations pour un certain nombre de valeurs n et un certain nombre de X.

http://img137.imageshack.us/img137/2099/permutationser8.jpg

Voilà où je veux en venir :

2 valeurs

1 X
2 possibilités : XY et YX
2 X
1 possibilité : XX

3 valeurs

1 X
3 possibilités : XYY, YXY et YYX
2 X
3 possibilités : XXY, XYX et YXX
3 X
1 possibilité : XXX

4 valeurs

1 X
4 possibilités : XYYY, YXYY, YYXY et YYYX
2 X
6 possibilités : XXYY, XYXY, XYYX, YXXY, YXYX et YYXX
3 X
4 possibilités : XXXY, XXYX, XYXX et YXXX
4 X
1 possibilité : XXXX

[etc]

Je sais qu'il y en a beaucoup qui se répètent par symétrie puisqu'il n'y a que deux valeurs différentes (X et Y), mais c'est là mon problème.

Je sais que pour un nombre de valeurs n où toutes les valeurs sont différentes, il y a n! possibilités de permutations.

Sauf que là, j'en ai aucune idée ! Plus que le nombre de valeurs augmentent, plus que les méthodes et formules que je découvre pour trouver le nombre de possibilités deviennent bizarres.

Par exemple, pour tout n valeurs où il y a deux X, les possibilités sont :

1 pour n=2
1+2 pour n=3
1+2+3 pour n=4
1+2+3+4 pour n=5
(n(n-1))/2 pour n

C'est pas trop mal, mais ensuite pour tout n valeurs où il y a trois X, j'arrive à quelque chose de ce genre et je ne sais pas trop comment faire une formule générale :

1 pour n=3
1+(1+2) pour n=4
1+(1+2)+(1+2+3) pour n=5
1+(1+2)+(1+2+3)+(1+2+3+4) pour n=6

Ensuite pour quatre X :

1+(1+(1+2))
1+(1+(1+2))+(1+(1+2)+(1+2+3))
1+(1+(1+2))+(1+(1+2)+(1+2+3))+(1+(1+2)+(1+2+3)+(1+2+3+4))

Ensuite pour cinq X :

1+(1+(1+(1+2)))
1+(1+(1+(1+2)))+(1+(1+(1+2))+(1+(1+2)+(1+2+3)))

Ça devient l'enfer ! Ça doit bien se simplifier, je suis certain qu'il y a une formule toute bête, mais que mon cerveau est trop épuisé ces temps-ci pour réussir à y penser.

Merci de m'éclairer.

[Zebulon]

Bonjour,
vous cherchez le nombre le nombre de façons d'écrire k X dans un mot de n lettres écrit uniquement avec des X et des Y, c'est ça ?
Vous voulez trouver par vous-même donc je ne vous donne pas "la solution", mais faites quelques recherches sur le triangle de Pascal.

[Patastronch]

[quote="TheReveller"][/quote]

Comme Zebulon le dit le triangle de Pascal est une des solutions, mais sans aller jusque la (tu vas tomber sur la réponse) regarde ton tableau et dit moi si tu remarque pas un lien entre les cases :

(n,m) (n,m-1) et (n+1,m-1) (avec n la colonne et m la ligne (=>numero des lignes qui décroient en descendant))

Une fois que tu auras trouvé ce qui relit ces cases, tu pourras définir une fonction f(n,m) qui est connu sous le nom de combinaison.

[TheReveller]

Ah oui, le triangle de Pascal ! Ça faisait longtemps... Peut-être que si j'avais disposé mon tableau autrement, j'aurais eu plus de chances de le voir.

Est-ce possible de calculer la valeur du nombre à la position (i,j) où i est le nombre de lignes et j est le nombre de colonnes ?

Autrement dit, est-ce que c'est calculable à l'aide d'une calculatrice scientifique de base ?

Merci pour votre aide !

[Zebulon]

Est-ce possible de calculer la valeur du nombre à la position (i,j) où i est le nombre de lignes et j est le nombre de colonnes ?

Oui ! Allez voir là :
http://fr.wikipedia.org/wiki/Coefficient_binomial

[TheReveller]

Ouf, je n'aurais jamais trouvé cela tout seul, merci !

Voilà où je voulais en venir :

On a a/c probabilités d'obtenir un X (a 0 et est entier)
On a k le nombre de fois qu'on a obtenu X après n tests. (0 <= k <= n)

Bref, par exemple, pour :

XXXYYYYYYY

On aurait a/c et b/d qui sont à notre choix, n vaut 10 et k vaut 3.

Si a/b vaut 1/3 et b/d vaut 2/3. Les probabilités qu'on obtienne 3 X après 10 tests sont de :

120 * (2^7 / 3^10) = 15360/59049 soit 26,012% de chances

On a alors une formule générale pour les probabilités d'avoir chaque k X après n tests qui est :

(n! * a^k * b^(n-k) / (k! * (n-k)! * c^k * d^(n-k)

Vrai ?

Ou c'est vrai seulement si a/c + b/d = 1
Ou c'est vrai seulement si a ou b vaut 1
Ou c'est vrai seulement si a/c + b/d = 1 et a ou b vaut 1

Ou tout est faux...

Comment ferait-on pour savoir les probabilités que le nombre de X obtenus soit plus grand que le nombre de Y obtenus ? Que le nombre de X obtenus soit égal au nombre de Y obtenus (Il y aura sûrement un problème lorsque n est impair... Ce n'est pas grave, on n'aura qu'à ne pas faire le calcul logiquement) ? Que le nombre de X obtenus soit plus petit que le nombre de Y obtenus ? Tout cela en fonction des variables que nous attribuons.

[fahr451]

maintenant que tu sais tout sur les coefficients binômiaux

C(n,k) est donc le nombre de façons de choisir k éléments (différents sans ordre) dans un ensemble à n éléments et C(n,k) = n!/(k!(n-k)!)
pour un mot de 2n lettres tu as demandé la proba d 'avoir autant de X que de Y ; plus de X que de Y; plus de Y que de X
proba d 'avoir autant de Xque de Y :il y a donc n fois X et n fois Y

il y a 2^(2n) mots au total (2 choix pour la 1ere lettre etc )
on compte le nbre d e mots de 2n lettres avec n X et n y; il suffit de choisir la place des X ,il faut choisir n places parmi les 2n places possibles, il y a par définition C(2n,n) façons, donc une proba d e le faire = C(2n,n) /2^(2n)
pour les deux autres : remarque que par symétrie la proba d 'avoir plus de X que de Y est la même que celle d avoir plus de Y que de X ;or la somme des 3 probas vaut 1; donc celle d 'avoir plus de X = (1-C(2n,n)/2^(2n) ) /2

[TheReveller]

Merci beaucoup.