Arrangement
La notion d'arrangement est utilisée en probabilités, et surtout pour les dénombrements en analyse combinatoire.
Page(s) en rapport avec ce sujet :
- Un arrangement est une suite ordonnée de p éléments, c'est-à-dire que, contrairement aux combinaisons, l'ordre intervient : prenons l'exemple d'un ensemble... (source : bibmath)
- 1) La classification des éléments figuratifs est constituée par une liste des .... il est rangé et le nombre total des unités de la totalité des pays..... 2) A l'égard de tout pays autre que ceux pour lesquels l'arrangement est entré en ... (source : wipo)
La notion d'arrangement est utilisée en probabilités, et surtout pour les dénombrements en analyse combinatoire.
En mathématiques, quand nous choisissons k objets parmi n objets discernables et que l'ordre dans lequel les objets sont choisis revêt une importance, nous pouvons les représenter par un k-uplet d'éléments différents et on en forme une liste ordonnée sans répétition envisageable, c'est-à-dire dans laquelle l'ordre des éléments est pris en compte (si 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 nommée un arrangement. Le nombre d'arrangements qu'on peut faire est noté et vaut :
Cette formule peut se comprendre avec un arbre des choix successifs, puisque le premier élément est choisi parmi n, le second parmi (n-1)... et le dernier parmi (n-k+1). Avec la notation factorielle, où n! = 1×2×... n, cette formule devient
Akn est en fait le nombre d'injections qu'on peut faire d'un ensemble à k éléments vers un ensemble à n éléments. Le nombre d'arrangements est lié au cœfficient binomial (anciennement
) par :
Exemple : À 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 envisageables. À chaque tirage suivant, la question qui vient d'être tirée est retirée de l'urne. Ainsi, en faisant passer les cinq candidats, le tirage se fait en premier lieu sur 50, puis sur 49, et ainsi de suite jusqu'à 46 qui représente la totalité des questions restantes dans l'urne pour le dernier tirage. L'arrangement va consister à additioner à chaque modification envisageable de cet ensemble de départ la nouvelle probabilité de piocher une question donnée. La solution pour cet exemple est par conséquent un arrangement de 5 (k) à 50 (n).
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) à 50 (n), et la solution vaudrait 50ˆ5.
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 la totalité des participants.
Définition mathématique
- 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 ai≠aj qqsoit i, j € [1, k] avec i≠j, . Un tel k-uplet est aussi nommé k-liste différente d'éléments de E.
- Théorème
Soient E et F deux ensembles finis de cardinaux respectifs n et k. La totalité 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
et se lit «Ank». On dit aussi qu'on a un arrangement de k à n.
- Démonstration
- Si k > n, alors il n'existe aucune injection de F dans E et par conséquent
.
- 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 par conséquent
.
- Supposons l'égalité vérifiée pour tout ensemble F de cardinal k - 1 (2 ≤ k ≤ n) et démontrons l'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 lorsqu'elle s ont même restriction à G. Les classes d'équivalence partitionnenten classes ayant toutes comme cardinal n- (k-1). En effet, il y a tout 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 envisageables. De plus le nombre de classes d'équivalence est égal au nombre de restrictions différentes d'applications de
à G; il y en a par conséquent
(la restriction d'une injection à une partie étant injective). Selon le lemme des bergers :
.
- Si k = 1 alors F est un singleton et toute application de F dans E est injective par conséquent
- Si k=0, nous poserons par convention pour tout entier naturel n
, dans la mesure où il existe une seule application qui va de la totalité vide ∅ dans un ensemble quelconque E qui de plus est injective !
- Démonstration (élémentaire)
Si 1 ≤ k ≤ n alors supposons que F={x1, x2, ..., xk}. Pour construire une application injective de F dans E, nous devons
- choisir l'image de x1 et il y a n images envisageables,
- choisir l'image de x2 et il reste n-1 images envisageables,
- ...
- choisir l'image de xk, il reste dans la totalité E n - (k-1) éléments non atteints par conséquent n - (k-1) images envisageables.
Au total, nous avons construit n. (n-1)..... (n - k + 1) applications injectives différentes.
- Corollaire
est aussi le nombre de k-arrangements sans répétition d'un ensemble E de cardinal n et nous avons
Algorithme de calcul
En pseudo-code
Fonction Arrangements (n, k) Ank = 1 // Test aux limites Si k < 0 ou k > n alors Retourner 0 Fin Si // Calcul de Ank (boucle de i = n - k + 1 à n) i = n - k + 1 Tant que i < n + 1 Ank = Ank * i i = i + 1 Fin tant que Retourner Ank Fin fonction
En Java
int arrangements(final int n, final int k) { int Ank = 1; // Test aux limites if (k < 0 || k > n) { return 0; } // Calcul de Ank (boucle de i = n-k à n) for (int i = n - k + 1; i <= n; i++) { Ank *= i; } return Ank; }
En Pascal (Delphi)
function arrangements(n, k : integer):longint; var i : integer; begin // Test aux limites if (k < 0) or (k > n) then begin result := 0; exit; end; result := 1; // Calcul de Ank (boucle de i = n-k+1 à n) for i := n - k + 1 to n do result := result*i; end;