Arrangement

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur les redirections Pour l'activité musicale homonyme, voir Arrangement (musique).

En mathématiques, l'arrangement fait partie de l'analyse de dénombrement (ou combinatoire) et est utilisée, entre autres, dans le calcul de probabilité.

Lorsque nous choisissons k objets parmi n objets et que l’ordre dans lequel les objets sont sélectionnés revêt une importance, nous pouvons les représenter par un k-uplet d'éléments distincts et on en constitue une liste ordonnée sans répétition possible, c'est-à-dire dans laquelle l'ordre des éléments est pris en compte (si l'on permute deux éléments de la liste, on a une liste différente, et un élément ne peut être présent qu'une seule fois).

Une telle liste ordonnée est appelée un arrangement. Le nombre d'arrangements que l'on peut faire est noté A^k_n et vaut :

A^k_n = n \left(n - 1\right) \left(n - 2\right) \cdots \left(n - k + 1\right)

Cette formule peut se comprendre à l'aide d'un arbre des choix successifs, puisque le premier élément est choisi parmi n, le second parmi (n – 1)… et le dernier parmi (nk + 1).

Avec la notation factorielle, où n! = 1×2×…×n, cette formule devient

A^k_n = \dfrac{n!}{(n-k)!}\quad\mbox{pour }k\leq n,

tandis que A^k_n=0 pour k > n (ce qui exprime le principe des tiroirs). Il s’agit en fait simplement de la factorielle décroissante appliquée aux seuls entiers naturels :

A^k_n = n^{\underline{k}}

Akn est en fait le nombre d'injections que l'on peut faire d'un ensemble à k éléments vers un ensemble à n éléments. Le nombre d'arrangements est lié au coefficient binomial {n \choose k} (anciennement  C^k_n) par :

{n \choose k} = \dfrac{A^k_n}{k!}

Exemples[modifier | modifier le code]

Exemple d'énumération d'éléments par arrangement[modifier | modifier le code]

Soit un ensemble de 4 éléments E = {a, b, c, d}. Les arrangements sans répétition de 3 éléments choisis parmi les 4 éléments de E sont  : \begin{matrix}
(a,b,c),&(a,c,b),&(b,a,c),&(b,c,a),&(c,a,b),&(c,b,a),\\
(a,b,d),&(a,d,b),&(b,a,d),&(b,d,a)&(d,a,b),&(d,b,a),\\
(a,c,d),&(a,d,c),&(c,a,d),&(c,d,a),&(d,a,c),&(d,c,a),\\
(b,c,d),&(b,d,c),&(c,b,d),&(c,d,b),&(d,b,c),&(d,c,b).
\end{matrix}

Il y en a A_4^3=24.

Exemple de dénombrement pour n grand[modifier | modifier le code]

À un examen, cinq candidats tirent les uns après les autres un sujet dans une urne contenant des questions toutes différentes. Le premier tirage se fera sur un ensemble de 50 questions possibles. À chaque tirage suivant, la question qui vient d'être tirée est enlevée de l'urne. Ainsi, en faisant passer les cinq candidats, le tirage se fait d'abord sur 50, puis sur 49, et ainsi de suite jusqu'à 46 qui représente l'ensemble des questions restantes dans l'urne pour le dernier tirage. Le nombre d'arrangements pour cette série de 5 questions prises parmi 50 est alors de 50 × 49 × 48 × 47 × 46.

Si on remettait la question tirée de nouveau dans l'urne à chaque tirage, ce serait un arrangement avec répétition de 5 (k) parmi 50 (n), et la solution vaudrait 505.

Exemples d'arrangements :

  • une phrase sans répétition de mot est un arrangement du dictionnaire ;
  • une association forme son bureau (président, trésorier, secrétaire) à partir des membres de l'association ; le bureau est un arrangement de l'association ;
  • le podium d'une course est un arrangement de l'ensemble des participants.

Définition mathématique[modifier | modifier le code]

Définition :

Soient E un ensemble fini de cardinal n et k un entier naturel. Un k-arrangement sans répétition de E est une application injective de {1, 2, ..., k} dans E.

Autre définition :

Soient E un ensemble fini de cardinal n et k un entier naturel. Un k-arrangement de E (ou k-arrangement sans répétition de E, ou encore arrangement sans répétition de n éléments pris k à k) est un k-uplet (a1, a2, ..., ak) d'éléments de E tel que aiaj quel que soit i, j ∈ [1, k] avec ij. Un tel k-uplet est aussi appelé k-liste distincte d'éléments de E.

Théorème[modifier | modifier le code]

Soient E et F deux ensembles finis de cardinaux respectifs n et k. L’ensemble \mathcal I(F, E) des applications injectives de F dans E est fini et son cardinal est égal à n(n – 1)... (nk + 1) si kn et 0 sinon. Ce cardinal se note A_n^k et se lit « Ank ». On dit aussi qu'on a un arrangement de k à n.

Corollaire[modifier | modifier le code]

A_n^k est aussi le nombre de k-arrangements sans répétition d'un ensemble E de cardinal n et nous avons \forall n, k \in \mathbb{N}, A_n^k=\left\{\begin{matrix}0 & \rm{\,si\,} & k>n\\\dfrac{n!}{(n-k)!} & \rm{\,si\,} & k\leq n\\\end{matrix}\right.

Démonstration :

Supposons F={x1, x2, ..., xk}. Une injection f de F dans E s'identifie au k-uplet d'éléments distincts (f(x1), f(x2), ..., f(xk)). Il y a donc une bijection entre l'ensemble des applications injectives de F dans E et l'ensemble des k-uplets d'éléments distincts de E.

Remarque :

Construire un arrangement revient à placer les uns après les autres, k objets discernables pris parmi n, dans k cases numérotées et donc une permutation de n éléments est un n-arrangement de n éléments. La notion d'arrangement généralise donc celle de permutation.

Articles connexes[modifier | modifier le code]