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)!}

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 {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 :

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 aiaj qqsoit i, j € [1, k] avec ij, . 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 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.

Démonstration 
Démonstration (élémentaire)

Si 1 ≤ kn alors supposons que F={x1, x2, ..., xk}. Pour construire une application injective de F dans E, nous devons

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;

Voir aussi

Recherche sur Amazon (livres) :



Ce texte est issu de l'encyclopédie Wikipedia. Vous pouvez consulter sa version originale dans cette encyclopédie à l'adresse http://fr.wikipedia.org/wiki/Arrangement.
Voir la liste des contributeurs.
La version présentée ici à été extraite depuis cette source le 10/03/2010.
Ce texte est disponible sous les termes de la licence de documentation libre GNU (GFDL).
La liste des définitions proposées en tête de page est une sélection parmi les résultats obtenus à l'aide de la commande "define:" de Google.
Cette page fait partie du projet Wikibis.
Accueil Recherche Aller au contenuDébut page
ContactContact ImprimerImprimer liens d'évitement et raccourcis clavierAccessibilité
Aller au menu