Mathématiques 2: Analyse combinatoire
Ordre sans répétition
Tirage avec ordre et sans répétition
1. Exemple
Combien de nombres à deux chiffres différents peut-on
former avec les chiffres 1, 3 et 5 ?
Nous avons en tout 3 chiffres et on veut
fabriquer un nombre avec 2 chiffres différents.
Ici l'ordre est important puisque , par exemple,
13 est différent de 31.
Ici aussi, Le tirage est sans répétition puisque
les nombres 11, 22, et 33 ne sont pas recherchés (le
chiffre des dizaines et le chiffre des unités
ne pouvant pas être le même).
La question posée est reformulée ainsi:
Combien de résultas différents obtient-on
en tirant au sort deux billes d’une boite
qui en contient trois, une verte, une rouge
et une blue, avec ordre et sans remise.
1re bille tirée = chiffre des dizaines,
2e bille tirée = chiffre des unités.
Réponse : 6 nombres :
13, 15, 31, 35, 51, 53.
Le diagramme en arbre est le suivant:
2. Cas général
Le nombre d'objets d'un résultat est égal au
nombre de tirages où l'on tire un objet à chaque
tirage. Ce nombre est noté p.
Le nombre d'objets différents sur lequels on effectue
l'expérience aléatoire est noté n.
1er tirage → n possibilités
2e tirage → (n - 1) possibilités
...
→ ...
pe tirage → (n - p + 1) possibilités
Au total, nous avons n x (n - 1) x ... x (n - p + 1)
possibilités. Ce nombre est appelé
nombre d'arragements sans répétition .
L'expression n x (n - 1) x ... x (n - p + 1)
peut être ecrite de la façon suivante:
n x (n - 1) x ... x (n - p + 1) =
n x (n - 1) x ... x (n - p + 1) x (n - p) x (n - p - 1) ... 2 x 1/ (n - p) x (n - p - 1) ... 2 x 1
= n!/(n - p)!
L'expérience aléatoire sans remise et avec ordre
de p objets parmis n est un arrangement sans répétition
de n objets . Ce nombre est noté A(p,n) = n!/(n - p)!
Dans l'exemple ci-dessus, p = 2 et n = 3 . Ainsi
les résultas sont en nombre de 3!/(3 - 2)! = 6
Expérience aléatoire avec ordre et sans répétition :
Arrangement sans répétition de n objets en p objets:
A(p,n) = n!/(n - p)!
3. Cas particulier: Permutations
3.1. Permutations d'objets tous distincts
Lorsqu' on a n objets à arranger en n objets, c'est à dire
le nombre de tirage est égal au nombre d'objets dans
l'ensemble de référence, on dit que l'on a une permutation
de n objets. Dans ce cas, à la fin du tirage, tous les
objets seront tirés. Toujours avec ordre et
sans remise, la formule ci-dessus devient:
A(p,n) = n!/(n - p)! = n!/(n - n)! = n!
Expérience aléatoire avec ordre et sans répétition :
Permutation de n objets :
A(p,n) = n!
3.2. Permutations d'objets distincts dont certains sont identiques
Permuter n objets se fait de n! façons différentes
loraqu'ils sont tous distincts; mais les objets
considérés ne sont pas toujours tous distincts.
On veut savoir le nombre de façons de permuter tous les
chiffres dans le nombre 122324.
S'ils étaient tous distincts, le nombre de permutations sera
6!. Avec trois chiffres identiques le nombre cherché est
sûrement moindre dans un tel cas.
Permuter les trois chiffres "2" dans le nombre donné
ne modifie pas la disposition des chiffres. On
s'en rend même pas compte!. Toutes les permutations,
qui sont en nombre de 3!, des trois chiffres "2" sont
considérées comme une seule et même permutation.
Ainsi chacune des 3! permutations du chiffre "2" qui donnent
une même disposition du nombre donné 122324 se trouvent 3!
fois dans le dénombrement des permutations si l'on
considère les 6 chiffres distincts.
Pour trouver donc le nombre de permutations possibles
dans le nombre donné, il faut diviser le nombre de
permutations des éléments considérés distints par
le nombre de permutations des éléments identiques; ce
qui donne 6!/4! = 5 x 6 = 30.
Le résultat général est le suivant:
Si un ensemble de n éléments qui contient r1 éléments
identiques d'une sorte, r2 éléments identiques d'une
autre sorte, r3 éléments identiques d'une
troisième sorte et ainsi de suite jusqu'à rk éléments
identiques d'une autre sorte, alors le nombre de
permutations de ses n éléments est donné par:
P(n) = n!/(r1! x r2! x r3! x ... x rk!)
avec r1 + r2 + r3 + ... + rk = n
Permutation de n objets dont "ni" sont de sorte "i":
P(n) = n!/(r1! r2! r3! ... rk!)
avec r1 + r2 + r3 + ... + rk = n
3.3. Exemple
On veut placer 10 livres sur une étagère.
De combien de manières différentes peut-on le faire?
3.3.1. Ils sont tous distincts
On prend un au hasard. On le place sur l'étagère.
L'expérience est donc sans répétition.
On prend au hasard un deuxième parmi les 9
qui restent et on le place; et ainsi
de suite jusqu'au 10 ième. On obtient ainsi
une disposition de 10 livres.
Si on recommence l'expérience plusieurs fois, on
obtient plusieurs dispositions. Mais on veut qu'elles
soient toutes différentes; c'est à dire, on veut de
l'ordre.
Ainsi l'expérience aléatoire considérée "de placer
les livres sur une étagère" est sans remise et avec
ordre; c'est donc un arrangement.
Un arragement de 10 objets parmi10 places offertes
est une permutation de 10 objets.
l'expérience aléatoire considérée est une permutation.
Puisque les livres sont distincts, il y a donc 10! =
3 628 800 façons de le faire.
3.3.2. Ils ne sont pas tous distincts
Maintenant, parmi les 10 livres, il y a 5 livres de
Mathématiques identiques, 3 livres de Physique identiques
et 2 livres de Chimie identiques.
l'expérience aléatoire considérée est une permutation.
Les livres ne sont pas tous distincts, Nous avons
trois sortes: une sorte avec 5 livres, l'autre avec
3 livres et la troisième avec 2 livres.
Le nombre de permutations est donc égal à:
p(10) = 10!/5!3!2! = 3 628 800 /1440 = 2520.
Il y a 2520 façons différentes de placer les 10
livres avec les 5-3-2 sortes sur une étagère.
