Arrangement (mathematiques)

Arrangement

Page d'aide sur l'homonymie Pour les articles homonymes, voir Arrangement (homonymie).

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

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 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 (n-1)(n-2) ... (n-k+1)

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

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 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. L'arrangement va consister à additioner à chaque modification possible de cet ensemble de départ la nouvelle probabilité de piocher une question donnée. La solution pour cet exemple est donc 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 l'ensemble des participants.

Sommaire

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 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 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 
  • 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 ≤ kn) 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 ≤ kn 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 possibles,
  • choisir l'image de x2 et il reste n-1 images possibles,
  • ...
  • choisir l'image de xk, il reste dans l'ensemble E 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.

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 \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.

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 = k à n-1)
    i = k
    Tant que i < n
        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 à n)
        for i := n - k to n do
            result := result*i;
 
    end;

Voir aussi

Liens internes

  • Portail des mathématiques Portail des mathématiques
Ce document provient de « Arrangement ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Arrangement (mathematiques) de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Arrangement (Mathématiques) — Arrangement Pour les articles homonymes, voir Arrangement (homonymie). La notion d arrangement est utilisée en probabilités, et notamment pour les dénombrements en analyse combinatoire. En mathématiques, lorsque nous choisissons k objets parmi n… …   Wikipédia en Français

  • Arrangement (mathématiques) — Arrangement Pour les articles homonymes, voir Arrangement (homonymie). La notion d arrangement est utilisée en probabilités, et notamment pour les dénombrements en analyse combinatoire. En mathématiques, lorsque nous choisissons k objets parmi n… …   Wikipédia en Français

  • Arrangement Avec Répétition — Un arrangement avec répétition en mathématiques, se produit lorsque nous rangeons dans un certain ordre k objets, choisis parmi n objets discernables, chaque objet pouvant être répété, nous pouvons représenter les différents rangements par des k… …   Wikipédia en Français

  • Arrangement avec repetition — Arrangement avec répétition Un arrangement avec répétition en mathématiques, se produit lorsque nous rangeons dans un certain ordre k objets, choisis parmi n objets discernables, chaque objet pouvant être répété, nous pouvons représenter les… …   Wikipédia en Français

  • arrangement — [ arɑ̃ʒmɑ̃ ] n. m. • XIIIe; de arranger ♦ Action d arranger; son résultat. 1 ♦ Action de disposer dans un certain ordre; la disposition qui en résulte. ⇒ disposition; assemblage, constitution, organisation. Arrangement d une maison, d un mobilier …   Encyclopédie Universelle

  • Arrangement — Pour les articles homonymes, voir Arrangement (homonymie). La notion d arrangement est utilisée en probabilités, et notamment pour les dénombrements en analyse combinatoire. En mathématiques, lorsque nous choisissons k objets parmi n objets et… …   Wikipédia en Français

  • Arrangement avec répétition — Un arrangement avec répétition en mathématiques, se produit lorsque nous rangeons dans un certain ordre k objets, choisis parmi n objets discernables, chaque objet pouvant être répété, nous pouvons représenter les différents rangements par des k… …   Wikipédia en Français

  • Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants  …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • Denombrement (mathematiques) — Combinatoire Pour les articles homonymes, voir combinatoire (homonymie). Une planche de l encyclopédie de Diderot et d …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”