Arrangement

La notion d'arrangement est utilisée en probabilités, et surtout pour les dénombrements en analyse combinatoire.

Catégories :

Opération - 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é $Aˆk_n$ et vaut :

$Aˆk_n = n (n-1)(n-2) ... (n-k+1)$

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

$Aˆk_n = \dfrac{n!}{(n-k)!}$

A^k_n 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 ${n \choose k}$ (anciennement $Cˆk_n$ ) par :

${n \choose k} = \dfrac{Aˆk_n}{k!}$

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 (a₁, a₂, ..., a_k) d'éléments de E tel que a_i≠a_j 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é $\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». 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 $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 par conséquent $A_nˆ1 = n$ .
- 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 partitionnent $\mathcal I(F,E)$ en 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 $\mathcal I(F,E)$ à G; il y en a par conséquent $\rm{card}\left(\mathcal I(G, E)\right)$ (la restriction d'une injection à une partie étant injective). Selon le lemme des bergers :
  $A_nˆk = (n - k + 1) _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$ , 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={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 envisageables,
choisir l'image de x₂ et il reste n-1 images envisageables,
...
choisir l'image de x_k, 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

$A_nˆk$ est aussi le nombre de k-arrangements sans répétition d'un ensemble E de cardinal n et nous avons $<img class=$

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;