Arrangement

En mathématiques, lorsque nous choisissons k objets parmi n objets discernables 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. Par exemple, quand à un examen, cinquante candidats tirent les uns après les autres un sujet dans une urne contenant des questions toutes différentes, il est possible de représenter les tirages par des 50-uplets de questions.

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 (a₁, a₂, ..., a_k) d'éléments de E tel que pour i≠j, a_i≠a_j. Un tel k-uplet est aussi appelé k-liste distincte d'éléments de E.

Théorème :

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)... (n-k+1) si k⩽n et 0 sinon. Ce cardinal se note $A_n^k$ et se lit « Ank ».

Démonstration :

Si k > n, alors il n'existe aucune injection de F dans E et donc $A_n^k=0$ .
Si k ⩽ n, alors démontrons l'égalité par récurrence sur l'entier k.
- Si k = 1 alors F est un singleton et toute application de F dans E est injective donc $A_n^1 = n$ .
- Supposons l'égalité vérifiée pour tout ensemble F de cardinal k - 1 (2⩽k⩽ n) et démontrons la au rang k :
  Soit F un ensemble de cardinal k, et x un élément de F. Posons G=F\{x}. Nous avons card(G)=k-1.
  Considérons la relation qui relie deux injections de F dans E quand elles ont même restriction à G. Les classes d'équivalence partitionnent $\mathcal I(F,E)$ en classes ayant toutes comme cardinal n-(k-1). En effet, il y a autant de façons de prolonger une injection de G dans E en une injection de F dans E que de choix de l'image de x parmi les n-k+1 images possibles. De plus le nombre de classes d'équivalence est égal au nombre de restrictions différentes d'applications de $\mathcal I(F,E)$ à G; il y en a donc $\rm{card}\left(\mathcal I(G, E)\right)$ (la restriction d'une injection à une partie étant injective). D'après le lemme des bergers:
  $A_n^k = (n - k + 1). A_n^{k-1}= n(n - 1) \ldots (n-k+2)(n- k+1)$ .
Si k=0, nous poserons par convention pour tout entier naturel n $A_n^0=1$ , puisqu'il existe une seule application qui va de l'ensemble vide ∅ dans un ensemble quelconque E qui de plus est injective !

Démonstration (élémentaire):

Si 1 ⩽ k ⩽ n alors supposons que F={x₁, x₂, ..., x_k}. Pour construire une application injective de F dans E, nous devons

choisir l'image de x₁ et il y a n images possibles,
choisir l'image de x₂ et il reste n-1 images possibles,
...
choisir l'image de x_k, il reste dans l'ensemble F n-(k-1) éléments non atteints donc n-(k-1) images possibles.

Au total, nous avons construit n.(n-1).....(n - k + 1) applications injectives différentes.

Corrolaire :

$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\\\frac{n!}{(n-k)!} & \rm{\,si\,} & k\leq n\\\end{matrix}\right.$

Démonstration :

Supposons F={x₁, x₂, ..., x_k}. Une injection f de F dans E s'identifie au k-uplet d'éléments distincts (f(x₁), f(x₂), ..., f(x_k)). 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.

Arrangement

Voyez aussi

See also: Arrangement, Arrangement avec répétition, Combinaison, Combinaison avec répétition, Combinatoire, Lemme des bergers, Mathématiques, N-uplet, Permutation, Permutation avec répétition