Permutations et combinaisons

Arrangement d'objets

Exemple

De combien de façons différentes peut-on arranger les lettres  P, Q, R, S ?

La réponse est 4! = 24, parce qu'il y a 4 espaces à remplir :  _, _, _, _

Le premier espace peut être rempli par l'une des quatre lettres, le second par l'une des trois lettres restantes, le troisième espace peut être rempli par l'une des deux lettres restantes et l'espace final doit être rempli par la lettre restante. Le nombre total d'arrangements possibles est donc  4 × 3 × 2 × 1 = 4!

n!      .
p! q! r! …

Exemple

De combien de façons les lettres du mot: STATISTICS peuvent être arrangées?

Il y a  3 S, 2 I et 3 T dans ce mot, par conséquent, le nombre d'arrangements = 

10!        =  50 400
3! 2! 3!

Combinaisons

Soit E un ensemble fini de cardinal n et k un entier naturel. Les combinaisons de cet ensemble sont ses sous-ensembles (ou ses parties). Une k-combinaison de E (ou k-combinaison sans répétition de E, ou encore combinaison sans répétition de n éléments pris kà k) est une partie à k éléments de E.

Nous notons \mathcal P_k(E) l’ensemble des k-combinaisons de E.

L’ensemble \mathcal P_k(E) des combinaisons à k éléments de E est fini et son cardinal se note {n \choose k} (ce qui se lit « k parmi n » ) ou encore C_n^k\, (qui se lit « combinaison de k parmi n »), la première notation étant préconisée par la norme ISO, et C_n^k=\tfrac{A_n^k}{k!}, où A_n^k est le nombre de k-arrangements de E.

Avec la formule pour A_n^k on obtient C_n^k=\frac{n(n-1)\ldots (n-k+1)}{k!}, qui pour k  n peut aussi s'écrire : C_n^k=\frac{n!}{k!(n-k)!}.

Exemple

Dans un sac, on a 10 boules numérotées de 1 à 10. Trois boules sont choisies au hasard. De combien de façons différentes peut-on tirer les trois boules ?

10C3 =10!=10 × 9 × 8= 120
             3! (10 – 3)!3 × 2 × 1

Permutations simples

Une permutation d'un ensemble X est une bijection de X sur lui-même.

Notamment, une permutation de n éléments (où n est un entier naturel) est une bijection d'un ensemble fini de cardinal n sur lui-même.

Si X est un ensemble fini de cardinal n, alors l'ensemble des permutations de X est fini, de cardinal n !.

Exemple
Les 4! = 24 permutations de 4 éléments distincts a, b, c, d :
abcd  bacd  cabd  dabc  abdc  badc  cadb  dacb
acbd  bcad  cbad  dbac  acdb  bcda  cbda  dbca
adbc  bdac  cdab  dcab  adcb  bdca  cdba  dcba

Exemple type
Nombre de dispositions de cinq personnes sur un banc de cinq places

Permutations avec répétitions

Le nombre de permutations que l'on peut constituer si certains des éléments sont identiques est plus petit que si tous les éléments sont distincts.
Théorème

Le nombre p(n1, n2, ..., nk) de permutations de n éléments avec n1, n2, ..., nk répétitions est

p(n_1, n_2, \ldots, n_k)=\frac{n!}{n_1!.n_2!\ldots n_k!}.

Ce nombre se note habituellement C_{n}^{n_1,n_2, \ldots, n_k}.

Exemple  

Quel est le nombre de permutations possibles avec les lettres du mot indienne ?

Pn (ri = 2; re = 2 ; rn = 3) = 8! / (2! 2!  3! ) = 1680

Probabilité

Les formules précédentes peuvent-être utilisées pour résoudre des problèmes de probabilité..

Par exemple

Au loto, 6 numéros sont tirés parmi 49. Vous gagnez si les 6 numéros que vous avez choisis sont identiques aux numéros tirés par la machine. Quelle est donc la probabilité de gagner au loto ?

Il existe  49C6 = 13 983 816 façons de choisir 6 numéros parmi les 49.

Donc la probabilté de gagner au loto est de 1/13983816 = 0.000 000 071 5, ce qui fait environ 1 chance sur 14 millions.