Arrangement
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

Voir aussi : Arrangement (musique)

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.

Exemple : A 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 (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble), « une...) de 50 questions possibles. A chaque tirage suivant, la question qui vient d'être tirée est enlevée de l'urne. Ainsi, s'il on faisait passer (Le genre Passer a été créé par le zoologiste français Mathurin Jacques Brisson (1723-1806) en 1760.) 5 élèves, le tirage se ferait 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 (La notion d'arrangement est utilisée en probabilités, et notamment pour les dénombrements en analyse combinatoire.) va consister a additioner à chaque modification de cet ensemble de départ la nouvelle probabilité (La probabilité (du latin probabilitas) est une évaluation du caractère probable d'un évènement. En mathématiques, l'étude des probabilités est un sujet...) de piocher une question donnée (Dans les technologies de l'information, une donnée est une description élémentaire, souvent codée, d'une chose, d'une transaction, d'un...). 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, il s'agirait alors d'une combinaison (Une combinaison peut être :).

Définition :

Soient E un ensemble fini (En mathématiques, un ensemble E est dit fini si et seulement si E est vide ou s'il existe un entier n et une bijection de E dans l'ensemble des n premiers entiers naturels.) 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 (Le mot injection peut avoir plusieurs significations :) 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 (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou l'univers.) ensemble F de cardinal k - 1 (2 ≤ kn) et démontrons la au rang ( Mathématiques En algèbre linéaire, le rang d'une famille de vecteurs est la dimension du sous-espace vectoriel engendré par cette famille. Le théorème du rang lie le rang et la dimension du noyau d'une application...) 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 (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) 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 (En mathématiques, l'ensemble vide est l'ensemble ne contenant aucun élément.) ∅ dans un ensemble quelconque E qui de plus est injective !

Démonstration (En mathématiques, une démonstration permet d'établir une proposition à partir de propositions initiales, ou précédemment démontrées à partir de propositions...) (é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 ( Total est la qualité de ce qui est complet, sans exception. D'un point de vue comptable, un total est le résultat d'une addition, c'est-à-dire une somme....), 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\\\frac{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 (Une fonction f: X → Y est dite bijective ou est une bijection si pour tout y dans l’ensemble d'arrivée Y il existe un et un seul x dans l’ensemble de définition X tel...) 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 (En mathématiques, la notion de permutation exprime l'idée de réarrangement d'objets discernables. Une permutation de n objets distincts rangés dans un certain ordre, correspond à...) de n éléments est un n-arrangement de n éléments. La notion d'arrangement généralise donc celle de permutation.

Voyez aussi

  • combinatoire (En mathématiques, la combinatoire, appelée aussi analyse combinatoire, étudie les configurations de collections finies d'objets ou les combinaisons d'ensembles finis, et les dénombrements.)
  • arrangement avec répétition
  • combinaison
  • combinaison avec répétition
  • Permutation
  • Permutation avec répétition
Page générée en 0.101 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique